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:
from collections import deque           
#頂点数と辺数
N, M = map(int, input().split())

#グラフ入力受取(無向グラフを想定)
G = [[] for _ 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)

#BFSのためのデータ構造
dist = [False]*N #全頂点を「未訪問」に初期化
que = deque()

#初期条件（頂点0を初期ノードとする）
dist[0] = True
que.append(0) #0を訪問予定頂点にする
ans = [0]*N

#BFS開始（キューが空になるまで探索を行う）
while len(que)!=0:
    v = que.popleft() #キューから先頭頂点を取り出す

    #v から辿れる頂点を全て調べる
    for nv in G[v]:
        #すでに発見済みの頂点は探索しない
        if dist[nv]:
            continue 

        #新たな白色頂点 nv について距離情報を更新してキューに追加する
        dist[nv] = True
        ans[nv] = v 
        que.append(nv)

    #結果出力（各頂点の頂点 0 からの距離を見る）
if any(dist):
    print("Yes")
    for v in range(1,N):
        print(ans[v]+1)
else:
    print("No")

Submission status: Accepted

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

ab = []
room = [set() for _ in range(n)]
root_help = [-1 for _ in range(n)]
for i in range(m):
    tmp=list(map(int,input().split()))
    tmp.sort()
    room[tmp[0]-1].add(tmp[1]-1)
    room[tmp[1]-1].add(tmp[0]-1)
    ab.append(tmp)

ab.sort(key=lambda x:x[0])

posi=[0]
next = [1]
already = {0}
while posi:
    tmp_posi=[]
    for p in posi:
        connect = room[p]
        for i in connect:
            if i not in already:
                root_help[i]=p
                already.add(i)
                tmp_posi.append(i)
    posi=tmp_posi

answer = [i + 1 for i in root_help[1::]]
if 0 in answer:
    print('No')
else:
    print('Yes')
    for i in answer:
        print(i)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
AB = [[] for _ in range(N)]
for i in range(M):
  A, B = map(int,input().split())
  AB[A-1].append(B-1)
  AB[B-1].append(A-1)
T = [-1]*N
T[0] = 0
tlist = [0]
t_change = True
while t_change:
  t_change = False
  tlist2 = []
  for t in tlist:
    for i in AB[t]:
      if T[i]==-1:
        t_change = True
        T[i] = t
        tlist2.append(i)
  tlist = tlist2
  
if -1 in T:
  print('No')
else:
  print('Yes')
  for i in range(1,N):
    print(T[i]+1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [[] for _ 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)

from collections import deque
que = deque()
que.append(0)
seen = [-1] * n
seen[0] = 0
while len(que) > 0:
    i = que.popleft()
    for gi in G[i]:
        if seen[gi] != -1:
            continue
        seen[gi] = i
        que.append(gi)
print('Yes')
for i in range(1, n):
    print(seen[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,m = MI()
ab = LI(m)

g = [ [] for _ in range(n) ]
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)
# print(g)

ls_ans = [-1]*n

q = deque()
q.append(0)

while q:
    t = q.popleft()
    ls = g[t]
    for i in ls:
        if ls_ans[i]==-1:
            ls_ans[i] = t
            q.append(i)
        else:
            pass
# print(ls_ans)

if -1 in ls_ans:
    print("No")
else:
    for i in range(n):
        if i==0:
            print("Yes")
        else:
            print( ls_ans[i] + 1 )

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
G = [[] for _ 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)

que = deque([0])
seen = [-1] * n
seen[0] = 0

while len(que) > 0:
    now_v = que.popleft()
    now_board = seen[now_v]
    next_vs = G[now_v]
    for next_v in next_vs:
        if seen[next_v] == -1:
            seen[next_v] = now_v
            que.append(next_v)

print('Yes')
for x in seen[1:]:
    print(x + 1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
path=[[] for i in range(n+1)]
anser=[0 for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  path[a].append(b)
  path[b].append(a)
nowlis=[1]
nowdone=1
anser[1]=1
while nowdone<n:
  now=nowlis.pop(0)
  done=path[now]
  #print("now",now,"次",done)
  for i in done:
    if anser[i]==0:
      anser[i]=now
      nowlis.append(i)
      nowdone+=1
  #print("anser",anser)
kad=anser.pop(0)
kadd=anser.pop(0)
print("Yes")
for i in anser:
  print(i)

Submission status: Accepted

Solution code:
from _collections import deque
n,m=map(int,input().split())
X=[[] for _ in range(n)]
visited=[0]*(n+1)
ANS=[0]*n
ANS[0]=1
for i in range(m):
    a,b=map(int,input().split())
    X[a-1].append(b-1)
    X[b-1].append(a-1)

q=deque([0])
visited[0]=1
while len(q)>0:
    s=q.popleft()
    for x in X[s]:
        if visited[x]:
            continue
        q.append(x)
        ANS[x]=s
        visited[x]=1
print('Yes')
for ans in ANS[1:]:
    print(ans+1)

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor, gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    
    N,M = LMIIS()
    edge = defaultdict(list)
    for i in range(M):
        a,b = LMIIS()
        edge[a].append(b)
        edge[b].append(a)

    #ダイクストラで1から各部屋への最短距離を求める
    visited = [-1] * (N+1)


    #根が１の木を作る
    #根から子を辿って、ルートを確定させていく
    roots = deque()
    roots.append(1)
    visited = [INF]*(N+1)
    visited[1] = 0
    lights = [0]*(N+1)
    while len(roots) > 0:
        root = roots.popleft()
        length = visited[root]
        for v in edge[root]:
            if length + 1 < visited[v]:
                visited[v] = length + 1
                lights[v] = root
                roots.append(v)
    print('Yes')
    for i in range(2,N+1):
        print(lights[i])





main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

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

Graph=defaultdict(list)

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

ans=[0]*(N+1)
q=deque()
q.append(1)

while(q):
  start=q.popleft()
  startans=ans[start]
  for a in Graph[start]:
    if ans[a]>0 or a==1:
      continue
    else:
      ans[a]=start
      q.append(a)
  #print(ans,q)
#print(Graph)
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
to = [[] for _ in range(N)]
ans = [-1] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

from collections import deque

Q = deque([0])
ans[0] = -2

while Q:
    v = Q.popleft()
    for s in to[v]:
        if ans[s] == -1:
            ans[s] = v
            Q.append(s)
print("Yes")
print(*(a + 1 for a in ans[1:]), sep="\n")

Submission status: Accepted

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

visited = [False for i in range(N+1)]
mark = [0 for i in range(N+1)]
q = deque([1])
while len(q) != 0:
    p = q.popleft()
    for g in G[p]:
        if not visited[g]:
            q.append(g)
            mark[g] = p
            visited[g] = True

cnt_visited = len([v for v in visited if v])
if cnt_visited != N:
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(mark[i])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
f=lambda:map(int,input().split())
n,m=f()
g=[[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
d=[-1]*n
from collections import deque
q=deque([0])
d[0]=0
while q:
  p=q.popleft()
  for c in g[p]:
    if d[c]<0:
      d[c]=p
      q.append(c)
if -1 in d: print('No')
else:
  print('Yes')
  for i in range(1,n): print(d[i]+1)

Submission status: Accepted

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import sys
    input=sys.stdin.readline
    n,m=L()
    dic={}
    michi=[1e+7]*(n-1)#部屋2~部屋Nまで→部屋2=michi[0],部屋N→michi[n-2]
    for i in range(m):
        ai,bi=L()
        if ai not in dic:
            dic[ai]=[]
        if bi not in dic:
            dic[bi]=[]
        dic[ai].append(bi)
        dic[bi].append(ai)
    from collections import deque
    d=deque()
    for i in dic[1]:
        michi[i-2]=1
        d.append(i)
    while len(d)!=0:
        i=d.popleft()
        #print(i)
        #tmp=michi[i-2]
        #tmp=i
        for j in dic[i]:
            #print(j,end=' ')
            if j==1:
                continue
            if michi[j-2]==1e+7:
                michi[j-2]=i
                d.append(j)
        #print()
        
    for i in michi:
        if i>=1e+7:
            print('No')
            exit()
    print('Yes')
    for i in michi:
        print(i)
    
        
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

from collections import deque
checked = [-1]*N
dirc = [-1]*N
def bfs(v):
    queue = deque()
    queue.appendleft((v, 0))
    while queue:
        v, p = queue.pop()
        if checked[v]==1:
            continue
        dirc[v] = p
        checked[v] = 1
        for i in rooms[v]:
            if checked[i]==-1:
                queue.appendleft((i, v))

bfs(0)
if -1 in dirc:
    print('No')
else:
    print('Yes')
    for d in dirc[1:]:
        print(d+1)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
from collections import *


def bfs():
    q = deque([1])
    dist = [0] * (N + 1)
    while q:
        v = q.popleft()

        for nv in G[v]:
            if dist[nv] == 0:
                dist[nv] = v
                q.append(nv)

    return dist


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)

dist = bfs()

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    pas = [-1 for _ in range(N)]
    pas[S] = 's'
    frag = set([S])
    que = deque([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:
            if i in frag:  # 処理済みか否か
                continue
            pas[i]=q
            que.append(i)
            frag.add(i)
    return pas


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

near = [[] for _ in range(n)]
for a, b in ab:
    near[a - 1].append(b - 1)
    near[b - 1].append(a - 1)
pas = bfs(near, 0, n)

if all(pas[i] != -1 for i in range(n)):
    print('Yes')
    for i in range(1, n):
        print(pas[i] + 1)
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int, input().split())
g = [[] for _ 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)

ans = [-1]*N
ans[0] = 0
q = deque([0])    # 今の部屋

while q:
    now =  q.popleft()
    for nxt in g[now]:
        if ans[nxt] == -1:
            ans[nxt] = now
            q.append(nxt)
print('Yes')
for i in range(1,N):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

pathes = {i: set() for i in range(1, n + 1)}
for _ in range(m):
  ai, bi = map(int, input().split()) 
  pathes[ai].add(bi)
  pathes[bi].add(ai)

queue = deque()
queue.append(1)

ans = [None] * n 

for _ in range(n):
  if len(queue) == 0:
    break;
  i = queue.popleft()
  next_room = pathes[i]
  for j in next_room:
    if ans[j-1] == None:
      ans[j-1] = str(i)
      queue.append(j)

ans[0] = "Yes"

print("\n".join(ans))

Submission status: Accepted

Solution code:
from collections import deque

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

visit = [-1]*N
visit[0] = 0
q = deque()
q.append([0, 0])
while len(q) > 0:
    v, c = q.popleft()
    for u in ab[v]:
        if visit[u] < 0:
            visit[u] = v
            q.append([u, v])

ok = True
for i in range(1, N):
    if visit[i] < 0:
        ok = False

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
from collections import deque
def resolve():
    N,M=pin()
    edge=dict()
    for i in range(M):
        a,b=pin()
        #non-directed
        edge.setdefault(a,[])
        edge.setdefault(b,[])
        edge[a].append(b)
        edge[b].append(a)
    #print(edge)
    milestones=[0]*(N+1)#1-index
    milestones[1]=1
    c=deque([1])
    #print(c)
    while(1):
        if len(c)==0:
            break
        t=c.popleft()
        #print(t)
        for to in edge[t]:
            #print(f"to={to}")
            if milestones[to]==0:
                milestones[to]=t
                c.append(to)
        #print(c)
        ##print(f"milestones={milestones}")
        ##print(f"endt={t}")
    print("Yes")
    print(*milestones[2:],sep="\n")
        
#%%submit!
resolve()

Submission status: Accepted

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

q=deque([])

edge=[set([]) for _ in range(n+1)]
mark=[-1 for _ in range(n+1)]
used=[False for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].add(b)
    edge[b].add(a)

q.append(1)
mark[1]=1
used[1]=True
while(len(q)>0):
    vi=q.popleft()
    ei=edge[vi]
    for eij in ei:
        if(used[eij]):
            continue
        else:
            mark[eij]=vi
            used[eij]=True
            q.append(eij)

print('Yes')
for i in range(2,len(mark)):
    print(mark[i])

Submission status: Accepted

Solution code:
import queue
n,m=map(int,input().split())
a=[[] for i in range(n)]
for i in range(m):
    b,c=map(int,input().split())
    if c!=1:
        a[b-1].append(c)
    if b!=1:
        a[c-1].append(b)
d=[0 for i in range(n)]
qu=queue.Queue()
qu.put(1)
while qu.empty()==False:
    qu1=qu.get()
    for i in range(len(a[qu1-1])):
        if d[a[qu1-1][i]-1]==0:
            d[a[qu1-1][i]-1]=qu1
            qu.put(a[qu1-1][i])
for i in range(1,n):
    if d[i]==0:
        print("No")
        break
else:
    print("Yes")
    for i in range(1,n):
        print(d[i])

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(N + 1):
        AB.append([])
    for _ in range(M):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)
    result = [0] * (N + 1)
    from collections import deque
    work = deque([])
    append = work.append
    pop = work.popleft
    append(1)
    while len(work) > 0:
        now = pop()
        for to in AB[now]:
            if result[to] == 0:
                result[to] = now
                append(to)
    for i in result[2:]:
        if i == 0:
            print("No")
            return
    print("Yes")
    for i in result[2:]:
        print(i)
main()

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())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

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

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = list(map(int, input().split()))
al = [0] * n
bl = [0] * n
G = [[] for _ 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)
N = n
# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

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

print('Yes')
for t in tag[1:]:
    print(t)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def dijkstra(path, N, start):
    visited = [False] * N
    mark = [-1] * N  # その頂点の次にどの頂点に行くか決定済みのもの
    que = [(0, start, -1)]  # (コスト、頂点、前の頂点)
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v, pre = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        if v > 0:
            if mark[v] != -1 and mark[v] != pre:
                return 'No'
            mark[v] = pre
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to, v))

    return mark

def main():
    N, M = map(int, readline().rstrip().split())
    path = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().rstrip().split())
        path[a-1].append((1, b-1))
        path[b-1].append((1, a-1))
    
    start = 0
    mark = dijkstra(path, N, start)
    if mark == 'No':
        print('No')
        return

    print('Yes')
    for v in range(1, N):
        print(mark[v] + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    visited = set()
    visited.add(1)
    res = [0 for _ in range(N+1)]
    To = {}
    for a, b in zip(A, B):
        if a in To:
            To[a].add(b)
        else:
            To[a] = set()
            To[a].add(b)
        if b in To:
            To[b].add(a)
        else:
            To[b] = set()
            To[b].add(a)
    crt = set()
    crt.add(1)
    crt2 = set()
    while(len(visited) < N):
        for i in crt:
            for j in To[i]:
                if j not in visited:
                    res[j] = i
                    visited.add(j)
                    crt2.add(j)
        crt = set(crt2)
        crt2.clear()

    print(YES)
    for i in range(2, N+1):
        print(res[i])
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline


def main():
    N, M = [int(v) for v in input().split()]

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

    arrow = [-1] * N

    def search():
        q = deque()
        q.append(0)

        closed = 1

        while q:
            e = q.popleft()
            for n in net[e]:
                if closed & (1 << n) == 0:
                    q.append(n)
                    arrow[n] = e
                    closed |= (1 << n)

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

    search()


main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline

n, m = map(int, input().split())
G = [[]for i in range(n+1)]
for i in range(m):
    a, b = map(int, readline().split())
    G[a].append(b)
    G[b].append(a)

ans = [0]*(n+1)

stk = deque([1])

while stk:
    v = stk.pop()
    for s in G[v]:
        if ans[s] == 0:
            ans[s] = v
            stk.appendleft(s)
ans = ans[2:]

if 0 in ans:
    print("No")
else:
    print("Yes")
    for i in ans:
        print(i)

Submission status: Accepted

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

from collections import deque

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

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

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

check_list = [0 for _ in range(n)]
d = deque([(0, -1)])
ans = [0 for _ in range(n)]
while(len(d) >= 1):
    # print(d)
    index, origin = d.popleft()
    if check_list[index] == 1:
        continue
    else:
        check_list[index] = 1
        ans[index] = origin
    road_list = road_map[index]

    for i in road_list:
        if check_list[i] == 0:
            # check_list[i] = 1
            d.append((i, index))


for i in range(1, len(ans)):
    if ans[i] == -1:
        print("No")
        exit()

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

def main():
    N, M = map(int, input().split())
    to = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
    
    # bfs
    visited = [False] * N
    par = [-1] * N 

    def bfs(s):
        q = deque()
        q.append(s)
        visited[s] = True
        par[s] = s

        while q:
            now = q.popleft()
            for nv in to[now]:
                if visited[nv]: continue
                else:
                    visited[nv] = True
                    par[nv] = now+1
                    q.append(nv)
    bfs(0)

    if -1 in par:
        print("No")
    else:
        print("Yes")
        print(*par[1:], sep="\n")

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
N rooms and M passages
"""

import sys

input = sys.stdin.readline

from collections import deque

def solve(n, m, g):
    visited = [0] * (n+1)
    prev = [0] * (n+1)

    deq = deque([0])
    visited[0] = 1
    visited_count = 1

    while deq:
        node = deq.popleft()

        for nb in g[node]:
            if not visited[nb]:
                visited[nb] = 1
                deq.append(nb)
                visited_count += 1
                prev[nb] = node + 1
    
    if visited_count == n:
        print("Yes")
        for node in range(1, n):
            print(prev[node])
    else:
        print("No")
            


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

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

solve(n, m, g)

Submission status: Accepted

Solution code:
from collections import deque

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

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

dist=[-1 for i in range(n)]
dist[0]=0

ans=[-1 for i in range(n)]
ans[0]=0

dq=deque()
dq.append(0)
while dq:
  x=dq.popleft()
  for i in tree[x]:
    if ans[i]==-1:
      ans[i]=x
      dq.append(i)

if -1 in ans:
  print('No')
  exit()

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

Submission status: Accepted

Solution code:
import sys
# from functools import lru_cache, cmp_to_key
# from heapq import merge, heapify, heappop, heappush
from math import sqrt, sin, cos, pi
from collections import defaultdict as dd, deque, Counter as C
# from itertools import combinations as comb, permutations as perm
# from bisect import bisect_left as bl, bisect_right as br, bisect
# from time import perf_counter
# from fractions import Fraction

# sys.setrecursionlimit(pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353


def data(): return sys.stdin.readline().strip()


def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)


def l(): return list(sp())


def sl(): return list(ssp())


def sp(): return map(int, data().split())


def ssp(): return map(str, data().split())


def l1d(n, val=0): return [val for i in range(n)]


def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


inf = 10 ** 20
n, m = sp()
graph = dd(set)
for i in range(m):
    u, v = sp()
    graph[u].add(v)
    graph[v].add(u)
dist = dd(lambda: inf)
dist[1] = 0
answer = dd(int)
vis = dd(lambda: False)
vis[1] = True
stack = deque()
stack.append(1)
while stack:
    temp = stack.popleft()
    for child in graph[temp]:
        if not vis[child]:
            stack.append(child)
            vis[child] = True
        if dist[child] > dist[temp] + 1:
            dist[child] = dist[temp] + 1
            answer[child] = temp
for i in range(1, n+1):
    if not vis[i]:
        out("No")
        exit()
out("Yes")
for i in range(2, n+1):
    out(answer[i])

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(m)]

es = [[] for i in range(n)]
for x,y in src:
    x,y = x-1,y-1
    es[x].append(y)
    es[y].append(x)

INF = float('inf')
ds = [INF] * n
ans = [-1]*(n)

def dijkstra(start, dists):
    dists[start] = 0
    hq = [(0,start)]
    heapq.heapify(hq)
    while hq:
        dist,v = heapq.heappop(hq)
        for to in es[v]:
            if dist+1 >= dists[to]: continue
            dists[to] = dist+1
            ans[to]=v+1
            heapq.heappush(hq, (dist+1,to))

dijkstra(0,ds)

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
input = stdin.readline

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

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

q = deque()

for x in a[1]:
    q.append(x)
    chk[x] = 1
    chkchk[x] = 0

while True:
    if len(q) == 0:
        break

    now = q.popleft()

    for x in a[now]:
        if chkchk[x] == 0:
            continue

        q.append(x)
        chk[x] = now
        chkchk[x] = 0

if sum(chkchk) == 0:
    print("Yes")
    for x in chk[2:]:
        print(x)
else:
    print("No")