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: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

G = [[] for _ in range(N+1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

parents = [0] * (N+1)
visited = [0] * (N+1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        parents[w] = v
        q.append(w)

print('Yes')
print(*parents[2:], sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()] 
g = [[] for _ in range(n)] 

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0
    pre = [-1] * n
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                pre[i] = v + 1 
                
    return pre

d = bfs(0)
if all([i != None for i in d]):
    print("Yes")
    for i in range(1,n):
        print(d[i])
else:
    print("No")

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int,input().split())

p = [0 for i in range(n+1)]
q = list()
q2 = list()

g=[[] for i in range(n+1)]

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


q2.append(1)

while 1:
    q=q2
    q2=[]

    while len(q):
        v = q.pop()
        
        for nv in g[v]:
            if p[nv] == 0:
                p[nv]=v
                g[nv].remove(v)
                q2.append(nv)
    if len(q2)==0:
        break

if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)

Submission status: Accepted

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

ds = [float('inf')]*(N+1)
ds[1] = 0
h = deque()
h.append(1)
 
while(len(h) > 0):
  v = h.popleft()
  for j in nl[v]:
    if ds[j] == float('inf'):
      ds[j] = ds[v] + 1
      rlt[j] = v
      h.append(j)

if -1 in rlt[2:]:
  print('No')
else:
  print('Yes')
  for i in rlt[2:]:
    print(i)

Submission status: Accepted

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)

ans = [0] * (N+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[i] = v

print("Yes")
print(*ans[2:], sep='\n')

Submission status: Accepted

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

room = [-1]*n
seen = [-1]*n
import queue
q = queue.Queue()
q.put(0)
while not q.empty():
    x = q.get()
    
    seen[x] =  -2
    for i in g[x]:
        if room[i] == -1:
            room[i] = x
            
        if seen[i] == -1:
            q.put(i)
            seen[i] = -2
        
print('Yes')
for i in range(1,n):
    print(room[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, M, *AB = map(int, open(0).read().split())
    C = {}
    for i in range(M):
        a = AB[2 * i + 0] - 1
        b = AB[2 * i + 1] - 1
        if a not in C:
            C[a] = []
        C[a].append(b)
        if b not in C:
            C[b] = []
        C[b].append(a)
    ANS = {i:-1 for i in range(N)}
    D = deque()
    D.append((0, C[0]))
    # print(D)
    while len(D) != 0:
        d = D.popleft()
        v = d[0]
        L = d[1]
        for l in L:
            if ANS[l] == -1:
                ANS[l] = v
                D.append((l, C[l]))
    print('Yes')
    for i in range(1, N):
        print(ANS[i] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import networkx as nx

N,M = map(int,input().split())
G = nx.Graph()
for i in range(M):
    A,B = map(int,input().split())
    G.add_edge(A,B)
print("Yes")
pre = nx.predecessor(G,1)
for i in range(2,N+1):
    print(pre[i][0])

Submission status: Accepted

Solution code:
from networkx import Graph,predecessor

G = Graph() #無効グラフ生成
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
G.add_edges_from(ab) #辺リスト生成
preds = predecessor(G,source=1)  #sourceはstart node
print("Yes")
for i in range(2,n+1):
    print(preds[i][0])

#描画
#import matplotlib.pyplot as plt
#import networkx as nx
#nx.draw_networkx(G)
#plt.show()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
#bfsで探索
T = [-1]*N
que = deque()
que.append(0)
while que:
    v = que.popleft()
    for e in G[v]:
        if T[e] == -1:
            T[e] = v+1
            que.append(e)
print("Yes")
print(*T[1:], sep="\n")

Submission status: Accepted

Solution code:
import queue
def readInt():
    return list(map(int, input().split()))

N, M = readInt()

graph = [[] for i in range(N)] #部屋がどことつながっているかを入れるリスト 
v = [-1 for i in range(N)] #部屋を探索したことがなければ-1
v[0] = [0]

for i in range(M):
    x, y = readInt()
    graph[x-1].append(y-1) #graph[0]は部屋1
    graph[y-1].append(x-1)


q = queue.Queue()
q.put(0)

while not q.empty():
    n = q.get()
   
    for j in graph[n]:
        if v[j]!=(-1):
            continue
        q.put(j)
        v[j] = n
        
print("Yes")
for i in range(1, N):
    print(v[i] + 1)

Submission status: Accepted

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)

ans = [0] * (n+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[i] = v
print('Yes')
print(*ans[2:], sep='\n')

Submission status: Accepted

Solution code:
def main():
    input1 = input()
    input1 = input1.split()
    N = int(input1[0])
    M = int(input1[1])

    aisle = {}
    result = [0]*(N-1)
    record = [1]
    count = N-1
    in1 = 0
    in2 = 0

    for i in range(M):
        input2 = input()
        input2 = input2.split()
        in1 = int(input2[0])
        in2 = int(input2[1])
        aisle.setdefault(in1,[]).append(in2)
        aisle.setdefault(in2,[]).append(in1)

    while count != 0 and len(record) != 0:
        pop1 = record.pop(0)
        if pop1 in aisle:
            for i in aisle[pop1]:
                if result[i-2] == 0 and i >= 2:
                    result[i-2] = pop1
                    record.append(i)
                    count = count -1

    if count == 0:
        print("Yes")
        for i in range(len(result)):
            print(result[i])
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(N + 1)]

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

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


d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if prev[i] == -1:
            prev[i] = v
            d.append(i)

prev.pop(0)
prev.pop(0)
if len(prev) > 0:
    print("Yes")
    for y in prev:
        print(y)
else:
    print("No")

Submission status: Accepted

Solution code:

def main():
    n, m = map(int, input().split())
    ab = (map(int, input().split()) for _ in range(m))

    # 死因 graph = [[0] * (n+1) for _ in range(n+1)]
    graph = [[] for _ in range(n+1)]

    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    from collections import deque

    q = deque()
    q.append(1)

    p = [0] * (n+1)

    while q:
        a = q.popleft()
        for b in graph[a]:
            if not p[b]:
                p[b] = a
                q.append(b)

    result = p[2:]

    is_yes = all(result)

    print('Yes' if is_yes else 'No')

    if is_yes:
        for r in result:
            print(r)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
import itertools
N, M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

loads = [[] for _ in range(N+1)]

for AB in ABs:
    loads[AB[0]].append(AB[1])
    loads[AB[1]].append(AB[0])


dq = collections.deque()

dq.append(1)
ans_list = [0 for _ in range(N+1)]

#print(loads)
print("Yes")
while len(dq) != 0:
    i = dq.popleft()

    for vec in loads[i]:
#        print(vec)
        if(ans_list[vec] == 0):
            ans_list[vec] = i
            dq.append(vec)
#        print(ans_list)
#        print(dq)


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

Submission status: Accepted

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

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist=[float("inf")]*size_v
  used=[False]*size_v
  prev=[-1]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    prev[min_v]=u
    for v,w in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

ablist=[]
graph=[[] for _ in range(N+1)]
for _ in range(M):
  a,b=map(int,input().split())
  graph[a].append((b,1))
  graph[b].append((a,1))
  ablist.append((a,b))
#print(graph)

size_v=N+1
dist,prev=dijkstra_heap(1)
#print(dist)
#print(prev)

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

Submission status: Accepted

Solution code:
from networkx import Graph,predecessor
G = Graph()

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

G.add_edges_from(rows)

preds = predecessor(G,source=1)

if len(preds) != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i][0])

Submission status: Accepted

Solution code:
from collections import deque
N,M = list(map(int,input().split()))
map1 = [[] for i in range(N+1)]

sirusi = [0]*(N+1)

for i in range(M):
    a,b = list(map(int,input().split()))
    
    map1[a].append(b)
    map1[b].append(a)
    
d = deque([1]+map1[1])
visited = [0]*(N+1)
visited[1] = 1
# print(map1)
while d:
    D = d.popleft()
    for i in map1[D]:
        if visited[i] == 1:
            continue
        visited[i] = 1
        d.append(i)
        sirusi[i] = D
        
print("Yes")
for i in range(2,N+1):
    print(sirusi[i])

Submission status: Accepted

Solution code:
from collections import deque 

n, m = map(int, input().split())
to = [[] for _ in range(n+1)]

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

q = deque([1])
ans = [0]*(n+1)
while q:
    p = q.popleft()
    for i in to[p]:
        if ans[i]==0:
            ans[i]=p
            q.append(i)
print('Yes')
print(*ans[2:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int,input().split())
graph = [[] for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a) #双方向

visited = [False]*N
visited[0] = True
ans = [0]*N
D = deque([0])
while D:
    v = D.popleft()
    for i in graph[v]:
        if visited[i]:
            continue
        visited[i] = True #一度通ったことを伝える
        ans[i] = v+1
        D.append(i)

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

Submission status: Accepted

Solution code:
# ノードの開始が'0'でなく'1'であることに注意!!※※※
# AtCoder Beginner Contest 168
# https://atcoder.jp/contests/abc168/tasks/abc168_d

import sys
input = sys.stdin.readline

n, m =  map(int, input().split()) # nは頂点の数、mは辺の数
pic = [[] for _ in range(n)] # 隣接リスト_初期化

for _ in range(m): # 隣接リスト_取り込み
    a, b = map(int, input().split())
    pic[a-1].append(b-1) # ※※※
    pic[b-1].append(a-1) # ※※※

from collections import deque

def BFS(u): # 'u'を開始位置として各頂点までの距離を探索する関数_dis → 探索元ノードを探索_ans
    queue = deque([u]) # dequeオブジェクトとして初期化、初期値は開始位置の'u'のみ
    dis = [None] * n # uからの距離を全ノード分初期化
    dis[u] = 0 # 自分'u'との距離は0
    ans = [-1] * n # 探索元のノードを格納する
    while queue:
        v = queue.popleft() # v:探索元のノード 
        for i in pic[v]: # pic[v]: 探索元のノードに隣接するノードのリスト
            if ans[i] == -1:
                ans[i] = v
            if dis[i] is None:
                dis[i] = dis[v] + 1
                queue.append(i)
    return ans

tmp = BFS(0) # ここは'1'でなく'0'※※※
print('Yes')
for j in tmp[1:]:
    print(j+1) # ※※※

Submission status: Accepted

Solution code:
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更新
				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)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    INF = float('inf')

    N, M = (int(x) for x in input().split())
    root = [[] for _ in range(N+1)]
    for i in range(M):
        A,B = (int(x) for x in input().split())
        root[A].append(B)
        root[B].append(A)
    dist = [INF] * (N+1)
    dist[1] = 0
    q = deque([1])

    while q:
        v = q.popleft()
        for r in root[v]:
            if dist[r] == INF:
                dist[r] = v
                q.append(r)
    print('Yes')
    for d in dist[2:]:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
 
n,m = map(int,input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
path = [[] for _ in range(n+1)]
 
for a,b in ab:
    path[a].append(b)
    path[b].append(a)
 
q = deque([1])
ans = [0] * (n+1)
while q:
    v = q.popleft()
    for w in path[v]:
        if ans[w] == 0:
            ans[w] = v
            q.append(w)
 
print('Yes')
print(*ans[2:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

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

res = {}
for i in range(m):
    a,b = map(int,input().split())
    res.setdefault(a,[]).append(b)
    res.setdefault(b,[]).append(a)

dist =[0] * (n+1)
sirusi = [0] * (n+1)
dist[1] = -1

que = deque([])
ique = deque([])
x = res.pop(1)
#print(x)
que.append(x)
ique.append(1)

d = 1
#print(len(que))

while(len(que)>0):
    data = que.popleft()
    index = ique.popleft()
    #print(data)
    ind = 0
    for i in data:
        #print(int(i))

        if dist[int(i)] == 0 :
            # print("d")
            # print(index)
            dist[i] = d
            sirusi[i] = index
            que.append(res.pop(i))
            ique.append(int(i))
        ind += 1
    d = d + 1
#
# while(len(next) > 0):
#     data = next.pop()
#     print("data = ",end="")
#     print(data)
#     if(not(type(data) is int)):
#         print("not int")
#         for i in range(len(data)):
#             if dist[i]  != 0:
#                 dist[data[i]] = d
#                 print("res[data[i]] = ")
#                 #print(res[data[i]])
#                 next.append(res.pop(data[i]))
#     else:
#         print("int")
#         if dist[data] == 0:
#             dist[data] = d
#             print("res = ",end="")
#             print(res[data])
#             next.append(res[data])
#
#     d = d +1



#print(dist)
#print(sirusi)
print("Yes")
for i in range(2,len(sirusi)):
    print(sirusi[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

(n, m) = map(int, raw_input().split())

d = defaultdict(list)

for i in xrange(m):
    (a, b) = map(int, raw_input().split())
    d[a].append(b)
    d[b].append(a)

pre = [0 for i in xrange(n + 1)]
cnt = 0

q = deque([1])
while q:
    cur = q.popleft()
    for nxt in d[cur]:
        if pre[nxt] == 0:
            cnt += 1
            pre[nxt] = cur
            q.append(nxt)


if cnt < n - 1:
    print 'No'
else:
    print 'Yes'
    for i in xrange(2, n + 1):
        print pre[i]

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
path = [[] for _ in range(n+1)]

for a,b in ab:
    path[a].append(b)
    path[b].append(a)

q = deque([1])
ans = [0] * (n+1)
while q:
    v = q.popleft()
    for w in path[v]:
        if ans[w] == 0:
            ans[w] = v
            q.append(w)

print('Yes')
print(*ans[2:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
L = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)

# 幅優先探索
d = deque([0])
D = [-1] * n
D[0] = 0
while len(d) > 0 :
    t = d.popleft()
    for i in L[t]:
        if D[i] == -1:
            D[i] = t
            d.append(i)
            # print(d, D)

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

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def bfs(graph: list, n: int, start: int, ans: list):
    q = deque([start])
    visited = [INF] * n
    visited[0] = 1
    while len(q) != 0:
        node = q.popleft()
        for leaf in graph[node]:
            if visited[leaf] != INF:
                continue
            ans[leaf] = node + 1
            visited[leaf] = 1
            q.append(leaf)

def create_graph(n: int, l: list) -> list:
    graph = [[] for _ in range(n)]
    for a, b in l:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    return graph

def main():
    n, m = i_map()
    num_list = i_row_list(m)

    graph = create_graph(n, num_list)

    ans = [0] * n

    bfs(graph, n, 0, ans)

    Yes()
    for a in ans[1:]:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()

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

G.add_edges_from(rows)

preds = dict(bfs_predecessors(G,source=1))

if len(preds)+1 != N:
    print("No")
    exit()

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
ways = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  ways[a].append(b)
  ways[b].append(a)
searched = [0 for i in range(N)]
searched[0] = 1
ans = [0 for i in range(N)]
d = deque([])
d.append(0)
while d:
  tmp = d.popleft()
  for w in ways[tmp]:
    if searched[w] == 0:
      searched[w] = 1
      ans[w] = tmp
      d.append(w)
print("Yes")
for a in ans[1:]:
  print(a + 1)

Submission status: Accepted

Solution code:
# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

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

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

# def bfs(si, sj, str_list, dist, h, w):
#     q = deque([[si, sj]])
#     dist[si][sj] = 0
#     max_tmp = 0
#     while len(q) != 0:
#         i, j = q.popleft()
#         for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
#             ni = i + dx
#             nj = j + dy
#             if ni < 0 or ni >= h or nj < 0 or nj >= w:
#                 continue
#             if str_list[ni][0][nj] != '.':
#                 continue
#             if dist[ni][nj] != inf:
#                 continue
#             dist[ni][nj] = dist[i][j] + 1
#             q.append([ni, nj])
#             max_tmp = max(max_tmp, dist[ni][nj])
#     return max_tmp

def create_graph(n: int, l: list) -> list:
    graph = [[] for _ in range(n)]
    for a, b in l:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    return graph

def main():
    n, m = i_map()
    num_list = i_row_list(m)

    graph = create_graph(n, num_list)

    q = deque([0])

    visited = [INF] * n
    visited[0] = 1

    ans = [0] * n

    while len(q) != 0:
        node = q.popleft()
        for leaf in graph[node]:
            if visited[leaf] != INF:
                continue
            ans[leaf] = node + 1
            visited[leaf] = 1
            q.append(leaf)

    Yes()
    for a in ans[1:]:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os

if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

f = lambda:list(map(int,input().split()))

def get_qsa(file_name):
    audio, size = readfile(file_name)
    headers = {
        'Connection': 'keep-alive',
        'Content-Length': str(size)
    }

    
    parameter = {
                "request_id":int(time.time()*100),
                "th":1,
                "tht":"qf492_100fps",
                "the":1.000000,
                "thst":"neural"
                }
    res = requests.post(f"http://{config['ip']}:{config['port']}", timeout=120, data=audio, headers=headers, params = parameter)
    # print(res.url)

    res_json = res.json()
    # print(res_json.keys())


    if res_json['retmsg']!="success":
        raise Exception
    

    bin_str = res_json["th"][0]["feat"]
    bin_data = base64.b64decode(bin_str)

    bin2qsa_siren(bin_data, file_name)


def solve():
    n,m = f()
    g= []
    for _ in range(n):
        g.append([])

    for _ in range(m):
        a,b = f()
        g[a-1].append(b-1)
        g[b-1].append(a-1)

    import queue
    q = queue.Queue()
    q.put(0)
    vis = set()
    vis.add(0)
    d = {}
    d[0] = 0

    ans = {}
    while not q.empty():
        u = q.get()
        for v in g[u]:
            if v in vis:
                continue
            vis.add(v)
            d[v] = d[u] + 1
            ans[v] = u
            q.put(v)

    ok = 1
    for i in range(1, n):
        if i not in vis:
            ok = 0
    
    if ok == 0:
        print("No")
    else:
        print("Yes")
        for i in range(1, n):
            print(ans[i]+1)



       
    
solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].append(B)
    graph[B].append(A)

from collections import deque

dist = [-1] * N
prev = [-1] * N
dist[0] = 0
queue = deque([0])
while queue:
    tmp = queue.popleft()
    for i in graph[tmp]:
        if dist[i] != -1:
            continue
        dist[i] = dist[tmp] + 1
        prev[i] = tmp
        queue.append(i)


print("Yes")
for i in prev[1:]:
    print(i+1)

Submission status: Accepted

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

node = [[] for i in range(n)]
for i in range(m):
    node[ab[i][0] - 1].append(ab[i][1])
    node[ab[i][1] - 1].append(ab[i][0])

# print(node)
node_dic = [[] for i in range(n)]
now = [1]
while True:
    # print('now:{}'.format(now))
    flag = True
    next_node = []
    for i in range(len(now)):
        next_node_element = node[now[i] - 1]
        
        for j in range(len(next_node_element)):
            if not node_dic[next_node_element[j] - 1]:
                next_node.append(next_node_element[j])
                node_dic[next_node_element[j] - 1].append(now[i])
                flag = False
    # next_node = sum(next_node, [])
    # print('next_node: {}'.format(next_node))
    # print(node_dic)
    # print('next_node:{}'.format(next_node))
    now = []
    now = next_node
    if flag:
        break

for i in range(n):
    if i == 0:
        print('Yes')
        continue
    print(node_dic[i][0])