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
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from collections import deque

def main():
    n, m = list(map(int, input().strip().split()))
    G = [[] for i in range(n)]
    for i in range(m):
        a, b = list(map(int, input().strip().split()))
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = deque()
    q.append((0, -1))
    visited = [False] * (n)
    shirube = [-1] * n
    visited[0] = True
    while len(q) != 0:
        src, prev = q.popleft()
        # print(src, prev)
        shirube[src] = prev
        for node in G[src]:
            if not visited[node]:
                visited[node] = True
                q.append((node, src))
    # print(G)
    print('Yes')
    for i in range(1, n):
        print(shirube[i]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
q=queue.Queue()
n,m=map(int,input().split())
room=[]
singpost=[0]*(n+1)

for i in range(n+1):
    room.append([])

for _ in range(m):
    r1,r2=map(int,input().split())
    if r1==1 :
        singpost[r2]=1
        q.put(r2)
    elif r2==1:
        singpost[r1]=1
        q.put(r1)
    else:
        room[r1].append(r2)
        room[r2].append(r1)

while not(q.empty()):
    loca=q.get()
    for x in room[loca]:
        if singpost[x]==0:
            singpost[x]=loca
            q.put(x)

if singpost.count(0)>2:print("No")
else:
    print("Yes")
    for x in range(2,n+1):
        print(singpost[x])

Submission status: Accepted

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

while len(q):
    now = q.pop(0)
    for i in room[now]:
        if mark[i] == -1:
            mark[i] = now
            q.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque
import queue
N,M = list(map(int,input().split()))
linked_list ={i:[] for i in range(1,N+1)}
A_list = []
B_list = []
depths = [-1 for _ in range(N)]
depths[0] = 0
for m in range(M):

    A, B = list(map(int,input().split()))
    linked_list[A].append(B)
    linked_list[B].append(A)

    # A_list.append(A)
    # B_list.append(B)
node = []
simbols =[]
q = deque()
q.append(1)
while len(q) >0:
    node_no  = q.popleft()
    for i in linked_list[node_no]:
        if depths[i-1] != -1:
            continue

        q.append(i)
        depths[i-1]=node_no

        # print(f"node_no is {node_no} target is {i}")
        # print(depths)

if -1 in  depths:
    print("No")
else:
    print("Yes")
    for i in depths[1:]:
        print(i)

mod = 998244353
INF = 1 << 29
lINF = 1 << 35


def readInt():
    return list(map(int, input().split()))


# def main():
#     n, m = readInt()
#     # インデックスを部屋番号として、各部屋から繋がっている部屋の番号をリストに持つ
#     graph = [[] for i in range(n)]
#     for i in range(m):
#         x, y = readInt()
#         graph[x - 1].append(y - 1)
#         graph[y - 1].append(x - 1)
#     # 各部屋に設定する番号を記録する
#     v = [-1 for i in range(n)]
#     # 部屋1は -1 以外にしておく
#     v[0] = [0]
#     # queueを作成し部屋1（インデックスは0）を入れる
#     q = queue.Queue()
#     q.put(0)
#     while not q.empty():
#         # queueの先頭（今いる部屋の番号）を取り出す
#         x = q.get()
#         # 今いる部屋と繋がっている部屋を順に探索する
#         for y in graph[x]:
#             # -1ではない場合は既に探索済みなのでスキップする
#             if v[y] != (-1):
#                 continue
#             # あとで探索する為にqueueに入れておく
#             q.put(y)
#             print(f"node_no is {x} target is {y}")
#             v[y] = x
#             print(v)
#     print("Yes")
#     for i in range(1, n):
#         print(v[i] + 1)
#     return
#
#
# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

q = deque()
q.append(1)
l = [-1]*(n + 1)
l[1] = 0

while q:
    v = q.popleft()
    for i in paths[v]:
        if l[i] == -1:
            l[i] = v
            q.append(i)

print("Yes")

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
goto=[[] for i in range(N+1)]
for i in range(M):
    goto[AB[i][0]].append(AB[i][1])
    goto[AB[i][1]].append(AB[i][0])
#print(goto)

parent=[0 for i in range(N+1)]
done=[0 for i in range(N+1)]
done[1]=1

from collections import deque
q=deque([1])

while q:
    r=q.popleft()
    for t in goto[r]:
        if done[t]:
            continue
        parent[t]=r
        done[t]=1
        q.append(t)

#print(parent)

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

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
n,m = ma()
import collections
que = collections.deque()
ls = [[] for i in range(n)]
for i in range(m):
    a,b = ma()
    ls[a-1].append(b-1)
    ls[b-1].append(a-1)
que.append((0,-1))
vis = [False]*n
ans = [0]*n
while que:
    now,prev = que.popleft()
    if not vis[now]:##同じ床をなんども訪れる予定がある
        vis[now] = True
        ans [now] = prev
        for nex in ls[now]:
            if not vis[nex]:
                que.append((nex,now))
print("Yes")
for i in range(1,n):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    status[s] = VISITING
    signs[s] = 0
    Q.append(s)
    while len(Q) > 0:
        u = Q.popleft()
        for v in rooms[u]:
            if status[v] == NOT_VISITED:
                status[v] = VISITING
                signs[v] = u
                Q.append(v)
        status[u] = VISITED


def bfs_opt(s):
    signs[s] = 0
    Q.append(s)
    while len(Q) > 0:
        u = Q.popleft()
        for v in rooms[u]:
            if signs[v] == INFTY:
                signs[v] = u
                Q.append(v)


n, m = map(int, input().split())
rooms = [[] for i in range(n)]

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

INFTY = float('inf')
signs = [INFTY] * n

# status を保持しなくても、signs == INFTY (== 未訪問) で訪問済みかどうかの判定は可能
# for bfs()
# NOT_VISITED = 0
# VISITING = 1
# VISITED = 2
# status = [NOT_VISITED] * n

Q = deque()

bfs_opt(0)

# ok = True
# for sign in signs:
#     if sign == INFTY:
#         ok = False

# ok にならない (No になる) ケースは存在しない
print('Yes')
signs = signs[1:]
for sign in signs:
    print(sign + 1)

Submission status: Accepted

Solution code:
from collections import deque
#幅優先探索
def bfs(adj, sign):
  queue = deque([0])
  sign[0] = 0
  while queue:
    x = queue.popleft()
    for y in adj[x]:
      if sign[y] == -1:
        sign[y] = x
        queue.append(y)

if __name__ == "__main__":
  n, m = map(int, input().split())
  adj = [set() for _ in range(n)]
  for _ in range(m):
    a, b = map(int, input().split())
    adj[a-1].add(b-1)
    adj[b-1].add(a-1)
  sign = [-1]*n
  bfs(adj, sign)
  if all([x != -1 for x in sign]):
    print("Yes")
    for x in sign[1:]:
      print(x+1)
  else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

tree=[[0] for _ in range(N)]

for _ in range(M):
    A,B=map(int,input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)

dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        dist[w] = v
        que.append(w)

print("Yes")
for j in range(1,N):
    print(dist[j]+1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
d = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    #a,b = a-1,b-1
    d[a].append(b)
    d[b].append(a)
#print(d)  
from collections import deque
q = deque([1])
visited = [False]*(n+1)
visited[1] = True
signpost = [False]*(n+1)

while q:
    k = q.popleft()
    for j in d[k]:
        if visited[j] != False:
            continue
        visited[j] = True
        signpost[j] = k
        q.append(j)
#print(visited,signpost)
if signpost[2:]:
    print("Yes")
for i in range(2,n+1):
    print(signpost[i])

Submission status: Accepted

Solution code:
from collections import namedtuple, deque

P = namedtuple('P', 'id prev')

N, M  = map(int, input().split())
G = [[] for _ in range(N + 1)]

for _ in range(M):
  a, b = map(int, input().split())
  G[a].append(b)
  G[b].append(a)
  
# 履歴（最初に訪問した訪問元の番号が入る）  
visited = [None] * (N + 1)
  
q = deque([P(1, None)])
  
while q:
  p = q.popleft()
  if visited[p.id] is not None:
    continue
    
  visited[p.id] = p.prev
  
  for e in G[p.id]:
    if visited[e] is not None:
      continue
    q.append(P(e, p.id))
  
print('Yes')  # 常にYes?  

for i in range(2, N + 1):
  print(visited[i])

Submission status: Accepted

Solution code:
(n,m),*e=[[*map(int,t.split())]for t in open(0)]
t=[[]for _ in range(n+1)]
for a,b in e:t[a]+=[b];t[b]+=[a]
q=[1]
a=[0]*-~n
while q:q=[a[j]==0and(a.__setitem__(j,i)or j)for i in q for j in t[i]]
print('Yes',*a[2:])

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
S=[[] for _ in range(N)]
#隣接リスト生成
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    S[a].append(b)
    S[b].append(a)
q=deque()
dist=[-1]*N
dist[0]=0
q.append(0)
while q:
    now=q.popleft()
    for j in S[now]:
        if dist[j] != -1:continue 
        dist[j]=now+1
        q.append(j)
print('Yes')
[print(dist[i]) for i in range(1,N)]

Submission status: Accepted

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_edges_from(s)
di=nx.predecessor(g,source=1)

print("Yes")
for x in range(2,n+1):
    print(di[x][0])

Submission status: Accepted

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_edges_from(s)

print("Yes")
for x in sorted(nx.bfs_predecessors(g,1)):
    print(x[1])

Submission status: Accepted

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

# D - .. (Double Dots)
from collections import deque
sys.setrecursionlimit(pow(10, 6))

def set_route(start, goal):
	global routes
	
	routes[goal].append(start)


def search(que):
	global routes
	global guides

	if len(que) > 0:
		goal = que.popleft()

		for start in routes[goal]:
			if guides[start] == 0:
				guides[start] = goal
				que.append(start)
		
		search(que)
	else:
		return 


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

# 空の辞書(routes)を作成
for i in range(1, n + 1):
	routes[i] = []

# すべての出入り口の情報を取得("routes"に保存)
for i in range(m):
	a, b = map(int, input().split())
	set_route(a, b)
	set_route(b, a)

# 道しるべ(最後に出力)を保存するためのリスト
guides = [0] * (n + 1)

que = deque()
que.append(1)
search(que)

ans = guides[2:]

if 0 in ans:
	print('No')
else:
	print('Yes')
	
	for a in ans:
		print(a)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
par = [0] * (n+1)

for _ in range(m):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

visited = [0] + [1] + [0] * (n-1)
q = deque()
q.append(1)
while q:
    now = q.popleft()
    #print("now:", now)
    visited[now] = 1
    for next in G[now]:
        #print("next:", next)
        #print("visited:", visited)
        if visited[next]:
            continue
        q.append(next)
        par[next] = now
        visited[next] = 1
print("Yes")
print("\n".join(map(str, par[2:])))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = []
B = []
pt = [[] for i in range(N)]
for i in range(M):
	a, b =  map(int, input().split())
	a -=1
	b -=1
	pt[a].append(b)
	pt[b].append(a)
n=N
res_list = [-1] * N
def bfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
                    res_list[j]=i
        q=q1
        c+=1
    return d
res = bfs(0)

no = 'No'
yes ='Yes'
if -1 in res:
	print(no)
else:
	print(yes)
	
for i,x in enumerate(res_list):
	if i==0:
		continue
	print(x+1)

Submission status: Accepted

Solution code:
# import queue
from collections import deque
import sys

readline = sys.stdin.readline


def main():
    n_rooms, n_passages = map(int, input().split())
    passages = (map(int, readline().strip().split()) for _ in range(n_passages))

    connections = [set() for _ in range(n_rooms+1)]  # type: list
    for a, b in passages:
        connections[a].add(b)
        connections[b].add(a)

    que = deque()
    que.append((0, 1))  # parent, current

    signs = [-1] * (n_rooms + 1)

    while que:
        parent, current = que.popleft()

        if signs[current] != -1:
            continue

        signs[current] = parent

        for room in connections[current]:
            if signs[room] == -1:
                que.append((current, room))

    print('Yes')
    for sign in signs[2:]:
        print(sign)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue
import sys

readline = sys.stdin.readline


def main():
    n_rooms, n_passages = map(int, input().split())
    passages = (map(int, readline().strip().split()) for _ in range(n_passages))

    # n_rooms, n_passages, *passages = map(int, open(0).read().split())

    connections = [set() for _ in range(n_rooms+1)]  # type: list
    for a, b in passages:
        connections[a].add(b)
        connections[b].add(a)

    que = queue.Queue()
    que.put((0, 1))  # parent, current

    signs = [-1] * (n_rooms + 1)

    while not que.empty():
        parent, current = que.get()

        if signs[current] != -1:
            continue

        signs[current] = parent

        for room in connections[current]:
            if signs[room] == -1:
                que.put((current, room))

    print('Yes')
    print('\n'.join(map(str, signs[2:])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue
import sys

readline = sys.stdin.readline


def main():
    n_rooms, n_passages = map(int, input().split())
    passages = (map(int, readline().strip().split()) for _ in range(n_passages))

    connections = [set() for _ in range(n_rooms+1)]  # type: list
    for a, b in passages:
        connections[a].add(b)
        connections[b].add(a)

    que = queue.Queue()
    que.put((0, 1))  # parent, current

    signs = [-1] * (n_rooms + 1)

    while not que.empty():
        parent, current = que.get()

        if signs[current] != -1:
            continue

        signs[current] = parent

        for room in connections[current]:
            if signs[room] == -1:
                que.put((current, room))

    print('Yes')
    for sign in signs[2:]:
        print(sign)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

adj = [[] for _ in range(n)]

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

from collections import deque
q = deque()

dist = [-1]*n
ans = [0]*n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] += 1
        q.append(to)
        ans[to] = now 
    
print("Yes")
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Accepted

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

adj = [[] for _ in range(n)]

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

from collections import deque
q = deque()

dist = [-1] * n
ans = [0] * n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now 
    
print("Yes")
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Accepted

Solution code:
n, m = map(int ,input().split())
 
adj = [[] for _ in range(n)]
 
for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    adj[a].append(b)
    adj[b].append(a)
 
from collections import deque
q = deque()
 
dist = [-1] * n
ans = [0] * n
 
q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now
 
print("Yes")
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N, M = map(int, input().split())
    d = [-1 for i in range(N)]
    par = [-1 for i in range(N)]
    adj = [list() for i in range(N)]

    for i in range(M):
        A, B = map(int, input().split())
        adj[A-1].append(B-1)
        adj[B-1].append(A-1)

    dq = deque()
    dq.append(0)
    d[0] = 0

    while(len(dq) > 0):
        n = dq.popleft()
        for i in range(len(adj[n])):
            if d[adj[n][i]] != -1:
                continue
            else:
                dq.append(adj[n][i])
                d[adj[n][i]] = d[n] + 1
                par[adj[n][i]] = n

    print("Yes")
    for i in range(1, len(par)):
        print(par[i]+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N, M = map(int, input().split())
    d = [-1 for i in range(N)]
    par = [-1 for i in range(N)]
    adj = [list() for i in range(N)]

    for i in range(M):
        A, B = map(int, input().split())
        adj[A-1].append(B-1)
        adj[B-1].append(A-1)

    dq = deque()
    dq.append(0)
    d[0] = 0

    while(len(dq) > 0):
        n = dq.popleft()
        for i in range(len(adj[n])):
            if d[adj[n][i]] != -1:
                continue
            else:
                dq.append(adj[n][i])
                d[adj[n][i]] = d[n] + 1
                par[adj[n][i]] = n

    reachable = True

    for i in range(1, len(par)):
        if par[i] == -1:
            reachable = False

    if reachable :
        print("Yes")
    else:
        print("No")

    for i in range(1, len(par)):
        print(par[i]+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A, B = [], []
dic = {i:[] for i in range(1, N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)

node = [float('inf')] * N
node[0] = 0 #1までの距離
route = [0]*N #ランプ置く部屋
rooms = [1] #次調べる部屋
st = {1}

for r1 in rooms:
    for r2 in dic[r1]:
        if node[r1-1] + 1 <= node[r2-1]:
            node[r2-1] = node[r1-1] + 1
            route[r2-1] = r1
            if not r2 in st:
                rooms.append(r2)
                st.add(r2)
            try:
                dic[r2].remove(r1)
            except:
                continue

if float('inf') in node:
    print('No')
else:
    print('Yes')
    for i in route[1:]:
        print(i)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
# graph = [[] for _ in range(N + 1)]
graph = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

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

while len(queue)>0:
    now = queue.pop(0)
    for v in graph[now]:
        if dist[v] == 0:
            queue.append(v)
            dist[v] = now


print("Yes")
for k in dist[2:]:
    print(k)

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    ### bfs ###
    q = queue.Queue()
    F = [-1]*N # 道標の先の部屋
    s = 1 # 始点
    while True:
        for v in vum[s]:
            if F[v-1] < 0:
                q.put(v)
                F[v-1] = s
        if q.empty():
            break
        s = q.get()

    if -1 in F[1:]:
        print('No')
    else:
        print('Yes')
        for f in F[1:]:
            print(f)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int, input().split())
dic = {}

AB = [map(int, input().split()) for _ in range(m)]

dic = [[] for _ in range(n + 1)]

for a,b in AB:
    a -= 1
    b -= 1

    dic[a].append(b)
    dic[b].append(a)

#dist = {}
queue = deque([0])
visited = []
pre = [-1] * (n+1)

#dist[0] = 0 
queue.append(0)

while queue:
    v = queue.popleft()
    
    for i in dic[v]:
        if pre[i] == -1:
        #dist[i] = dist[v] + 1
            pre[i]= v
            queue.append(i)

print("Yes")
for i in range(n):
    ans = 0
    
    if(i == 0):
        continue
    
    ans = pre[i]
    ans += 1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())

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

dist = [-1] * n
prev_node = [-1] * n
dist[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for v_next in graph[v]:
        if dist[v_next] == -1:
            dist[v_next] = dist[v] + 1
            prev_node[v_next] = v
            q.append(v_next)

# print(dist)
# print(prev_node)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
w={}
for i in range(m):
    a,b=map(int,input().split())
    if a in w: w[a].add(b)
    else: w[a]=set([b])
    if b in w: w[b].add(a)
    else: w[b]=set([a])

d=[-1]*(n+1)
p=set([1])
q=set([])
d[1]=0
f=1
while 1:
    if f%2:
        for i in p:
            for j in w[i]:
                if d[j]==-1 or f<d[j]:
                    d[j]=f
                    q.add(j)
        p=set([])
        if len(q)==0: break
    else:
        for i in q:
            for j in w[i]:
                if d[j]==-1:
                    d[j]=f
                    p.add(j)
        q=set([])
        if len(p)==0: break
    f+=1
#print(d)
print("Yes")
for i in range(2,n+1):
    for j in w[i]:
        if d[j]+1==d[i]:
            print(j)
            break

Submission status: Accepted

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

queue = deque([1])
d = [None]*(N+1)
d[1]=None
while queue:
    now = queue.popleft()
    for i in g[now]:
        if d[i] is None:
            d[i]=now
            queue.append(i)
print("Yes")
for i in range(2,N+1):
    print(d[i])

Submission status: Accepted

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

from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]

for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

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

Q = deque()
Q.append(1)

while Q:
    x = Q.pop()
    for t in G[x]:
        if USED[t] == -1:
            Q.appendleft(t)
            USED[t] = x

if -1 in USED:
    print("No")
else:
    print("Yes")
    print(*USED[2:])

Submission status: Accepted

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

N,M=map(int,input().split())
E=[[] for i in range(N+1)]

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

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

from collections import deque
Q=deque()
Q.append(1)
while Q:
    x=Q.pop()
    for to in E[x]:
        if USE[to]==-1:
            USE[to]=x
            Q.appendleft(to)

if -1 in USE:
    print("No")
else:
    print("Yes")
    print(*USE[2:])

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

graph = [[] for i in range(N)]

for A, B in AB:
    graph[A-1] += [B]
    graph[B-1] += [A]

D = deque([0])
visited = [0] * N
visited[0] = 1

ret = [0 for i in range(N)]

while D:
    v = D.popleft()
    for i in graph[v]:
        i -= 1
        if visited[i]: continue
        visited[i] = 1
        ret[i] = v + 1
        D.append(i)

if any(ret[1:]):
    print("Yes")
    for i in ret[1:]:
        print(i)
else:
    print("No")

Submission status: Accepted

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

for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

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

Q = deque()
Q.append(1)

while Q:
    x = Q.pop()
    for t in G[x]:
        if USED[t] == -1:
            Q.appendleft(t)
            USED[t] = x

if -1 in USED:
    print("No")
else:
    print("Yes")
    print(*USED[2:])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
graph = [0]*(N+1)
for i in range(N+1):
    graph[i]=list()
for i in range(M):#生成
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
graph[0].append(1)
# for i in range(N+1):#整列
#     graph[i].sort()
# print(graph)
ans = [-1]*(N+1)
ans[1] = 0
dis_stack = list()
dis_stack.extend(graph[0])
bef_stack = [1]
# k = 0
# print(graph)


while dis_stack:
    now_watch=dis_stack.pop(0)
    next_watch = graph[now_watch]
    for spot in next_watch:
        if(ans[spot] != -1):
            continue            
        # print(dis_stack)
        # print(bef_stack)
        dis_stack.append(spot)
        ans[spot] = now_watch
            # print(ans)
 
ans.pop(0)
print("Yes")
for i in range(1,len(ans)):
    print(ans[i])

    # k +=1
# 探索スタート地点を「探索候補スタック」に積む
# while スタックが空っぽになるまで
#     スタックから次の探索地点を1つ取り出す（pop）
#     「探索済みリスト」に取り出した地点を格納（ここが現在地点）
# 　　現在地点から、次に行こうと思えば行けるポイントを全部探し出す
#     for 地点 in 次に行こうと思えば行けるポイント
#         if その地点は既に「探索済みリスト」にある？
#             探索済みなので「探索候補スタック」には入れない（continue）
#         if その地点は既に「探索候補スタック」にある？（閉路があるなら可能性あり、木なら可能性なし）
#             探索予定なので「探索候補スタック」には入れない（continue）
#         未探索かつ候補にも入っていない地点なので「探索候補スタック」に追加する（append）
# print 探索済み地点

Submission status: Accepted

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

for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

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

Q = deque()
Q.append(1)

while Q:
    x = Q.pop()
    for t in G[x]:
        if USED[t] == -1:
            Q.appendleft(t)
            USED[t] = x

if -1 in USED:
    print("No")
else:
    print("Yes")
    for _ in USED[2::]:
        print(_)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())

AB = [list(map(int, input().split())) for i in range(M)]

links=[[] for _ in range(N+1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)

results=[-1]*(N+1)#番号をそのまま使いたいからプラス１
#このresults[i]のiが各部屋となり、そのresults[i]の値が繋がる別の部屋番号となる

q=deque([1])#1からスタートさせるために

while q:
    pos=q.popleft()#1からスタート
    for i in links[pos]:#部屋posにつながる部屋iを探索
        if results[i]==-1:#部屋iを未探索なら、そこに行くべき場所posを記入 すでに値が入っている場合では、この場合部屋探索は１からスタートしているため先に入っている値（部屋番号）が１に近い数値となっている。なので値が入っている場合はスルーする。
            results[i]=pos
            q.append(i)#捜索した部屋iを次の出発地として追記
print('Yes')
print('\n'.join(str(i) for i in results[2:]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
visited = [-1 for _ in range(n+1)]
visited[1] = 0
will = []
root = [[] for _ in range(n+1)] 
for i in range(m):
    a,b = map(int,input().split())
    root[a].append(b)
    root[b].append(a)

will.append(1)

while will:
    visit = will.pop(0)
    for i in root[visit]:
        if visited[i] != -1:
            continue
        will.append(i)
        visited[i] = visit

if visited[1:] == -1:
    print('No')
else:
    print('Yes')
    for i in range(2,len(visited)):
        print(visited[i])

Submission status: Accepted

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)
    g[b-1].append(a)
d = [0]*n
check = [False]*n
check[0] = True
def bfs():
    q = deque()
    q.append(1)
    
    while q:
        room = q.popleft()
        for nroom in g[room-1]:
            if check[nroom-1]:
                continue
            d[nroom-1] = room
            check[nroom-1] = True
            q.append(nroom)

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