Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import heapq


class Dijkstra:
    """
    dijkstraの最短経路問題を解く
    input:
        S: start node
        mat : mat[a][b] = edge_weight(a,b)
    """

    def __init__(self, start, num_node, mat):
        """
        mat: mat[a][b] = edge_weight(a,b)
        num_node: num of nodes
        dist: dist from start_node
        prev: 最短経路において、一つ前のノードを記憶。経路復元に使う?
        """
        self.start_node = start
        self.mat = mat
        self.num_node = num_node
        self.dist = [float('inf')]*num_node
        self.prev = defaultdict(lambda: None)

        # dist form S to S = 0
        self.dist[start] = 0

    def calc_dist(self):
        """
        最短経路 distを計算する
        Q: content (dist_from_start,node)
        Qはheapqとして使う。dist_from_startの小さい順になる
        """
        Q = []
        heapq.heappush(Q, (0, self.start_node))
        while Q:
            dist_to_node, node = heapq.heappop(Q)
            # 現在の値よりも大きくて、更新にならない場合
            if self.dist[node] < dist_to_node:
                continue

            # 次のホップを計算する
            for nex in range(self.num_node):
                weight = self.mat[node][nex]
                cand = dist_to_node + weight

                if self.dist[nex] > cand:  # update
                    self.dist[nex] = cand
                    self.prev[nex] = node
                    heapq.heappush(Q, (cand, nex))

    def get_dist(self, d):
        """
            startからdまでの距離を返す
            これの前にcalc()を実行しておく
            たどり着けない場合は、float('inf')がかえる
        """
        return self.dist[d]
    def get_path(self,dst):
        """
        startからdstまでのpathをlistでreturn
        valifyしてないので怪しい
        """
        cur=dst
        ret=[cur]
        while cur!=self.start_node:
            cur=self.prev[cur]
            ret.append(cur)
        return list(reversed(ret))

N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

grid=[[float("inf")]*N for _ in range(N)]

for a,b in edges:
    grid[a][b]=1
    grid[b][a]=1

D = Dijkstra(0,N,grid)
D.calc_dist()

ans=[]
for i in range(1,N):
    ans.append(D.prev[i]+1)
print("Yes")
print("\n".join(map(str,ans)))


Fixed submission:
N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

adj=[set() for _ in range(N)]

for a,b in edges:
    adj[a].add(b)
    adj[b].add(a)

start=0
dst=[-1]*N
visited={0}

Q={start}

while Q:
    tmp=set()
    for cur in Q:
        for nex in adj[cur]:
            if nex in visited:
                continue
            dst[nex]=cur
            visited.add(nex)
            tmp.add(nex)
    Q=tmp

print("Yes")
print("\n".join(map(str,[v+1 for v in dst[1:]])))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import heapq


class Dijkstra:
    """
    dijkstraの最短経路問題を解く
    input:
        S: start node
        mat : mat[a][b] = edge_weight(a,b)
    """

    def __init__(self, start, num_node, mat):
        """
        mat: mat[a][b] = edge_weight(a,b)
        num_node: num of nodes
        dist: dist from start_node
        prev: 最短経路において、一つ前のノードを記憶。経路復元に使う?
        """
        self.start_node = start
        self.mat = mat
        self.num_node = num_node
        self.dist = [float('inf')]*num_node
        self.prev = defaultdict(lambda: None)

        # dist form S to S = 0
        self.dist[start] = 0

    def calc_dist(self):
        """
        最短経路 distを計算する
        Q: content (dist_from_start,node)
        Qはheapqとして使う。dist_from_startの小さい順になる
        """
        Q = []
        heapq.heappush(Q, (0, self.start_node))
        while Q:
            dist_to_node, node = heapq.heappop(Q)
            # 現在の値よりも大きくて、更新にならない場合
            if self.dist[node] < dist_to_node:
                continue

            # 次のホップを計算する
            for nex in range(self.num_node):
                weight = self.mat[node][nex]
                cand = dist_to_node + weight

                if self.dist[nex] > cand:  # update
                    self.dist[nex] = cand
                    self.prev[nex] = node
                    heapq.heappush(Q, (cand, nex))

    def get_dist(self, d):
        """
            startからdまでの距離を返す
            これの前にcalc()を実行しておく
            たどり着けない場合は、float('inf')がかえる
        """
        return self.dist[d]
    def get_path(self,dst):
        """
        startからdstまでのpathをlistでreturn
        valifyしてないので怪しい
        """
        cur=dst
        ret=[cur]
        while cur!=self.start_node:
            cur=self.prev[cur]
            ret.append(cur)
        return list(reversed(ret))

N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

grid=[[float("inf")]*N for _ in range(N)]

for a,b in edges:
    grid[a][b]=1
    grid[b][a]=1

D = Dijkstra(0,N,grid)
D.calc_dist()

ans=[]
for i in range(1,N):
    ans.append(D.prev[i]+1)
print("Yes")
print("\n".join(map(str,ans)))


Fixed submission:
N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

adj=[set() for _ in range(N)]

for a,b in edges:
    adj[a].add(b)
    adj[b].add(a)

start=0
dst=[-1]*N
visited={0}

Q={start}

while Q:
    tmp=set()
    for cur in Q:
        for nex in adj[cur]:
            if nex in visited:
                continue
            dst[nex]=cur
            visited.add(nex)
            tmp.add(nex)
    Q=tmp

print("Yes")
print("\n".join(map(str,[v+1 for v in dst[1:]])))