Problem:


Score: 400 points

Problem Statement

There is a cave.

The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.

It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.

Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.

If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.

Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

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

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

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

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

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

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

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

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

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

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

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

Thus, the objective is satisfied.

Sample Input 2

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

Sample Output 2

Yes
6
5
5
1
1

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



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


Sample output:
Yes
1
2
2

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

n, m = map(int, readline().split())
ab = map(int, read().split())

graph = [[] for _ in range(n+1)]
for a, b in zip(ab, ab):
    graph[a].append(b)
    graph[b].append(a)

ans = [0] * (n + 1)
visited = [0] * (n + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in graph[v]:
        if visited[w]:
            continue
        visited[w] = 1
        ans[w] = v
        q.append(w)
 
print('Yes')
print(*ans[2:], sep='\n')

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

 
n, m = map(int, readline().split())
 
adj = [[] for _ in range(n)]
 
for i in range(m):
    a, b = map(int, readline().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
 
 
import heapq
 
MAX = 10 ** 9 + 5
 
visited = [False for _ in range(n)]
dist = [MAX for _ in range(n)]
path = [0 for _ in range(n)]
 
def dji(start):
    dist[start] = 0
    q = [(0, 0)]
    while len(q) > 0:
        v = heapq.heappop(q)
        if visited[v[1]]:
            continue
        visited[v[1]] = True
        for u in adj[v[1]]:
            if dist[v[1]] + 1 < dist[u]:
                dist[u] = dist[v[1]] + 1
                path[u] = v[1] + 1
                heapq.heappush(q, (dist[u], u))
 
dji(0)
if all(visited):
    print("Yes")
    for i in path[1:]:
        print(i)
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
neighbor=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  neighbor[a].append(b)
  neighbor[b].append(a)
def bfs(start,arrcnt):
  queue=deque([start])
  d=[None]*arrcnt
  d[start]=0
  while queue:
    l=queue.popleft()
    for i in neighbor[l]:
      if d[i]==None:
        d[i]=l+1
        queue.append(i)
  return d
d=bfs(0,n)
if None in d:
  print("No")
else:
  print("Yes")
  for i in range(1,n):
    print(d[i])

Submission status: Accepted

Solution code:
#ABC168D
def main():
    import sys
    from collections import defaultdict
    from collections import deque
    N, M = map(int, sys.stdin.readline().split())
    AB = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    #print(AB)
    
    edge = defaultdict(list)
    for ab in AB:
        edge[ab[0]-1] +=[ab[1]-1]
        edge[ab[1]-1] +=[ab[0]-1]
    
    #print(edge)
    flag = [-1 for i in range(N)]
    def bfs(start, queue=deque([])):
        queue += [start]
        flag[start] =1
        while queue:
            now = queue.popleft()
            for ch in edge[now]:
                if flag[ch]==-1:
                    flag[ch] = now+1
                    queue.append(ch)
            
            
    
    bfs(0)
    print('Yes')
    for f in flag[1:]:
        print(f)
        
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
ans=[0]*(n+1)
adj=[[] for _ in range(n+1)]
for i in range(m):
    u,v=map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)
que=deque([1])
vis=[0 for _ in range(n+1)]
vis[1]=1
while que:
    t=que.popleft()
    #print(t)
    for i in adj[t]:
        #print(i)
        if vis[i]==1:
            continue
        vis[i]=1
        ans[i]=t
        que.append(i)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 8)

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

aisles = [[] for _ in range(n)]
visited = [1] + [0] * (n - 1)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    aisles[a].append(b)
    aisles[b].append(a)

q = deque([0])

while q:
    v = q.pop()
    for nex in aisles[v]:
        if visited[nex] != 0:
            continue
        visited[nex] = v + 1
        q.appendleft(nex)

print("Yes")
for point in visited[1:]:
    print(point)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())
    adj = [[]for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)
    parent = [0]*(n+1)
    visited = [0]*(n+1)
    root = 1
    visited[root] = 1
    q = deque([root])
    while q:
        v = q.popleft()
        for i in adj[v]:
            if visited[i]:
                continue
            visited[i] = 1
            parent[i] = v
            q.append(i)
    print('Yes')
    print(*parent[2:], sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
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)
from collections import deque  
queue = deque([0])
d = [None] * N
d[0] = 0 
while queue:
  v = queue.popleft()
  for i in g[v]:
    if d[i] is None:
      d[i] = d[v] + 1
      queue.append(i)
  
l=[0]*(N-1)
for i in range(1,N):
  for j in g[i]:
    if d[j]==(d[i]-1):
      l[i-1]=j+1
      break
if 0 in l:
  print('No')
else:
  print('Yes')
  for i in range(len(l)):
    print(l[i])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
path = [[]for i in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1,input().split())
    path[a] += [b]
    path[b] += [a]
ans = [-1 for i in range(n)]
depth = [[] for i in range(n)]
visited = [False for i in range(n)]
d=0
ans[0] = -2
depth[0]+=[0]
visited[0]=True
while False in visited:
    for i in depth[d]:
        for j in path[i]:
            if not visited[j]:
                ans[j] = i+1
                depth[d+1] += [j]
                visited[j] = True
    d += 1
print("Yes")
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
lis = [0]*(n+1)
c = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
    
que = deque([1])
check = [0 for i in range(n+1)]
check[1] = 1
while que:
    now = que.popleft()
    nx = c[now]
    for i in nx:
        if check[i] == 1:
            continue
        check[i] = 1
        lis[i] = now
        que.append(i)
if 0 in lis[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join(map(str, lis[2:])))

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
lis = [0]*(n+1)
c = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
    
que = deque([1])
check = [0 for i in range(n+1)]
check[1] = 1
while que:
    now = que.popleft()
    nx = c[now]
    for i in nx:
        if check[i] == 1:
            continue
        check[i] = 1
        lis[i] = now
        que.append(i)
if 0 in lis[2:]:
    print("No")
else:
    print("Yes")
    for i in lis[2:]:
        print(i)

Submission status: Accepted

Solution code:
#見ずに解けていない
from collections import defaultdict
from collections import deque

graph=defaultdict(list)

n,m=map(int,input().split())
for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans=defaultdict(lambda:-1)
que=deque([1])
ans[1]=1
while len(que)>0:
    a=que.popleft()
    for b in graph[a]:
        if ans[b]==-1:
            ans[b]=a
            que.append(b)
if len(ans)!=n:
    print("No")
else:
    print("Yes")
    for b in range(2,n+1):
        print(ans[b])

Submission status: Accepted

Solution code:
from collections import deque
 
 
def main():
    N, M, *AB = map(int, open(0).read().split())
 
    graph = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(AB)] * 2):
        graph[a].append(b)
        graph[b].append(a)
 
    # bfs
    queue = deque([1])
    sign = [0] * (N + 1)
    sign[1] = 1
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not sign[v]:
                sign[v] = u
                queue.append(v)
 
    if all(sign[2:]):
        print("Yes")
        print("\n".join(map(str, sign[2:])))
    else:
        print("No")
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
MAX = 1000000000
import queue
dist = [MAX for i in range(N)]
pre = [-1 for i in range(N)]
To = [[] for i in range(N)]#indexに向かっている部屋番号の集合

que = queue.Queue()

for _ in range(M):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    To[a].append(b)
    To[b].append(a)
dist[0] = 0
que.put(0)
while(not que.empty()):
    v = que.get()
    for u in To[v]:
        if pre[u] != -1: continue
        dist[u] = dist[v] + 1
        que.put(u)
        pre[u] = v
        
        
print('Yes')
for i in pre[1:N]:
    print(i+1)

Submission status: Accepted

Solution code:
import queue
N,M=map(int,input().split())
adj=[[] for s in range(N+1)]
parent=[-1]*(N+1)
for i in range(M):
    A,B=map(int,input().split())
    adj[A].append(B)
    adj[B].append(A)
q=queue.Queue()
q.put((1,0))
while(not q.empty()):
    x,p=q.get()
    if parent[x]!=-1:
        continue
    parent[x]=p
    for next in adj[x]:
        if parent[next]==-1:
            q.put((next,x))
print('Yes')
for k in parent[2:]:
    print(k)

Submission status: Accepted

Solution code:
import queue
N,M = map(int,input().split())
adj = [[]for i in range(N+1)] #どこの部屋とどこの部屋が繋がっているかを表す、N＋1の理由は、部屋番号とインデックスが一個ずれてるから
parent = [-1] * (N+1) #-1なら未訪問、N+1な理由は同様である
for m in range(M):
    a,b = map(int,input().split())
    adj[a].append(b) #お互いの場所を書く、繋がっているかを記録する
    adj[b].append(a) #こっちにもお互いの場所を書く
q = queue.Queue() #記録するようのトンネルみたいなもの、入ったものから出ていく感じ、自分の部屋番号、親の部屋番号（ただ作っただけ）
q.put((1,0)) # 部屋1の親は部屋0と考える（二個ぶち込んでる) 
while(not q.empty()): #もう探索の候補がqueueに入ってこなくなったら終わり
    x, p = q.get() #探索の候補を受け取る、一回取り出したらもう抜ける
    if parent[x] != -1: #-1じゃなくて変えられていたら訪問済みでスキップ
        continue
    parent[x] = p #親を示しているリストを更新する
    for next in adj[x]: #今いる場所に繋がっている部屋を全てループする
        if parent[next] == -1: # 未訪問なら
            q.put((next,x)) # 探索候補に追加、これがもう全て-1じゃなくて回りきったら終わりとする
print ('Yes') # 必ず目標は達成できる
for p in parent[2:]: # 部屋2以降の親（前の部屋）
    print(p)

Submission status: Accepted

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

#隣接リスト
road=[[] for i in range(n+1)]
for i in range(m):
    road[road_input[i][0]].append(road_input[i][1])
    road[road_input[i][1]].append(road_input[i][0])

from collections import deque
q=deque([1])
ans=[-1 for i in range(n)]
while len(q)>0:
  p=q.popleft()
  for i in road[p]:
    if ans[i-1]== -1:
      ans[i-1]=p
      q.append(i)

print("Yes")
for j in range(1,n):
    print(ans[j])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
gra=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  gra[a-1].append(b-1)
  gra[b-1].append(a-1)
from collections import deque
d=deque()
d.append(0)
visited=[False]*n
visited[0]=True
dep=[0]*n
while d:
  g=d.popleft()
  for i in gra[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    dep[i]=dep[g]+1
route=[0]*(n-1)
for i in range(1,n):
  for t in gra[i]:
    if dep[t]==dep[i]-1:
      route[i-1]=t+1
      break
print('Yes')
print(*route)

Submission status: Accepted

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

def dijkstra(N):
  signs = [None] * (N+1)
  signs[0] = -1
  steps = [float('inf')] * (N+1)
  visited = [False] * (N+1)

  # step,from,cur_node
  q = [(0, -1, 1)]
  while q:
    step,p,cur_node = heapq.heappop(q)
    steps[cur_node] = step
    signs[cur_node] = p
    visited[cur_node] = True

    for nei in adj[cur_node]:
      if visited[nei]: continue
      if step+1 < steps[nei]:
        steps[nei] = step+1
        heapq.heappush(q, (step+1, cur_node, nei))
  return signs

signs = dijkstra(N)[2:]
if float('inf') in signs:
  print("No")
else:
  print("Yes")
  for s in signs:
    print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
q = deque([0])
Dequeue = lambda: q.popleft()
Enqueue = lambda x: q.append(x)
n, m = map(int, input().split())
l = [[] for _ in [0]*n]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    l[a] += [b]
    l[b] += [a]
ans = [-1]*n
while q:
    v = Dequeue()
    for i in l[v]:
        if ans[i] < 1:
            ans[i] = v+1
            Enqueue(i)
if -1 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

graph = defaultdict(list)

V, E = map(int, input().split())
for _ in range(E):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

ans = defaultdict(lambda: -1)
que = deque([1])
ans[1] = 1
while len(que) > 0:
    u = que.popleft()
    for v in graph[u]:
        if ans[v] == -1:
            ans[v] = u
            que.append(v)

if len(ans) != V:
    print('No')
else:
    print('Yes')
    for v in range(2, V + 1):
        print(ans[v])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = {}
for i in range(m):
    am, bm = map(int, input().split())
    if am not in graph:
        graph[am] = [bm]
    else:
        graph[am].append(bm)
    if bm not in graph:
        graph[bm] = [am]
    else:
        graph[bm].append(am)
guide = {1: 0}
visited = [1]
i = 0
while True:
    for j in graph[visited[i]]:
        if j not in guide.keys():
            guide[j] = visited[i]
            visited.append(j)
    i += 1
    if i == len(visited):
        break

if len(visited) == n:
    print("Yes")
    for x in range(2, n+1):
        print(guide[x])
else:
    print("No")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = {}
for i in range(m):
    am, bm = map(int, input().split())
    if am not in graph:
        graph[am] = [bm]
    else:
        graph[am].append(bm)
    if bm not in graph:
        graph[bm] = [am]
    else:
        graph[bm].append(am)
guide = {1: 0}
visited = [1]
i = 0
while True:
    # flag = False
    for j in graph[visited[i]]:
        if j not in guide.keys():
            guide[j] = visited[i]
            visited.append(j)
            # flag = True
    i += 1
    # if flag and i == len(visited):
    #     break
    if i == len(visited):
        break

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
graph = {}
for i in range(0, m):
    am, bm = map(int, input().split())
    if am not in graph:
        graph[am] = [bm]
    else:
        graph[am].append(bm)
    if bm not in graph:
        graph[bm] = [am]
    else:
        graph[bm].append(am)
signs = {1:0}
current = [1]
while current:
    node = current.pop(0)
    for j in graph[node]:
        if j not in signs:
            signs[j] = node
            current.append(j)  
if len(signs) == n:
    print("Yes")
    for x in range(2, n+1):
        print(signs[x])
else:
    print("No")

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
graph = {}
for i in range(0, m):
    am, bm = map(int, input().split())
    if am not in graph:
        graph[am] = [bm]
    else:
        graph[am].append(bm)
    if bm not in graph:
        graph[bm] = [am]
    else:
        graph[bm].append(am)
signs = {1:0}
current = [1]
i = 0
while True:
    flag = 0
    for j in graph[current[i]]:
        if j not in signs:
            signs[j] = current[i]
            current.append(j)
            flag = 1
    i+=1
    if flag == 0 and i == len(current):
        break
    
if i == n:
    print("Yes")
    for x in range(2, n+1):
        print(signs[x])
else:
    print("No")

Submission status: Accepted

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

from collections import defaultdict
pth = defaultdict(list)

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

sign = [0] * (N+1)
sign[0] = 1
sign[1] = 1
q = [1]
hist = set()

while len(q) != 0:
    key = q.pop(0)

    for n in pth[key]:
        if sign[n] == 0:
            sign[n] = key
            # print("sign[",n,"]=",key)
            q.append(n)
        else:
            continue
    # print(q)

if not all([x != 0 for x in sign[2:]]):
    print("No")
else:
    print("Yes")
    for s in sign[2:]:
        print(s)

Submission status: Accepted

Solution code:
import numpy as np

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

network = [[] for _ in range(N+1)]
res = [0 for _ in range(N+1)]
distance = [N+1 for _ in range(N+1)]
distance[1] = 0


for _ in range(M):
    i, j = map(int, input().split())
    network[i].append(j)
    network[j].append(i)


from collections import deque


n = 0
s = []
queue = deque([1])
while n < N:
    top = queue.popleft()
    for i in network[top]:
        if distance[i] > distance[top]+1:
            distance[i] = distance[top]+1
            res[i] = top
            queue.append(i)
    n += 1


print("Yes")  
for r in res[2:]:
    print(r)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
lst=[[] for i in range(n)]
ans=[0 for i in range(n)]
for i in range(m):
    a,b=list(map(int,input().split()))
    lst[a-1].append(b-1)
    lst[b-1].append(a-1)
que=deque([])
que.append(1)
while que:
    p=que.popleft()
    for i in lst[p-1]:
        if ans[i]==0:
            ans[i]=p
            que.append(i+1)
print("Yes")
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

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


def depth_first_seach(idx_start):
	queue = deque([idx_start])
	distance = [None]*N
	to_go = [None]*N
	distance[idx_start] = 0
	while queue:
		v = queue.popleft()
		for i in g[v]:
			if distance[i] is None:
				to_go[i] = v
				distance[i] = distance[v] + 1
				queue.append(i)
				
	return to_go, distance

to_go, distance = depth_first_seach(0)

for i in range(1,N):
	if to_go[i] == None:
		print("No")
		exit()

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

queue=deque([0])

while queue:
  v=queue.popleft()
  for nv in graph[v]:
    if (dist[nv]!=-1):
      continue
    dist[nv]=v
    queue.append(nv)

print("Yes")

for i in dist[1:]:
  print(i+1)

Submission status: Accepted

Solution code:
# Problem D - Double Dots

from collections import deque

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

# initialization
nodes = [0] * N
visit = [0] * N
edges_dic = {}
for i in range(M):
    A, B = map(int, input().split())
    if A in edges_dic:
        edges_dic[A].append(B)
    else:
        edges_dic[A] = [B]

    if B in edges_dic:
        edges_dic[B].append(A)
    else:
        edges_dic[B] = [A]
queue = deque([1])

# search
while len(queue)>=1:
    q = queue.popleft()
    visit[q-1] = 1
    next_n = edges_dic[q]
    for n in next_n:
        if visit[n-1]==0:
            nodes[n-1] = q
            visit[n-1] = 1
            queue.append(n)

# output
print("Yes")
for i in range(1, N):
    print(nodes[i])

Submission status: Accepted

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

	for i in range(m):
		a, b = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	d = deque()
	dist = [-1] * (n+1)
	dist[0] = 0
	dist[1] = 0
	d.append(1)

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

	if graph[1] == "":
		print("No")
	else:
		print("Yes")
		for i in range(2,n+1):
			for g in graph[i]:
				if dist[g] == dist[i]-1:
					print(g)
					break


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# BFSして終わり 必ず存在するので
from collections import deque

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

stamp = [0] * (n + 1)
stamp[0], stamp[1] = -1, -1
queue = deque()
for tv in t[1]:
    queue.append((tv, 1))
    stamp[tv] = 1

while len(queue) > 0:
    cur_node, pre_node = queue.popleft()
    for nex_node in t[cur_node]:
        if stamp[nex_node] != 0:
            continue
        stamp[nex_node] = cur_node
        queue.append((nex_node, pre_node + 1))

print("Yes")
for i in stamp[2:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

class Graph():
    def __init__(self, directed:bool, nord_count:int):
        self.directed = directed
        self.degree = [0 for _ in range(nord_count)]
        self.edges = [[] for _ in range(nord_count)]
        self.edge_count = 0
        self.nord_count = nord_count


    def insert_edge(self, x, y, directed:bool):
        edge = EdgeNode(y=y, weight=None, edge_node = None)
        self.edges[x].append(edge)
        self.degree[x] += 1
        if directed == False:
            self.insert_edge(y, x, True)
        else:
            self.edge_count += 1

    def print_graph(self):
        for i in range(self.nord_count):
            for edge in self.edges[i]:
                print(i, edge.y)

class EdgeNode():
    def __init__(self, y, weight, edge_node):
        self.y = y
        self.weight = weight
        self.edge_node = edge_node

N, M = [int(i) for i in input().split()]
graph = Graph(directed=False, nord_count = N)
for i in range(M):
    A, B  = [int(i) for i in input().split()]
    graph.insert_edge(x=A-1, y=B-1, directed=False)

signpost = [None for _ in range(N)]
found = [False for _ in range(N)]
found[0] = True
current_node = 0
previous_node = 0
queue = deque([[previous_node, current_node]])
while len(queue) != 0:
    previous_node, current_node = queue.popleft()
    signpost[current_node] = previous_node
    for edge in graph.edges[current_node]:
        if found[edge.y] == False:
            found[edge.y] = True
            queue.append([current_node, edge.y])
signpost = signpost[1:]
if None in signpost:
    print('No')
else:
    print('Yes')
    for i in signpost:
        print(i+1)

Submission status: Accepted

Solution code:
from collections import deque
dic={}
n,m=map(int,input().split())
nod=[[]]
keep=[0]*n
for i in range(n-1):
  nod.append([])
for i in range(m):
  a,b=map(int,input().split())
  nod[a-1].append(b)
  nod[b-1].append(a)
use=deque()
use.append(1)
for i in range(0,10**100):
  if bool(use):
    sss=use.popleft()
    for j in nod[sss-1]:
      if not j in dic:
        keep[j-1]=sss
        use.append(j)
        dic[j]=1
  else:
    break

keep.pop(0)
print("Yes")
for x in keep:
  print(x)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import Queue

def main():
    # n = int(input())

    n, m = [int(s) for s in input().split()]

    # edge = defaultdict(bool)

    # あるノードと接続しているノード一覧
    edge_to_k = defaultdict(set)

    for i in range(m):
        a, b = [int(s) for s in input().split()]
        # edge[(a, b)] = True
        # edge[(b, a)] = True

        edge_to_k[a].add(b)
        edge_to_k[b].add(a)

    # 道しるべ
    ans = {}
    ans[1] = 1 # 便宜的

    queue = Queue()
    queue.put(1)

    while(not queue.empty()):
        to_node = queue.get()

        # 取り出した部屋につながる部屋にもし道しるべが付いていない場合、道しるべを付ける
        for k in edge_to_k[to_node]:
            if k not in ans:
                sys.stderr.write('on {}. put {}\n'.format(to_node, k))
                queue.put(k)
                ans[k] = to_node

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

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

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

N,M = [int(x) for x in input().split()]
next =[set() for _ in range(N+1)]

for i in range(M):
    A,B = [int(x) for x in input().split()]
    next[A].add(B)
    next[B].add(A)

opened = deque()
opened.append(1)

closed = [False] * (N+1)
prev = [-1] * (N+1)
prevlen = [float('inf')] * (N+1)
prevlen[1] = 0

while len(opened) != 0:
    target = opened.popleft()
    closed[target] = True
    for n in next[target]:
        if closed[n] == False:
            opened.append(n)
            closed[n] = True
        if prevlen[n] > prevlen[target]+1:
            prev[n] = target
            prevlen[n] = prevlen[target]+1


print('Yes')
# for i in range(2,N+1):
#     print(prev[i])
print(" ".join([str(x) for x in prev[2:]]))

Submission status: Accepted

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

N,M = [int(x) for x in input().split()]
next =[set() for _ in range(N+1)]

for i in range(M):
    A,B = [int(x) for x in input().split()]
    next[A].add(B)
    next[B].add(A)

opened = deque()
opened.append(1)

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

while len(opened) != 0:
    target = opened.popleft()
    for n in next[target]:
        if prev[n] == -1:
            opened.append(n)
            prev[n] = target


print('Yes')
# for i in range(2,N+1):
#     print(prev[i])
print(" ".join([str(x) for x in prev[2:]]))

Submission status: Accepted

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

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

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

while que:
  q = que.popleft()
  for i in ab[q]:
    if ans[i] == -1:
      que.append(i)
      ans[i] = q

print("Yes")

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)] # 隣接リスト

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = v
                queue.append(i)
    return d

# 0からの各頂点の距離
d = bfs(0)
print('Yes')
for i in range(1, n):
    print(d[i] + 1)

Submission status: Accepted

Solution code:
import queue

N, M = map(int, input().split())
adj = [[] for i in [0]*N] # 隣接リスト
for i in [0]*M:
    a, b = map(int, input().split())
    adj[a-1].append(b)
    adj[b-1].append(a)

que = queue.Queue()
que.put(1)
guide = [-1]*(N)
 
while not que.empty():
    x = que.get()
    for y in adj[x-1]:
        if guide[y-1] == -1:
            que.put(y)
            guide[y-1] = x


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

Submission status: Accepted

Solution code:
import queue

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

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

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

dist = [-1 for i in range(N)]
que = queue.Queue()

dist[0] = 0
que.put(0)


while not que.empty():
    v = que.get()
    for nv in graph[v]:
        if dist[nv] != -1:
            continue

        dist[nv] = v
        que.put(nv)


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

Submission status: Accepted

Solution code:
from collections import deque


n, m = map(int, input().split())
edg = [[] for i in range(n+1)]
ans = [-1]*(n+1)


for _ in range(m):
	u, v = map(int, input().split())
	edg[u].append(v)
	edg[v].append(u)



def bfs():
	q = deque()
	q.append(1)
	ans[1] = 1

	while q:
		top = q.popleft()
		for child in edg[top]:
			if ans[child] == -1:
				ans[child] = top
				q.append(child)


bfs()

if -1 in ans[1:]:
	print("No")
else:
	print("Yes")
	print("\n".join(map(str, ans[2:])))