Problem:


Score: 400 points

Problem Statement

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.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 2 \times 10^5

1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)

A_i \neq B_i\ (1 \leq i \leq M)

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

If there is no way to place signposts satisfying the objective, print No.

Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

If we place the signposts as described in the sample output, the following happens:

Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.

Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.

Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.

Thus, the objective is satisfied.

Sample Input 2

6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6

Sample Output 2

Yes
6
5
5
1
1

If there are multiple solutions, any of them will be accepted.



Sample input:
4 4
1 2
2 3
3 4
4 2


Sample output:
Yes
1
2
2

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		route[A - 1] += [B]
		route[B - 1] += [A]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)
	signal_cnt = 0

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		if checked[src - 1] == 0:
			checked[src - 1] = 1
			signal[src - 1] = str(checking["dst"])
			signal_cnt += 1
			rooms = route[src - 1]
			for r in rooms:
				if checked[r - 1] == 0:
					to_check.append({"src": r, "dst": src})
	if signal_cnt != N - 1:
		print("No")
	else:
		print("Yes")
		print("\n".join(signal[1:]))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		route[A - 1] += [B]
		route[B - 1] += [A]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		if checked[src - 1] == 0:
			checked[src - 1] = 1
			signal[src - 1] = checking["dst"]
			rooms = route[src - 1]
			for r in rooms:
				if checked[r - 1] == 0:
					to_check.append({"src": r, "dst": src})
	if signal.count(0) > 0:
		print("No")
	else:
		print("Yes")
		print("\n".join([str(q) for q in signal[1:]]))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		M = max([A, B])
		m = min([A, B])
		route[m - 1] += [M]
		route[M - 1] += [m]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		if checked[src - 1] == 0:
			checked[src - 1] = 1
			signal[src - 1] = checking["dst"]
			rooms = route[src - 1]
			for r in rooms:
				to_check.append({"src": r, "dst": src})
	if signal.count(0) > 0:
		print("No")
	else:
		print("Yes")
		print("\n".join([str(q) for q in signal[1:]]))

main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N, M = map(int, input().split())
res = [[] for i in range(N+5)]


for i in range(M) :
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    res[a].append(b)
    res[b].append(a)
    
pre = [-1] * N
d = 1
dl = []
pre[0] = 0

for i in res[0] :
    dl.append((i,0))

while(len(dl) != 0) :
    a,b = dl[0]
    dl.pop(0)
    if(pre[a] != -1) :
        continue
    pre[a] = b
    for i in res[a] :
        if(pre[i] != -1):
            continue
        dl.append((i,a))
        
for i in range(N) :
    if(i == 0) :
        print("Yes")
        continue
    print(pre[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
import copy
N, M = map(int, input().split())
res = [[] for i in range(N+5)]


for i in range(M) :
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    res[a].append(b)
    res[b].append(a)
    
pre = [-1] * N
d = 1
dl = []
pre[0] = 0

for i in res[0] :
    dl.append((i,0))

while(len(dl) != 0) :
    a,b = dl[0]
    dl.pop(0)
    if(pre[a] != -1) :
        continue
    pre[a] = b
    for i in res[a] :
        dl.append((i,a))
        
for i in range(N) :
    if(i == 0) :
        print("Yes")
        continue
    print(pre[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]

checked = [-1 for _ in range(N)]
checked[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(M):
        if (L[i][0] - 1 == now and checked[L[i][1]-1] == -1):
            checked[L[i][1]-1] = now + 1
            d.append(L[i][1]-1)

        if (L[i][1] - 1 == now and checked[L[i][0]-1] == -1):
            checked[L[i][0]-1] = now + 1
            d.append(L[i][0]-1)


flag = False
for i in range(1, N):
    if checked[i] == -1:
        flag = True
        break

if flag:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(checked[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]

link = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    link[L[i][0]-1][L[i][1]-1] = 1
    link[L[i][1]-1][L[i][0]-1] = 1

checked = [-1 for _ in range(N)]
ans = [-1 for _ in range(N)]
checked[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(N):
        if link[now][i] == 1 and checked[i] == -1:
            checked[i] = checked[now] + 1
            ans[i] = now + 1
            d.append(i)

flag = False
for i in range(1, N):
    if ans[i] == -1:
        flag = True
        break

if flag:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = list(map(int, input().split()))
S = set()
for _ in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    S.add((a, b))
    S.add((b, a))

parents = [-1]*N
parents[0] = 0
L = deque([0])
while L:
    k = L.pop()
    for l in S:
        if l[0] == k and parents[l[1]] < 0:
            L.appendleft(l[1])
            parents[l[1]] = k
    # print(L)

if -1 in parents:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(parents[i]+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

dist = [-1] * (N+1)
dist[1] = 0
connection = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

for quel in range(M):
    a, b = map(int, input().split())
    connection[a].append(b)
    connection[b].append(a)

que = []
que.append(1)

while que:
    v = que.pop(0)

    for i in connection[v]:
        if dist[i] != -1:continue

        dist[i] = dist[v] + 1
        que.append(i)
        ans[i] = v

#print(dist)
print('Yes')
for j in range(2, N+1):
    print(ans[j])

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy

N, M = map(int, input().split())
edges = numpy.array([list(map(int, input().split())) for _ in range(M)])

torch = [-1] * N

q = queue.Queue()
q.put(1)
torch[0] = 1

while True:
    p = q.get()

    # find the room next to p
    for i, j in zip(*numpy.where(edges == p)):
        s = edges[i, 1 - j]

        if torch[s - 1] != -1:
            continue

        torch[s - 1] = p
        q.put(s)

    if q.empty():
        break

ans = 'Yes'
if -1 in torch:
    ans = 'No'

print(ans)
for t in torch[1:]: print(t)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
A = []
B = []
route = [[False for _ in range(N)] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    route[a-1][b-1] = True
    route[b-1][a-1] = True

print('Yes')

q = deque()
d = [-1] * N
d[0] = 0
q.append(0)

while len(q) != 0:
    x = q.popleft()
    for i in range(1, N):
        if route[x][i] and d[i] == -1:
            d[i] = x + 1
            q.append(i)

for i in range(1, N):
    print(d[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
A = []
B = []
route = [[False for _ in range(N)] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    route[a-1][b-1] = True
    route[b-1][a-1] = True

print('Yes')

q = deque()
d = [-1] * N
d[0] = 0
for i in range(1, N):
    if route[0][i]:
        q.append(i)
        d[i] = 1

while len(q) != 0:
    x = q.popleft()
    for i in range(1, N):
        if route[x][i] and d[i] == -1:
            d[i] = x + 1
            q.append(i)

for i in range(1, N):
    print(d[i])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
lst = []
for i in range(m):
  x,y = map(int,input().split())
  lst.append([x,y]) 
from collections import deque
d = ['t']*n
d[0] = 0
que = deque([1])
while que:
  p = que.popleft()
  for j in range(m):
    if lst[j][0] == p:
      q = lst[j][1]
      if d[q-1] == 't':
        d[q-1] = p
        que.append(q)
    if lst[j][1] == p:
      q = lst[j][0]
      if d[q-1] == 't':
        d[q-1] = p   
        que.append(q)
print('Yes')        
for i in range(1,n):
  print(d[i])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
lst = []
for i in range(m):
  x,y = map(int,input().split())
  lst.append([x,y]) 
from collections import deque
d = ['t']*n
d[0] = 0
que = deque([1])
while que:
  p = que.popleft()
  for j in range(m):
    if lst[j][0] == p:
      q = lst[j][1]
      if d[q-1] == 't':
        d[q-1] = p
        que.append(q)
    if lst[j][1] == p:
      q = lst[j][0]
      if d[q-1] == 't':
        d[q-1] = p   
        que.append(q)
print('Yes')        
for i in range(1,n):
  print(d[i])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

neighbors = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in neighbors.keys():
    neighbors.update({a:set()})
  if b not in neighbors[a]:
    neighbors[a].add(b)
  if b not in neighbors.keys():
    neighbors.update({b:set()})
  if a not in neighbors[b]:
    neighbors[b].add(a)
#print(neighbors)
lst = [0] * (n - 1) #部屋１を除く、すべての部屋の通り方を調べる、「通っていない」を0として定義
visited = set() #一度訪れた部屋は再度探索する必要はないので、それを省くための集合
queue = [[0, set([1])]]
while queue:
  #print(queue)
  pre_room, rooms = queue.pop(0) #左が今いる部屋、右が次に進む部屋
  #print(pre_room, rooms)
  for room in rooms:
    if room in visited:
      continue
    if lst[room - 2] == 0 and room != 1: #次に進む部屋が通っていないかどうか（と今いる部屋が１ではないこと）の確認
      lst[room - 2] = pre_room #部屋2の場合、lstのindexは0に相当するので-2する必要がある
    visited.add(room) #今いる部屋を訪れたので、集合に入れる
    next_rooms = set() #次に進む部屋を探索する
    for nei in neighbors[room]:
      next_rooms.add(nei)
    next_rooms = [room, next_rooms]
    queue.append(next_rooms)
if 0 in lst:
  print('No')
else:
  print('Yes')
  for i in range(n - 1):
    print(lst[i])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

route = [tuple(map(int, input().split())) for _ in range(M)]

ans = [0]*(N+1)
que = [1]

while len(route) > 0 and len(que) > 0:
    temp = []
    del_l = []
    for i, (a, b) in enumerate(route):
        if a in que and b not in que:
            ans[b] = a
            temp.append(b)
            del_l.append(i)
        if b in que and a not in que:
            ans[a] = b
            temp.append(a)
            del_l.append(i)
    route = [r for r in route if route.index(r) not in del_l]
    que = temp

answer = ['Yes'] + ans[2:]

print(*answer, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

route = [tuple(map(int, input().split())) for _ in range(M)]

ans = [0]*(N+1)
stack = [1]
que = [1]

while len(stack) < N:
    temp = []
    for a, b in route:
        if a in que and b not in stack:
            ans[b] = a
            temp.append(b)
        elif b in que and a not in stack:
            ans[a] = b
            temp.append(a)
    que = temp
    stack += temp

answer = ['Yes'] + ans[2:]

print(*answer, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    
parent = [0]*(N+1)
parent[0] = -1
parent[1] = -1

nextroom = deque()
nextroom.append(1)
for j in range(N):
    for i in range(M):
        if A[i]==nextroom[0] and parent[B[i]]==0:
            nextroom.append(B[i])
            parent[B[i]] = A[i]
        if B[i]==nextroom[0] and parent[A[i]]==0:
            nextroom.append(A[i])
            parent[A[i]] = B[i]
    nextroom.popleft()
    
if parent.count(0)==0:
    print('Yes')
    for i in range(2,len(parent)):
        print(parent[i])
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    
parent = [0]*(N+1)
parent[0] = -1
parent[1] = -1

nextroom = [1]
for j in range(N):
    for i in range(M):
        if A[i]==nextroom[0] and parent[B[i]]==0:
            nextroom.append(B[i])
            parent[B[i]] = A[i]
        if B[i]==nextroom[0] and parent[A[i]]==0:
            nextroom.append(A[i])
            parent[A[i]] = B[i]
    nextroom.pop(0)
    
if parent.count(0)==0:
    print('Yes')
    for i in range(2,len(parent)):
        print(parent[i])
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    
parent = [0]*(N+1)
parent[0] = -1
parent[1] = -1

nextroom = [1]
for i in range(N):
    for i in range(M):
        if A[i]==nextroom[0] and parent[B[i]]==0:
            nextroom.append(B[i])
            parent[B[i]] = A[i]
        if B[i]==nextroom[0] and parent[A[i]]==0:
            nextroom.append(A[i])
            parent[A[i]] = B[i]
    nextroom.pop(0)
    
if parent.count(0)==0:
    print('Yes')
    for i in range(2,len(parent)):
        print(parent[i])
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import copy

n,m = list(map(int,input().split()))

coriddorList = [set() for i in range(n+1)]
deepList = [-1 for i in range(n+1)]


for i in range(m):
    a,b = list(map(int,input().split()))
    coriddorList[a].add(b)
    coriddorList[b].add(a)
    
room = 1

deepList[room] = 0
deepSet = {0:{room}}
deep = 1
roomList = {room}
nextRoomlist = set()
count = 1

while count > 0:
    count = 0
    for room in roomList:
        for i in coriddorList[room]:
            if deepList[i] == -1:
                deepList[i] = deep
                nextRoomlist.add(i)
                count += 1
    roomList = copy.copy(nextRoomlist)
    deep += 1

deepList[0] = 0

for i in range(n+1):
    value = deepList[i]
    if value in deepSet.keys():
        deepSet[value].add(i)
    else:
        deepSet[value] = {i}

ansList = []

for i in range(2,n+1):
    deep = deepList[i]
    lis = coriddorList[i]
    for k in deepSet[deep - 1]:
        if k in lis:
            ansList.append(k)
            break

if -1 in deepList:
    print("No")
else:
    print("Yes")
    for i in range(len(ansList)):
        print(ansList[i])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
root=[[] for _ in range(N+1)]
ans=[0]*(N+1)

print('Yes')
f=0

for _ in range(M):
    a,b=map(int,input().split())
    root[a].append(b)
    root[b].append(a)

#print(root)

lis=[1]
done=set([1])
i=0
while len(done)!=N:
    lis_=[]
    
    for li in lis:
        lis_+=root[li]
        for r in root[li]:
            if not r in done:
                ans[r]=li
            
    lis=lis_
    done=done|set(lis)
    
    #print(lis)
print('\n'.join(map(str,ans[2:])))

Submission status: Time Limit Exceeded

Solution code:
#問題文に連結と書いてあるのでどの部屋も互いに行き来できる
#自分がきたところを記録する幅優先探索をすればいい
n,m=list(map(int,input().split()))
#道を二次元リストで表す
road=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  road[a-1][b-1]=1
  road[b-1][a-1]=1
#幅優先探索
from collections import deque
q=deque([1])
ans=[0 for i in range(n)]
check=[0 for i in range(n)]
check[0]=1
while len(q)>0: 
  p=q.popleft()
  for j in range(n):
    if road[p-1][j]!=0 and check[j]==0:
      q.append(j+1)
      check[j]=1
      ans[j]=p
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
#問題文に連結と書いてあるのでどの部屋も互いに行き来できる
#自分がきたところを記録する幅優先探索をすればいい
n,m=list(map(int,input().split()))
road=[[0 for i in range(n)] for j in range(n)]
ab=[]
for i in range(m):
  a,b=list(map(int,input().split()))
  road[a-1][b-1]=1
  road[b-1][a-1]=1
from collections import deque
q=deque([1])
ans=[0 for i in range(n)]
check=[0 for i in range(n)]
check[0]=1
while len(q)>0: 
  
  p=q.popleft()
  for j in range(n):
    if road[p-1][j]!=0 and check[j]==0:
      q.append(j+1)
      road[p-1][j]=0
      road[j][p-1]=0
      check[j]=1
      ans[j]=p
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
N, M = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N+1))
for _ in range(M):
  a, b = map(int, input().split())
  G.add_edge(a, b)

dist = nx.shortest_path_length(G, target=1)
print('Yes')
for i in range(2, N+1):
  print(min((dist[j], j) for j in nx.all_neighbors(G, i))[1])

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
N, M = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N+1))
for _ in range(M):
  a, b = map(int, input().split())
  G.add_edge(a, b)

paths = nx.shortest_path(G, target=1)
print('Yes')
for i in range(2, N+1):
  print(paths[i][1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[[] for i in range(n)]
visited=[False for i in range(n)]
ans=[0]*n

for i in range(m):
      a,b=map(int,input().split())
      lst[a-1].append(b-1)
      lst[b-1].append(a-1)

Q=[0]
visited[0]=True

while Q:
  v=Q.pop(0)
  for i in lst[v]:
        if visited[i]==False:
              visited[i]=True
              ans[i]=v
              Q.append(i)

print('Yes')

for i in range(1,n):
      print(ans[i]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
root = [[] for _ in range(n)]
adj = [-1 for _ in range(n)]
for _ in range(m):
  r,c = map(int, input().split())
  root[r-1].append(c-1)
  root[c-1].append(r-1)
  
explor = [0]

while explor:
  tmp = explor.pop()
  for i in root[tmp]:
    if adj[i]==-1:
      adj[i] = tmp
      explor = [i] + explor

print('Yes')
for i in adj[1:]:
  print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
root = [[] for _ in range(n)]
adj = [-1 for _ in range(n)]
for _ in range(m):
  r,c = map(int, input().split())
  root[r-1].append(c-1)
  root[c-1].append(r-1)
  
visited = {0}
explor = [0]

while len(visited)!=n:
  tmp_explor = set()
  while explor:
    tmp = explor.pop()
    visited = visited.union(set(root[tmp]))
    for i in root[tmp]:
      if adj[i]==-1:
        adj[i] = tmp
        tmp_explor.add(i)
  explor = tmp_explor.copy()

print('Yes')
for i in adj[1:]:
  print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
root = [[] for _ in range(n)]
adj = [-1 for _ in range(n)]
for _ in range(m):
  r,c = map(int, input().split())
  root[r-1].append(c-1)
  root[c-1].append(r-1)
  
visited = {0}
explor = [0]

while len(visited)!=n:
  tmp_explor = set()
  while explor:
    tmp = explor.pop()
    tmp_explor = tmp_explor.union(set(root[tmp]))
    visited = visited.union(set(root[tmp]))
    for i in root[tmp]:
      if adj[i]==-1:
        adj[i] = tmp
  explor = tmp_explor.copy()

print('Yes')
for i in adj[1:]:
  print(i+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

pairs = [[] for _ in range(N + 1)]
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0]].append(input_list[1])
    pairs[input_list[1]].append(input_list[0])

ans = [0 for _ in range(N + 1)]
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了
done = [1] # 探索済リスト

n = 1
while n_ans < N - 1:
    for m in pairs[n]:
        if m not in done:
            done.append(m)
            ans[m] = n
            n_ans += 1
    n = m

print('Yes')
for i in range(2, N + 1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

pairs = [[0] for _ in range(N + 1)]
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0]].append(input_list[1])
    pairs[input_list[1]].append(input_list[0])

ans = [0 for _ in range(N + 1)]
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了

n = 1
while n_ans < N - 1:
    for m in pairs[n]:
        if m != 0 and m != 1:
            if ans[m] == 0:
                ans[m] = n
                n_ans += 1

    n = m

print('Yes')
for i in range(2, N + 1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int, input().split())
ab=deque()
for _ in range(m):
    ab.append(list(map(int, input().split())))

ans=deque([0]+[1]+[0]*(n-1))
tmp=deque()

tansakuheya=deque([1])

for _ in range(100009):

	for heya in tansakuheya:

		for gyou in range(m):
			if ab[gyou][0]==heya:
				if ans[ab[gyou][1]]==0:
					ans[ab[gyou][1]]=ab[gyou][0]
					tmp.append(ab[gyou][1])

			if ab[gyou][1]==heya:
				if ans[ab[gyou][0]]==0:
					ans[ab[gyou][0]]=ab[gyou][1]
					tmp.append(ab[gyou][0])
	
	if len(tmp)==0:
		break

	tansakuheya=tmp
	tmp=deque()

print("Yes")
for i in range(2,n+1):
	print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
ab=[]
for _ in range(m):
    ab.append(list(map(int, input().split())))

ans=[0]+[1]+[0]*(n-1)
tmp=[]

tansakuheya=[1]

while len(tansakuheya)>0:

	for heya in tansakuheya:

		for gyou in range(m):
			if ab[gyou][0]==heya:
				if ans[ab[gyou][1]]==0:
					ans[ab[gyou][1]]=ab[gyou][0]
					tmp.append(ab[gyou][1])

			if ab[gyou][1]==heya:
				if ans[ab[gyou][0]]==0:
					ans[ab[gyou][0]]=ab[gyou][1]
					tmp.append(ab[gyou][0])

	tansakuheya=tmp
	tmp=[]

print("Yes")
for i in range(2,n+1):
	print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
Graph = [[]for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    Graph[a].append(b)
    Graph[b].append(a)

dist = [-1] * (N + 1)
dist[0] = 0
dist[1] = 0

d = deque()
d.append(1)
while d:
    v = d.popleft()
    for i in Graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)

ans = dist[0:]
C = [0] * (N + 1)
for j in range(2, len(ans)):
    if ans[j] == 1:
        C[j] = 1
    for k in range(2, max(ans) +1):
        if ans[j] == k:
            index_num = [n for n, v in enumerate(ans) if v == k - 1]
            for l in index_num:
                if l in Graph[j]:
                    C[j] = l
                    break
print('Yes')
for m in range(2,N + 1):
    print(C[m])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

neighbors = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in neighbors.keys():
    neighbors.update({a:[]})
  if b not in neighbors[a]:
    neighbors[a].append(b)
  if b not in neighbors.keys():
    neighbors.update({b:[]})
  if a not in neighbors[b]:
    neighbors[b].append(a)
#print(neighbors)
lst = [0] * (n - 1)
visited = set()
queue = [[0, [1]]]
while queue:
  #print(queue)
  pre, next_rooms = queue.pop(0)
  #print(pre, next_rooms)
  for next_room in next_rooms:
    if next_room in visited:
      continue
    if lst[next_room - 2] == 0 and next_room != 1:
      lst[next_room - 2] = pre
    visited.add(next_room)
    rooms = []
    for nei in neighbors[next_room]:
      rooms.append(nei)
    rooms = [next_room, rooms]
    queue.append(rooms)
if 0 in lst:
  print('No')
else:
  print('Yes')
  for i in range(n - 1):
    print(lst[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())

G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

ls = deque([[0, 0]])
ans = [-1] * N
depthes = [float("inf")] * N 
ans[0] = 0
depthes[0] = 0
while len(ls) > 0:
    v, depth = ls.pop()

    for next_v in G[v]:
        if depthes[next_v] <= depth+1:
            continue
        ans[next_v] = v
        depthes[next_v] = depth + 1
        ls.append([next_v, depth+1])

if -1 in ans:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())

G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

ls = deque([[0, 0]])
ans = [-1] * N
depthes = [float("inf")] * N 
ans[0] = 0
depthes[0] = 0
while len(ls) > 0:
    v, depth = ls.pop()

    for next_v in G[v]:
        if depthes[next_v] < depth+1:
            continue
        ans[next_v] = v
        depthes[next_v] = depth + 1
        ls.append([next_v, depth+1])

if -1 in ans:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i]+1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

que = deque()
dist = [float('inf')] * n
prev = [-1] * n
dist[0] = 0
que.append(0)
while que:
    now = que.pop()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            prev[edge] = now + 1
            que.append(edge)


print('Yes')
for i in range(1, n):
    print(prev[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

que = deque()
dist = [float('inf')] * n
dist[0] = 0
que.append(0)
while que:
    now = que.pop()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            que.append(edge)

# print(dist)
arrow = [0] * n
for i, j in enumerate(dist):
    if i == 0:
        continue
    idxs = []
    for idx in range(n):
        if dist[idx] == j - 1:
            idxs.append(idx)
    for edge in edges[i]:
        if edge in idxs:
            arrow[i] = edge + 1
            break
    if arrow[i] == 0:
        print('No')
        sys.exit()

print('Yes')
for i in range(1, n):
    print(arrow[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

que = deque()
dist = [float('inf')] * n
dist[0] = 0
que.append(0)
while que:
    now = que.pop()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            que.append(edge)

# print(dist)
arrow = [0] * n
for i, j in enumerate(dist):
    if i == 0:
        continue
    idxs = []
    for idx in range(n):
        if dist[idx] == j - 1:
            idxs.append(idx)
    for edge in edges[i]:
        if edge in idxs:
            flg = True
            arrow[i] = edge + 1
    if arrow[i] == 0:
        print('No')
        sys.exit()

print('Yes')
for i in range(1, n):
    print(arrow[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())

G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def dfs(v, u, depth):

    depth_min[v] = depth
    memo[v] = u

    for next_v in G[v]:
        if next_v == 0:
            continue
        if depth_min[next_v] > depth+1:
            dfs(next_v, v, depth+1)

depth_min = [float("inf")] * N
memo = [-1] * N
dfs(0, 0, 0)
if -1 in memo:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(memo[i]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[] for _ in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a].append(b)
    way[b].append(a)

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])