Problem:
There is a cave.  The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.  It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.  Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.    * If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.  Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

Incorrect submission (verdict: Wrong Answer):
from sys import stdin
from sys import setrecursionlimit
import math
setrecursionlimit(10 ** 7)

n,m = map(int,stdin.readline().rstrip().split())
li = [[]for _ in range(n)]
lin = []

for i in range(m):
    a,b = map(int,stdin.readline().rstrip().split())
    a -= 1
    b -= 1
    li[a].append(b)
    li[b].append(a)
    lin.append([a,b])

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


def depth_first_search(start, W):
    
    work_stack = []
    visited = set()
    work_stack.append(start)
    visited.add(start)
    while work_stack:
        print(work_stack)  
        here = work_stack.pop()
        for i, node in enumerate(W[here]):
            if node == 0: continue
            if i not in visited:
                work_stack.append(i)
                visited.add(i)
    return visited

uni = UnionFind(n)

lis = [0]*n
visited = [False]*n
visited[0] = True
oya = 0
def keiro(now):
    ima = li[now]
    for i in ima:
        if visited[i]:
            continue
        else:
            lis[i] = now
            visited[i] = True
            keiro(i)

keiro(0)
print("Yes")
for i in lis[1:]:
    print(i+1)

print(lis)


Fixed, accepted submission:
from sys import stdin
from sys import setrecursionlimit
from queue import deque
setrecursionlimit(10 ** 7)

n,m = map(int,stdin.readline().rstrip().split())
li = [[]for _ in range(n)]
lin = []

length = {}
length_path = [0]*n

for i in range(m):
    a,b = map(int,stdin.readline().rstrip().split())
    a -= 1
    b -= 1
    li[a].append(b)
    li[b].append(a)
    if a < b:
        length[(a,b)] = 1
    else:
        length[(b,a)] = 1
    lin.append([a,b])


work_queue = deque([])
visited = [False]*n
work_queue.append(0)
while work_queue:
    now = work_queue.popleft()
    visited[now] = True
    for i in li[now]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if now < i:
            length_path[i] = length_path[now]+length[(now,i)]
        else:
            length_path[i] = length_path[now]+length[(i,now)]
kotae = [0]*n

for num,i in enumerate(li):
    ima = i
    now = 10**10
    for j in ima:
        if length_path[j] < now:
            now = length_path[j]
            k = j
    kotae[num] = k+1
print("Yes")
for i in kotae[1:]:
    print(i)