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 python3
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline

    N, M = map(int, input().split())
    G = [[] for _ in [0] * (N + 1)]
    for _ in [0] * M:
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    
    q = deque([1])
    depth = [0 for _ in [0] * (N + 1)]
    while q:
        v = q.popleft()
        for nv in G[v]:
            if depth[nv] == 0:
                # depth[nv] = depth[v] + 1
                depth[nv] = v
                q.append(nv)
    if 0 in depth[2:]:
        print('No')
        return
    else:
        print('Yes')
        for guide in depth[2:]:
            print(guide)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a = [0] * (m + 1)
b = [0] * (m + 1)
road = [[] for _ in range(n + 1)]

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

ans = [-1] * (n + 1)
ans[0] = 0
ans[1] = 0

q = deque()
q.appendleft(1)

while len(q):
    i = q.pop()
    for j in road[i]:
        if ans[j] == -1:
            ans[j] = i
            q.appendleft(j)

if ans.count(-1) != 0:
    print("No")
    exit()
else:
    print("Yes")
    print(*ans[2:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
ab=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    ab[a].append(b) 
    ab[b].append(a)
ans=[0]*(n+1)
ans[1]=1
que=deque()
que.append(1)
while que:
    x=que.popleft()
    for i in ab[x]:
        if ans[i]==0:
            ans[i]=x
            que.append(i)
print("Yes")
for j in range(2,n+1):
  print(ans[j])

Submission status: Accepted

Solution code:
import collections

def main():
    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)

    check = [0]*(n+1)
    ans = [0]*(n+1)
    q = collections.deque()
    q.append(1)
    check[1] = 1

    while len(q) != 0:
        v = q.popleft()
        for u in g[v]:
            #print(u)
            if check[u] == 0:
                check[u] = 1
                ans[u] = v
                q.append(u)

    for i in range(2,n+1):
        if ans[i] == 0:
            print('No')
            return

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

main()

Submission status: Accepted

Solution code:
from collections import defaultdict

G = defaultdict(set)
N, M = [int(_) for _ in input().split()]
for _ in range(M):
    A, B = [int(_) for _ in input().split()]
    G[A].add(B)
    G[B].add(A)

f = [-1 for _ in range(N+1)]
f[1] = 0

pool = set([1])
np = set()
cnt = 0
while pool:
    np = set()
    for p in pool:
        for v in G[p]:
            if f[v] == -1:
                f[v] = p
                cnt += 1
                np.add(v)
    pool = np

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

Submission status: Accepted

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

while True :
    if len(visit)==0 :
        break
    x=visit.popleft()
    for i in A[x] :
        if depth[i]==-1 :
            depth[i]=x+1
            visit.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
root = [[] for _ in range(n)]
adj = [-1 for _ in range(n)]
for _ in range(m):
  r,c = map(int, input().split())
  root[r-1].append(c-1)
  root[c-1].append(r-1)
  
explor = deque()
explor.append(0)

while explor:
  tmp = explor.popleft()
  for i in root[tmp]:
    if adj[i]==-1:
      adj[i] = tmp
      explor.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
l=[[] for i in range(n)]#各部屋とつながっている部屋
#print(l,ab)
for a,b in ab:
    l[a-1].append(b)
    l[b-1].append(a)
result=[-1]*n
q=deque([1])
#print(l,result)
while True:
    if len(q)==0:
        break
    x=q.popleft()
    for j in l[x-1]:
        if result[j-1]==-1:
            result[j-1]=x
            q.append(j)
    #print(q,result)

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

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(m):
    tmp = list(map(int,input().split()))
    turo[tmp[0]].append(tmp[1])
    turo[tmp[1]].append(tmp[0])

sirusi[1] = 0

q = deque()
q.append(1)

while len(q) != 0:
    x = q.popleft()
    for i in turo[x]:
        if sirusi[i] == -1:
            sirusi[i] = x
            q.append(i)

print('Yes')
for i in range(n+1):
    if i != 0 and i != 1:
        print(sirusi[i])

Submission status: Accepted

Solution code:
import collections

n,m = map(int,input().split())
g = [[] for i in range(n+1)]
for i in range(m):
  a,b = map(int,input().split())
  g[a].append(b)
  g[b].append(a)
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 j in g[v]:
    if check[j] == 0:
      check[j] = 1
      ans[j] = v
      q.append(j)
print('Yes')
for k in range(2,n+1):
  print(ans[k])

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
mark=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  a-=1;b-=1
  g[a].append(b)
  g[b].append(a)
D=deque([0])
visited=[False]*n
visited[0]=True
while D:
  v=D.popleft()
  for i in g[v]:
    if visited[i]:
      continue
    visited[i]=True
    mark[i]=v
    D.append(i)
print("Yes")
for i in range(1,n):
  print(mark[i]+1)

Submission status: Accepted

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

pairs = [[] for _ in range(N)]  # pairs[i]:i+1と直接つながっている部屋のリスト
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0] - 1].append(input_list[1] - 1)
    pairs[input_list[1] - 1].append(input_list[0] - 1)

ans = [0] * (N - 1)
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了
done = [True] + [False] * (N - 1) # 探索済リスト
todo = [0]

while n_ans < N - 1:
    for n in todo:
        for m in pairs[n]:
            if not done[m]:
                done[m] = True
                ans[m - 1] = n + 1
                n_ans += 1
                todo.append(m)

print('Yes')
print(*ans, sep='\n')

Submission status: Accepted

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

pairs = [[] for _ in range(N + 1)]  # pairs[i]:iと直接つながっている部屋のリスト
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0]].append(input_list[1])
    pairs[input_list[1]].append(input_list[0])

ans = [0] * (N + 1)
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了
done = [False] * (N + 1) # 探索済リスト
todo = [1]

while n_ans < N - 1:
    for n in todo:
        for m in pairs[n]:
            if not done[m]:
                done[m] = True
                ans[m] = n
                n_ans += 1
                todo.append(m)

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

Submission status: Accepted

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

pairs = [[] for _ in range(N + 1)]  # pairs[i]:iと直接つながっている部屋のリスト
for _ in range(M):
    input_list = list(map(int, input().split()))
    pairs[input_list[0]].append(input_list[1])
    pairs[input_list[1]].append(input_list[0])

ans = [0 for _ in range(N + 1)]
n_ans = 0   # ansを埋めた回数 -> N-1になったら終了
done = [False for _ in range(N + 1)]  # 探索済リスト
todo = [1]

while n_ans < N - 1:
    for n in todo:
        for m in pairs[n]:
            if not done[m]:
                done[m] = True
                ans[m] = n
                n_ans += 1
                todo.append(m)

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

Submission status: Accepted

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

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

for _ in range(1000009):

    for bangou in tansakuheya:

        for heya in ikisaki[bangou]:
            if ans[heya]==0:
                ans[heya]=bangou
                tmp.append(heya)

    tansakuheya=tmp
    tmp=[]


    if not tansakuheya:
        break

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

Submission status: Accepted

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

for _ in range(m):
    a,b = map(int, input().split())
    ikisaki[a].append(b)
    ikisaki[b].append(a)
ans=[0]+[1]+[0]*(n-1)
tansakuheya=deque([1])
tmp=deque()

for _ in range(1000009):

    for bangou in tansakuheya:

        for heya in ikisaki[bangou]:
            if ans[heya]==0:
                ans[heya]=bangou
                tmp.append(heya)

    tansakuheya=tmp.copy()
    tmp=deque()


    if not tansakuheya:
        break

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

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
dist=[10**15 for i in range(N)]
prev=[-1 for i in range(N)]
dist[0]=0
q=[]
heapq.heappush(q,(0,0))
while(len(q)>0):
    c,v=heapq.heappop(q)
    if dist[v]<c:
        continue
    for d in G[v]:
        if dist[d]>dist[v]+1:
            dist[d]=dist[v]+1
            heapq.heappush(q,(dist[d],d))
            prev[d]=v
print("Yes")
for i in range(1,N):
    print(prev[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

g = [set() for _ in range(N)]
for a, b in AB:
    a, b = a-1, b-1
    g[b].add(a)
    g[a].add(b)

mark = [-1]*N
mark[0] = 0
q = deque([0])
while q:
    t = q.popleft()

    for c in g[t]:
        if mark[c] == -1:
            mark[c] = t
            q.append(c)

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

Submission status: Accepted

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


def main():
  N, M = list(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)

  from_ = [0]*(N+1)

  q = deque([1])
  seen = set()
  seen.add(1)

  while len(q):
    now = q.popleft()
    for next_ in G[now]:
      if next_ not in seen:
        seen.add(next_)
        q.append(next_)
        from_[next_] = now

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


if(__name__ == '__main__'):
  main()

Submission status: Accepted

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

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

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

d = deque()
d.append(1)
while d:
    v = d.popleft()
    for i in Graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        pre[i] = v
        d.append(i)
ans = dist[0:]
print('Yes')
for j in range(2, len(pre)):
    print(pre[j])

Submission status: Accepted

Solution code:
from collections import deque

def resolve():
    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)

    INF = 1001001001
    dist = [INF] * N
    prev = [-1] * N
    dist[0] = 0
    q = deque([0])
    while len(q) > 0:
        i = q.popleft()
        for j in to[i]:
            if dist[j] != INF:
                continue
            dist[j] = dist[i] + 1
            prev[j] = i
            q.append(j)

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque


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

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

    que = deque()
    hint = [0] * N
    seen = [False] * N

    seen[0] = True
    que.appendleft(0)

    # BFS
    while que:
        v = que.popleft()
        for nv in to[v]:
            if seen[nv]:
                continue
            que.append(nv)
            hint[nv] = v + 1
            seen[nv] = True

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

import copy

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

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

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

rets = [0 for i in range(N)]
visited = [0] * N
visited[0] = 1

D = deque([0])

while D:
    v = D.popleft()
    for i in road[v]:
        if visited[i]: continue
        visited[i] = 1
        rets[i] = v
        D.append(i)

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

Submission status: Accepted

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

ans =[[0,0] for _ in range(M)]

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

to_list = [[] for _ in range(N)]
prev = [0]*N
for a,b in AB:
  to_list[a-1].append(b-1)
  to_list[b-1].append(a-1)

que = [0]
marked = {0}
for i in que:
  for j in to_list[i]:
    if j in marked: 
      continue
    que.append(j)
    marked.add(j)
    prev[j] = i+1
print("Yes")
print(*prev[1:],sep = "\n")

Submission status: Accepted

Solution code:
from collections import deque
def BFS(N,M,List):
    Graph = [[] for T in range(N+1)]
    for NodeM in range(0,M):
        Graph[List[NodeM][0]].append(List[NodeM][1])
        Graph[List[NodeM][1]].append(List[NodeM][0])

    Distance = [-1]*(N+1)
    Distance[0] = 0
    Distance[1] = 0
    From = [0]*(N+1)
    From[1] = 1

    Deque = deque()
    Deque.append(1)
    while Deque:
        V = Deque.popleft()
        for NodeV in Graph[V]:
            if Distance[NodeV]==-1:
                Distance[NodeV] = Distance[V]+1
                Deque.append(NodeV)
                From[NodeV] = V

    return Distance[1:],From[1:]
  
N,M = (int(X) for X in input().split())
List = [[] for T in range(0,M)]
for T in range(0,M):
    List[T] = [int(X) for X in input().split()]
Distance,From = BFS(N,M,List)
print('\n'.join(['Yes']+[str(X) for X in From[1:]]))

Submission status: Accepted

Solution code:
from queue import Queue
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)
parents = [None] * (n+1)
parents[1] = 0
parents[0] = 0
def bfs():
    q = Queue()
    q.put(1)
    while not q.empty():
        u = q.get()
        for v in adj[u]:
            if parents[v] is None:
                parents[v] = u
                q.put(v)
bfs()     
#print(parents)
if None in parents:
    print("No")
else:
    print("Yes")
    for i in range(2, n+1):
        print (parents[i])

Submission status: Accepted

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

neighbors = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in neighbors.keys():
    neighbors.update({a:set()})
  if b not in neighbors[a]:
    neighbors[a].add(b)
  if b not in neighbors.keys():
    neighbors.update({b:set()})
  if a not in neighbors[b]:
    neighbors[b].add(a)
#print(neighbors)
lst = [0] * (n - 1)
visited = set()
queue = [[0, set([1])]]
while queue:
  #print(queue)
  pre_room, rooms = queue.pop(0)
  #print(pre_room, rooms)
  for room in rooms:
    if room in visited:
      continue
    if lst[room - 2] == 0 and room != 1:
      lst[room - 2] = pre_room
    visited.add(room)
    next_rooms = set()
    for nei in neighbors[room]:
      next_rooms.add(nei)
    next_rooms = [room, next_rooms]
    queue.append(next_rooms)
if 0 in lst:
  print('No')
else:
  print('Yes')
  for i in range(n - 1):
    print(lst[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

deq=deque()
dic=defaultdict(list)

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

sign=[-1]*(n+1)
sign[1]=0
for i in dic[1]:
    deq.append(i)
    sign[i]=1

while deq:
    p = deq.popleft()
    for i in dic[p]:
        if sign[i]!=-1:
            continue
        else:
            sign[i]=p
            deq.append(i)

bl = True
for i in range(2, n+1):
    if sign[i]<0:
        bl = False

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(graph, n, s):
  visited = [0]*n # 移動回数を保持
  visited[s] = 1 # 部屋1の探索は完了としている
  q = deque([s]) # 探索用にdequeを設定し、初期位置としてs(0)を設定する
  while q:
    node = q.popleft() # 先頭から順番に実行
    for i in graph[node]: # 各部屋から行ける別の部屋を確認
      if not visited[i]: # 値が"0"の場合に処理を実行
        visited[i] = node + 1 # 部屋1からの移動回数を保持する
        q.append(i) # 移動先の部屋をqに格納し、探索を継続する
  return visited

n,m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda x: int(x)-1, input().split())
  graph[a].append(b)
  graph[b].append(a)
  
visited = bfs(graph, n, 0)[1:] # 幅優先探索を行い、部屋1以外の結果を取得する
if all(visited):
  print("Yes")
  print(*visited, sep="\n") 
else:
  print("No")

Submission status: Accepted

Solution code:
import queue
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
ans=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=queue.Queue()
q.put(1)
d[1]=0
while not q.empty():
  now=q.get()
  for to in e[now]:
    if d[to]==INF:
      ans[to]=now
      d[to]=d[now]+1
      q.put(to)
print('Yes')
for i in ans[2:]:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque

mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

N,M = MI()
links = [[] for _ in range(N)]

for _ in range(M):
    a, b = MI()
    a -= 1
    b -= 1
    links[a].append(b)
    links[b].append(a)

ans = [-1] * N
ans[0] = 0
q = deque([(0, 0)])
while q:
  room, prev = q.popleft()
  for next_ in links[room]:
    if ans[next_] < 0:
      ans[next_] = room+1
      q.append((next_, room))
print("Yes")
for i in range(1,N):
  print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
def bfs(N,start,dp):
  visited=[0]*N
  visited[start]=1
  que=deque([start])
  while que:
    a=que.popleft()
    for i in dp[a]:
      if not visited[i]:
        visited[i]=a+1
        que.append(i)
  return visited
N,M=map(int,input().split())
dp=[[] for i in range(N)]
for _ in range(M):
  A,B=map(int,input().split())
  dp[A-1].append(B-1)
  dp[B-1].append(A-1)
visited=bfs(N,0,dp)[1:]
if all(visited):
  print('Yes')
  for i in visited:
    print(i)
else:
  print('No')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n,m = MI()
graph = [[] for _ in range(n+1)]

for i in range(m):
    a,b = MI()
    graph[a].append(b)
    graph[b].append(a)

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

d = deque()
d.append(1)
ans = [0]*(n+1)
while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        ans[i] = v
        dist[i] = 0
        d.append(i)
print("Yes")
for i in ans[2:]:
    print(i)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,m = [int(x) for x in stdin.readline().rstrip().split()]

d = {}
for i in range(m):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]

    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)

    if b not in d:
        d[b] = [a]
    else:
        d[b].append(a)

sol = {}

m = [1]
while True:
    next_m = []
    for mm in m:
        b = d[mm]
        for bb in b:
            if bb not in sol:
                sol[bb] = mm
                next_m.append(bb)

    if len(next_m) == 0: break
    m = next_m

sol = sorted(sol.items())

print("Yes")
for v in sol[1:]:
    print(v[1])

Submission status: Accepted

Solution code:

from collections import deque

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

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

dist = [10 ** 9] * (N + 1)
dist[1] = 0
ans = [0] * (N + 1)
q = deque([1])

while q:
    u = q.popleft()
    for v in graph[u]:
        if dist[v] > dist[u] + 1:
            dist[v] = dist[u] + 1
            ans[v] = u
            q.append(v)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

ls = deque([0])
ans = [-1] * N
ans[0] = 0
while len(ls) > 0:
    v = ls.popleft()

    for next_v in G[v]:
        if ans[next_v] != -1:
            continue
        ans[next_v] = v
        ls.append(next_v)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def resolve():
    n, m = map(int, input().split())
    aisle = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        aisle[a - 1].append(b - 1)
        aisle[b - 1].append(a - 1)

    d = deque()
    d.append(0)

    room_depths = [-1] * 100010
    room_depths[0] = 0
    room_inds = [-1] * 100010

    # BFS
    while d:
        room = d.popleft()
        for next_room in aisle[room]:

            # 隣接する頂点で、まだ数字が書かれていない頂点に、現在の頂点の数字+1を書く
            if room_depths[next_room] == -1:
                d.append(next_room)
                room_depths[next_room] = room_depths[room] + 1
                room_inds[next_room] = room + 1

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

Submission status: Accepted

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

ad={} #近接リスト
for n in range(N):
    ad[n+1]=set([])
    
depth={} #深さ
for n in range(N):
    depth[n+1]=0
    
parent={}
for n in range(N):
    parent[n+1]=0
    
visit_dict={} #発見しているか保持（-1:未発見、0:発見、1:訪問済）
for n in range(N):
    visit_dict[n+1]=-1
    
for m in range(M):
    a,b=list(map(int,input().split()))
    ad[a].add(b)
    ad[b].add(a)

# 幅優先探索
from collections import deque

que = deque([1])
visit = deque([])
depth[1]=1
visit_dict[1]=0

i=0
while len(que) > 0:
    i+=1
    start=que[0]
    for _ in ad[start]:
        if visit_dict[_] != -1:
            continue
        else:
            depth[_]=depth[start]+1
            parent[_]=start
            visit_dict[_]=0
            que.append(_)  
            
    visit_dict[start]=1
    visit.appendleft(que.popleft())
            

print('Yes')
for p in list(parent.keys())[1:]:
    print(parent[p])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
input = sys.stdin.readline

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

que = deque()
dist = [float('inf')] * n
prev = [-1] * n
dist[0] = 0
que.append(0)
while que:
    now = que.popleft()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            prev[edge] = now + 1
            que.append(edge)


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
# import sys
# input = sys.std.readline

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

que = deque()
dist = [float('inf')] * n
prev = [-1] * n
dist[0] = 0
que.append(0)
while que:
    now = que.popleft()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            prev[edge] = now + 1
            que.append(edge)


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

Submission status: Accepted

Solution code:
from collections import deque

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

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

xs = [0] * (n + 1)
q = deque()
q.append(1)
seen = {1}
while len(q) > 0:
    v = q.popleft()
    for t in eg[v]:
        if t in seen:
            continue
        q.append(t)
        seen.add(t)
        xs[t] = v
print("Yes")
print(*xs[2:], sep="\n")

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline


N,M = list(map(int,input().split()))
road = [[] for _ in range(N+1)]
flag = [-1 for _ in range(N+1)]
flag[1]=0
for i in range(M):
    a,b = map(int,input().split())
    road[a].append(b)
    road[b].append(a)
q = collections.deque([1])
while q:
    now = q.popleft()
    for r in road[now]:
        if flag[r] == -1:
            flag[r] = now
            q.append(r)
            
print('Yes')
for i in range(2,N+1):
    print(flag[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys
n,m = map(int,input().split())
 
turo = [[] for i in range(n)]
q = deque()
his = [False]*n
for i in range(m):
    a,b = map(int,input().split())
    turo[a-1].append(b-1)
    turo[b-1].append(a-1)
 
par = [i for i in range(n)]
rank = [sys.maxsize for i in range(n)]
rank[0] = 0
q.append(0)
 
while len(q) > 0:
    #print(q)
    room = q.popleft()
    
    if not his[room] :
        his[room] = True
    else:
        continue
    for room2 in turo[room]:
        if rank[room] < rank[room2]:
            q.append(room2)
            par[room2] = room
            rank[room2] = rank[room]+1
 
if len(his) < n:
    print("No")
    exit()
 
print("Yes")
for i in range(1,n):
    print(par[i]+1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
route = [[] for _ in range(N)]
sign = [0]*N

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

marked = {0}
q = [0]
for i in q:
    for j in route[i]:
        if j in marked:
            continue
        q.append(j)
        marked.add(j)
        sign[j] = i+1

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