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):
import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LS() for _ in range(M)]
path = {}
allpath = []

for ind,ab in enumerate(AB):
  if ab[0] not in path:
    path[ab[0]] = []
  tmp = []
  tmp.append(ind+1)
  tmp.append(ab[1])
  path[ab[0]].append(tmp[::])
  if ab[1] not in path:
    path[ab[1]] = []
  tmp = []
  tmp.append(-ind-1)
  tmp.append(ab[0])
  path[ab[1]].append(tmp[::])

#print(path)




def dfs(st, end):
  global allpath
  stack = []
  #res = []
  is_passed = [False] * (M*2+1)
  hist = [[0, '0']]
  now = [0, st]
  pre = None
  st_flag = (st!=end)
  while True:
    #print(now)
    #print(stack)
    hist.append(now)
    #print(hist)
    if now[0] != 0:
      if now[1] != '1':
      	is_passed[now[0]] = True
    if st_flag and now[1] == end:
      # ended
      #print("\tsuccess! route is below:\n\t\t{0}".format(hist))
      allpath.append(hist)
      if not stack:
        break
      next = stack[len(stack)-1]
      target_p = AB[abs(next[0])-1]
      if target_p[0] == next[1]:
        target = target_p[1]
      else:
        target = target_p[0]
      for i,v in enumerate(hist[-2::-1]):
        if v[1] == target:
          break
        is_passed[v[0]] = False
      #print("hit id is {0}".format(i))
      hist = hist[0:len(hist)-i-1]
      #print(hist)
    else:
      st_flag = True
      useflag = True
      for v in path[now[1]]:
        if is_passed[v[0]]:
          continue
        if v[1]==hist[len(hist)-2][1]:
          continue
        for w in hist[2:]:
          if v[1]==w[1]:
            break
        else:
          stack.append(v)
          useflag = False
        continue
      if useflag:
        #print("\tno route from path{0}".format(now))
        #print("\tstack is {0}".format(stack))
        if not stack:
          break
        next = stack[len(stack)-1]
        #print("\tnext is {0}".format(next))
        target_p = AB[abs(next[0])-1]
        if target_p[0] == next[1]:
          target = target_p[1]
        else:
          target = target_p[0]
        #print("\ttarget is {0}".format(target))
        for i,v in enumerate(hist[::-1]):
          if v[1] == target:
            break
          is_passed[v[0]] = False
        hist = hist[0:len(hist)-i]
    if not stack:
      
      break
    now = stack.pop()

dfs('1','1')
for P in allpath:
  if len(P) == N+2:
    print("yes")
    Q = []
    for p in P:
      if p[0] == 0:
        continue
      tmp = AB[abs(p[0])-1][0]
      if tmp == p[1]:
      	tmp = AB[abs(p[0])-1][1]
      Q.append([tmp, p[1]])
    Q.sort(key=lambda x:x[0])
    #print(Q)
    for q in Q[1:]:
      print(q[1])
    break

Fixed, accepted submission:
import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LI() for _ in range(M)]
path = [[] for _ in range(N+1)]
mp = []
ans = [0] * (N+1)

for ab in AB:
	a = ab[0]
	b = ab[1]
	path[a].append(b)
	path[b].append(a)
	#print(a,b)

def bfs(tree, st, endlist, endnum):
	queue = collections.deque()
	queue.append([-1,st])
	endlist[st] -= 1
	now = [-1,-1,-1]
	pre = []
	depth = 0
	histind = -1
	node = -1
	hist = []
	res = []
	allres = []
	while queue:
		pre = now[:]
		now = queue.popleft()
		histind = now[0]
		node = now[1]
		hist.append([histind,node])
		
		res = [node,hist[histind][1]]
		allres.append(res[::])
		endnum -= 1
		if endnum == 0:
			return allres
		for v in path[node]:
			if endlist[v] > 0:
				queue.append([len(hist)-1,v])
				
				endlist[v] -= 1
		continue
	return None

#print_map(path)
result = bfs(path, 1, [1] * (N+1), N)
#print("[TO, FROM] = {0}".format(result))
if result is None:
	print("No")
	exit(0)
print("Yes")
execnum = N
maxlen = len(result[len(result)-1])
for i in result:
	#print(i)
	if ans[i[0]] == 0:
		ans[i[0]] = i[1]
		execnum-=1
		if execnum == 0:
			break

for i in ans[2:]:
	print(i)