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:
#!/usr/bin/env python
from collections import deque

def main():
    n, m = map(int, input().split())
    rw_lst = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        rw_lst[a].append(b)
        rw_lst[b].append(a)

    sign_lst = [-1 for _ in range(n+1)]
    sign_lst[1] = 0
    check_lst = [False for _ in range(n+1)]
    check_lst[1] = True

    queue = deque([1])
    while queue:
        room = queue.popleft()
        for way in rw_lst[room]:
            if not check_lst[way]:
                check_lst[way] = True
                sign_lst[way] = room
                queue.append(way)

    check = True
    for i in range(1, n+1):
        check = check and check_lst[i]

    if check:
        print("Yes")
        for i in range(2, n+1):
            print(sign_lst[i])
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

way = [0 for i in range(N)]
way[0] = 1
que = deque([0])

while True:
    if len(que) == 0:
        break
    a = que.popleft()
    for i in room[a]:
        if way[i] == 0:
            way[i] = a + 1
            que.append(i)

if 0 in way:
    print("No")
else:
    print("Yes")
    for i in way[1:]:
        print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(500000)

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

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

for i in range(m):
    ta,tb=map(int, input().split())
    if ta!=1:
        a[tb-1].append(ta-1)
    if tb!=1:
        a[ta-1].append(tb-1)

KITENAI=900000
ans=[0]*n
mk=[KITENAI]*n
mk[0]=0
qu=[0]

def setnext(now):
    global mk
    global qu

    for i in a[now]:
        if mk[i]==KITENAI:
            qu.append(i)
            mk[i]=mk[now] + 1
            ans[i]=now+1

while len(qu)>0:
    setnext(qu.pop(0))

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

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):
    x,y = map(int,input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)
ans = [-1]*n
deq = deque([0])
while deq:
    fr = deq.popleft()
    for go in g[fr]:
        if ans[go] == -1:
            ans[go] = fr
            deq.append(go)
print("Yes")
for i in ans[1:]:print(i+1)

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

# mod = int(1e9+7)
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)
            v[y] = x
    print("Yes")
    for i in range(1,n):
        print(v[i]+1)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:

import queue

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

G=[[] for i in range(n)]

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

q=queue.Queue()

vis=[0]*n
mae=[-1]*n

q.put([0,0])
while q.empty()==False:
 r=q.get()
 if vis[r[0]]==1:
  continue
 vis[r[0]]=1
 mae[r[0]]=r[1]
 for v in G[r[0]]:
  if vis[v]==0:
   q.put([v,r[0]])

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict


def bfs(graph, start):

    queue = deque([start])
    visited = set()
    visited.add(start)
    parent = defaultdict(int)
    parent[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                queue.append(v)
                visited.add(v)
                parent[v] = current_vertex
    return parent

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

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

parent = bfs(graph, 1)

print('Yes')
for k, v in sorted(parent.items()):
    if v != 0:
        print(v)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import deque

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

    for m in range(M):
        A, B = map(int, input().split())
        path[A-1].append(B-1)
        path[B-1].append(A-1)
    
    sign = [-1]*N
    q = deque()
    q.append(0)
    while q:
        u = q.popleft()
        for v in path[u]:
            if sign[v] == -1:
                sign[v] = u + 1
                q.append(v)
    
    print('Yes')
    print('\n'.join(map(str, sign[1:])))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


r, p = map(int, input().split())
graph = [[] for _ in range(r)]

for x in range(p):
    x1, x2 = map(int, input().split())
    graph[x1-1].append(x2-1)
    graph[x2-1].append(x1-1)

q = deque([0])
res = [-1]*r
res[0] = 0
while q:
    l = q.popleft()
    for x in graph[l]:
        if res[x] == -1:
            res[x] = l
            q.append(x)
if -1 in res[1:]:
    print("No")
    exit()
print("Yes")
for x in res[1:]:
    print(x+1)

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

visited={1}
stack=deque([1])
re=[-1 for i in range(N+1)]
re[0]=0
re[1]=0
while stack:
    #print(stack)
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            re[p]=a
            stack.append(p)
#print(re)
if -1 in re:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(re[i])

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque


def S(): return sys.stdin.readline().rstrip()


def I(): return int(sys.stdin.readline().rstrip())


def MI(): return map(int, sys.stdin.readline().rstrip().split())


def MS(): return map(str, sys.stdin.readline().rstrip().split())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def LS(): return list(sys.stdin.readline().rstrip().split())


# N = I()
# A = [LI() for _ in range(N)]


n, m = map(int, input().split())
a = [0] * m
b = [0] * m
box = [[] for i in range(n)]
s = deque()
ans = [-1] * (n - 1)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    box[a[i] - 1].append(b[i])
    box[b[i] - 1].append(a[i])
for i in range(len(box[0])):
    s.append([1, box[0][i]])

while len(s) > 0:
    k = s.popleft()

    if ans[k[1] - 2] == -1 and k[1] - 2 != -1:
        ans[k[1] - 2] = k[0]

        for i in range(len(box[k[1] - 1])):
            s.append([k[1], box[k[1] - 1][i]])

print('Yes')
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
import queue
def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q =queue.Queue()
    q.put(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.get()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.put(next)
        if q.empty():
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

ans=[-1]*n
ans[0] = 0
from collections import deque
q = deque([0])
while q:
    a=q.popleft()
    for i in lis[a]:
        if ans[i]==-1:
            ans[i]=a
            q.append(i)
print("Yes")
for i in range(1,len(ans)):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
from queue import Queue

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

visited = [False for x in range(n)]
distance = [float("inf") for x in range(n)]
distance[0] = 0
parent = [-1 for x in range(n)]
que = Queue()
que.put(0)
while not que.empty():
    now = que.get()
    if visited[now]:
        continue
    visited[now] = True
    for _next in d[now]:
        if visited[_next]: continue
        if parent[_next] != -1: continue
        parent[_next] = now + 1
        distance[_next] = min(distance[_next], distance[now] + 1)
        que.put(_next)
print("Yes")
for i in parent[1:]:
    print(i)

Submission status: Accepted

Solution code:
import collections

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)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
ans=[0]*(n+1)
while len(q)!=0:
  v=q.popleft()
  for u in g[v]:
    if check[u]==0:
      check[u]=1
      ans[u]=v
      q.append(u)
print('Yes')
for i in range(2,n+1):
  print(ans[i])

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque


def S(): return sys.stdin.readline().rstrip()


def I(): return int(sys.stdin.readline().rstrip())


def MI(): return map(int, sys.stdin.readline().rstrip().split())


def MS(): return map(str, sys.stdin.readline().rstrip().split())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def LS(): return list(sys.stdin.readline().rstrip().split())


# N = I()
# A = [LI() for _ in range(N)]


n, m = map(int, input().split())
a = [0] * m
b = [0] * m
box = [[] for i in range(n)]
s = deque()
ans = [-1] * (n - 1)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    box[a[i] - 1].append(b[i])
    box[b[i] - 1].append(a[i])
for i in range(len(box[0])):
    s.append([1, box[0][i]])

while len(s) > 0:
    k = s.popleft()

    if ans[k[1] - 2] == -1 and k[1] != 1:
        ans[k[1] - 2] = k[0]

        for i in range(len(box[k[1] - 1])):
            s.append([k[1], box[k[1] - 1][i]])

print('Yes')
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
d=deque()

l=[[] for _ in range(n)]
R=[-1]*(n+1)
R[1]=0

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

def g(s):
    for i in range(len(l[s-1])):
        if R[l[s-1][i]]==-1:
            R[l[s-1][i]]=s
            d.append(l[s-1][i])
    if len(d)!=0:
        s=d.popleft()
        return g(s)
    else:
        return
g(1)
print("Yes")
for h in range(2,len(R)):
    print(R[h])

Submission status: Accepted

Solution code:
import sys
import numpy as np
#import math
#import itertools
#import re
#from functools import lru_cache
from collections import deque

input = sys.stdin.readline
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    n, m = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(m)]
    graph = [[] for _ in range(n)]
    for a, b in AB:
        graph[a-1].append(b)
        graph[b-1].append(a)
    dist = np.ones(n)
    dist *= -1
    dist[0] = 0
    queue = deque([1])
    while queue:
        p = queue.popleft()
        for next in graph[p-1]:
            if dist[next-1] == -1:
                dist[next-1] = p
                queue.append(next)

    if np.count_nonzero(dist == -1) > 0:
        print(c)
    else:
        print('Yes')
        for d in dist[1:]:
            print(int(d))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans_li = [-1]*n
queue=deque([0])
visited = [False]*n

while queue:
    x = queue.popleft()
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def bfs(s):
    from collections import deque
    check = [0] * (n + 1)
    check[s] = 1
    q = deque([s])
    while q:
        now = q.popleft()
        for next in graph[now]:
            if check[next] == 0:
                check[next] = str(now)
                q.append(next)
    return check


n, m = map(int, readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
print('Yes')
print('\n'.join(bfs(1)[2:]))

Submission status: Accepted

Solution code:
# ダイクストラ法
# connections = [[[町ｘ, コスト], [町y, コスト]], ...]
import heapq as hq


def D_stra(N, connections, st):
    mxc = float("inf") #2 ** 29
    cost = [mxc for i in range(N)]
    route = [mxc for i in range(N)]
    visited = [False for i in range(N)]
    cost[st] = 0
    q = []

    hq.heappush(q, (0, st))

    while q:
        c, node = hq.heappop(q)
        if visited[node]:
            continue
        visited[node] = True

        for connection in connections[node]:
            target, mc = connection
            if cost[target] > c + mc:
                cost[target] = c + mc
                hq.heappush(q, (c + mc, target))
                route[target] = node


    return cost, route

n, m = map(int, input().split())
mp2 =[]

connections = [[] for _ in range(n)]
for _ in range(m):
    aa, bb = map(int, input().split())
    connections[aa-1].append([bb-1, 1])
    connections[bb-1].append([aa-1, 1])

dijkstra_result = []
_, result = D_stra(n, connections, 0)

if float("inf") in result[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(result[i]+1)

Submission status: Accepted

Solution code:
#import numpy as np
from collections import deque
#T= str(input())
#K = int(input())
N,M= map(int,input().split())
#A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
ans=[-1]*(N+1)
X=[[] for i in range(N+1)]
#print(X)
for i in range(M):
    a,b= map(int,input().split())

    X[a].extend([b])
    X[b].extend([a])
#print(X)
c=0
dq=deque([1])

while c<N:
    i = dq.popleft()
    for j in X[i]:
        if ans[j]==-1:
            ans[j]=i
            c+=1
            dq.append(j)
            #print(ans)
print('Yes')
print(*ans[2:],sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
# from math import factorial
import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)
n, m = list(map(int, input().split()))
room = [[] for i in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    room[a-1].append(b-1)
    room[b-1].append(a-1)

ans = [-1]*n


def bfs(i):
    q = deque()
    q.append(i)
    while q:
        x = q.popleft()
        for i in range(len(room[x])):
            if ans[room[x][i]] == -1:
                q.append(room[x][i])
                ans[room[x][i]] = x
    return


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

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

# N個の部屋とM本の通路
N, M = [int(x) for x in stdin.readline().rstrip().split()]

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

# A->B と B->A をリストに保存していく
# AとBは "1以上" を想定
for _ in range(M):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    route[A].append(B)
    route[B].append(A)

# 場所1までの距離
dist_to_1 = [INF for _ in range(N+1)]
dist_to_1[1] = 0

# next_route[i] = j: 場所iがゴールに最短でたどり着くために向かう場所j
next_route = [0 for _ in range(N+1)]

# 場所iに訪れたかどうか
is_visited = [False for _ in range(N+1)]

# 幅優先探索
# 試すべき位置をキューで管理
que = deque([1])

# キューが空じゃなければ
while len(que) != 0:
    now = que.popleft()
    
    # 過去に訪れていれば無視
    if is_visited[now]:
        continue

    is_visited[now] = True

    # そこからいける場所を幅優先探索で
    for place in route[now]:
        que.append(place)

        # 距離とルートの更新
        if dist_to_1[now]+1 < dist_to_1[place]:
            dist_to_1[place] = dist_to_1[now]+1
            next_route[place] = now

# 場所2以降において、どこか次の道が見つかってない場合は
# ゴールにいけないということ
if 0 in next_route[2:]:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(next_route[i])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N, M = map(int, input().split())
guidepost = [None] * N
distance = [0] + [10**9] * (N - 1)
dd = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
stack = deque([1])
checked = [False] * N
while len(stack) >= 1:
    i = stack.popleft()
    if checked[i - 1]:
        continue
    checked[i - 1] = True
    for j in dd[i]:
        distance[j - 1] = min(distance[j - 1], distance[i - 1] + 1)
        if guidepost[j - 1] is None:
            guidepost[j - 1] = i
        elif distance[guidepost[j - 1] - 1] > distance[i - 1]:
            guidepost[j - 1] = i
        if not checked[j - 1]:
            stack.append(j)
print('Yes')
# join?
# for i in range(1, N):
#     print(guidepost[i])
print('\n'.join([str(guidepost[i]) for i in range(1, N)]))

Submission status: Accepted

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

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

#print(g)

root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in g[p+1]:
        if root[i-1] <= 0:
            q.put(i-1)
            root[i-1] = p + 1
            count += 1
            #print(p,i,count,root)
            if count >= n:
                break


if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])

Submission status: Accepted

Solution code:
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)
ans = [0] * N
visit = [0] * N
visit[0] = 1
from queue import Queue
q = Queue()
q.put(0)
while not q.empty():
    current = q.get()
    for a in L[current]:
        if visit[a] == 0:
            visit[a] = visit[current] + 1
            ans[a] = current + 1
            q.put(a)
        else:
            if visit[a] > visit[current] + 1:
                visit[a] = visit[current] + 1
                ans[a] = current + 1
flag = True
for i in range(1,N):
    if ans[i] == 0:
        flag = False
        print('No')
        break
if flag == True:
    print('Yes')
    for i in range(N-1):
        print(ans[i+1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = [[] for i in range(n)]
d = [0]
e = [-1]*n
for i in range(m):
    a, b = map(int, input().split())
    c[a-1].append(b-1)
    c[b-1].append(a-1)
while d:
    f = d.pop(0)
    for i in c[f]:
        if e[i] == -1:
            d.append(i)
            e[i] = f
print("Yes")
for i in range(n-1):
    print(e[i+1]+1)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()

rt = [[] for i in range(n)]
srb = [None] * n
dk = [10**10]*n


for i in range(m):
    a,b = mi()
    rt[a-1].append(b-1)
    rt[b-1].append(a-1)

from collections import deque
l = deque()

srb[0] = 0
for i in rt[0]:
    l.append(i)
    srb[i] = 1

while len(l) != 0:
    c = l.popleft()
    for i in rt[c]:
        if srb[i] == None:
            l.append(i)
            srb[i] = c+1

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

Submission status: Accepted

Solution code:
from collections import deque

import sys
input = sys.stdin.readline 

N,M = map(int,input().split())
path = [[] for i in range(N)]
ans = [None for i in range(N)]
visited = [0 for i in range(N)]

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

def bfs(path, root,visited):
  visited[root] = 1
  queue = deque([root])
  while queue:
    cur = queue.popleft()
    for chi in path[cur]:
      if visited[chi] == 1:
        continue
      else:
        ans[chi] = cur + 1
        visited[chi] = 1
        queue.append(chi)

  if all([i == 1 for i in visited]):
    return "Yes"
  else:
    return "No"
  
flag = bfs(path,0,visited)

print(flag)

if flag == "Yes":
  for i in range(1,N):
    print(ans[i])

Submission status: Accepted

Solution code:
n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = {}
def trace():
    tasks = [(1, 0)]
    i = 0
    while i < len(tasks):
        no, lv = tasks[i]
        for c in d[no]:
            if c != 1:
                if c not in r or (r[c][1] > lv and r[c][1] != 0):
                    r[c] = (no, lv)
                    tasks.append((c, lv + 1))
        i += 1
trace()

for i in range(2, n):
    if i not in r:
        print('No')
        break
else:
    print('Yes')
    for i in range(2, n +1):
        print(r[i][0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N, M, *AB = map(int, sys.stdin.buffer.read().split())

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

for i in range(M):
  A,B = AB[2*i],AB[2*i+1]
  list_path[A].append(B)
  list_path[B].append(A)

list_bfs = [1]
list_flg = [0 for _ in range(N+1)]
list_flg[1] = 1

while len(list_bfs)>0:
  list_tmp = []
  for i in list_bfs:
    for j in list_path[i]:
      if list_flg[j]==0:
        list_tmp.append(j)
        list_flg[j] = i
  list_bfs = list_tmp

print('Yes')
for i in list_flg[2:]:
  print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N, M, *AB = map(int, sys.stdin.buffer.read().split())

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

for i in range(M):
  A,B = AB[2*i:2*i+2]
  list_path[A].append(B)
  list_path[B].append(A)

list_bfs = [1]
list_flg = [0 for _ in range(N+1)]
list_flg[1] = 1

while len(list_bfs)>0:
  list_tmp = []
  for i in list_bfs:
    for j in list_path[i]:
      if list_flg[j]==0:
        list_tmp.append(j)
        list_flg[j] = i
  list_bfs = list_tmp

print('Yes')
for i in list_flg[2:]:
  print(i)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def bfs(s):
    from collections import deque
    check = [-1] * (n + 1)
    check[s] = 0
    q = deque([s])
    while q:
        now = q.popleft()
        for next in graph[now]:
            if check[next] == -1:
                check[next] = now
                q.append(next)
    return check


n, m = map(int, readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
print('Yes')
for v in bfs(1)[2:]:
    print(v)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
ans = [-1 for i in range(n+1)]
def bfs():
    #start at 1
    que = deque([1])
    while que:
        node = que.popleft()
        for i in adjacent_list[node]:
            if ans[i] == -1:
                que.append(i)
                ans[i] = node
bfs()
print("Yes")
for i in range(2,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
def bfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda n: int(n) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
print("Yes")
print(*bfs(graph, N, 0)[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

def main():
  N, M = list(map(int, input().split(' ')))

  root = [[] for i in range(N+1)]
  for i in range(M):
    A, B = list(map(int, input().split(' ')))
    root[A].append(B)
    root[B].append(A)

  mitisurube = [-1 for i in range(N+1)]
  next_ = deque()
  next_.append(1)

  while next_:
    now_pos = next_.popleft()
    for next_pos in root[now_pos]:
      if mitisurube[next_pos] == -1:
        mitisurube[next_pos] = now_pos
        next_.append(next_pos)
  #print('root')
  #print(*root)
  #print('mitisirube')
  print('Yes')
  print(*mitisurube[2:], sep='\n')

if __name__ == '__main__':
  main()

Submission status: Accepted

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

for i in range(m):
    ta, tb = map(int, input().split())
    dir[ta].append(tb)
    dir[tb].append(ta)

ans = [0]*(n+1)
flag = [False]*(n+1)
flag[1] = True
que = deque([1])
while que:
    #print('que: ', len(que), que)
    now = que.popleft()
    for to in dir[now]:
        if flag[to]:
            continue
        que.append(to)
        flag[to] = True
        ans[to] = now

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

Submission status: Accepted

Solution code:

from collections import deque
def resolve():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(lambda x:int(x)-1, input().split())
        G[x].append(y)
        G[y].append(x)

    dist = [-1]*N
    ans = [0]*N
    q = deque()
    q.append(0)
    while q:
        fm = q.popleft()
        for to in G[fm]:
            if dist[to] != -1:
                continue
            dist[to] += 1
            ans[to] = fm
            q.append(to)

    print("Yes")
    for i in range(1, N):
        print(ans[i] + 1)
        
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    from collections import deque

    n, m = map(int, input().split())
    d = {}
    par = [[] for i in range(n)]
    que = deque()
    for i in range(m):
        a, b = map(int, input().split())
        par[a - 1].append(b)
        par[b - 1].append(a)

    que.append(1)
    while(len(que) > 0):
        label = que.popleft()
        for i in par[label - 1]:
            if i not in d.keys():
                que.append(i)
                d[i] = label

    if len(d) < n:
        print("No")
        return

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

resolve()