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 itertools
# import math
import sys
sys.setrecursionlimit(500*500)
# import numpy as np
from collections import deque

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# A_B = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# edges = [list(map(int,input().split())) for _ in range(M)]
# tree = [[] for _ in range(N + 1)]

# for edge in edges:
#     tree[edge[0]].append([edge[1], edge[2]])
#     tree[edge[1]].append([edge[0], edge[2]])

# depth = [-1] * (N + 1)
# depth[1] = 0

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

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

for edge in edges:
    tree[edge[0]].append(edge[1])
    tree[edge[1]].append(edge[0])

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

d = deque()
d.append(1)

ans = [0] * (N + 1)
while d:
 v = d.popleft()
 for i in tree[v]:
   if depth[i] != -1:
     continue
   depth[i] = depth[v] + 1
   ans[i] = v
   d.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
INF = 1000000
to_room = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    to_room[a].append(b)
    to_room[b].append(a)
dp = [INF] * (n + 1)
dp[1] = 0
seen_room = deque()
seen_room.append(1)
ans = [0] * (n + 1)
while seen_room:
    v = seen_room.popleft()
    for next in to_room[v]:
        if dp[next] <= dp[v] + 1:
            continue
        dp[next] = dp[v] + 1
        ans[next] = v
        seen_room.append(next)
#     print(seen_room)
# print(to_room)
# print(dp)
if 0 in ans[2:]:
    print("No")
else:
    print("Yes")
    for a in ans[2:]:
        print(a)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
B = [[] for i in range(N)]
C = [0 for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  B[a-1].append(b)
  B[b-1].append(a)
d = deque([1])
while len(d):
  p = d.pop()
  for q in B[p-1]:
    if C[q-1] == 0:
      C[q-1] = p
      d.appendleft(q)
print("Yes")
for i in range(1, N):
  print(C[i])

Submission status: Accepted

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

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    dq = deque([])
    traversed = [False for _ in range(N+1)]
    ans = [None for _ in range(N+1)]

    G = {n : set([]) for n in range(1, N+1)}
    for a, b in zip(A,B):
        G[a].add(b)
        G[b].add(a)

    dq.append(1)
    traversed[1] = True

    while dq:
        s = dq.popleft()

        for node in G[s]:
            if not traversed[node]:
                dq.append(node)
                traversed[node] = True
                

                ans[node] = s

    print(YES)
    for s in ans:
        if s != None:
            print(s)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]

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

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

q = deque([1])
signpost = [0] * (N + 1)

while q:
    v = q.popleft()
    for w in conn[v]:
        if signpost[w] == 0:
            signpost[w] = v
            q.append(w)

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

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

d = deque()
d.append(1)

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

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

Submission status: Accepted

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

A = [[] for i in range(N+1)]

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

def BFS():
    q = deque()
    q.append(1)
    pre = [0] * (N+1)
    pre[0] = pre[1] = -1
    while(q):
        x = q.popleft()
        for y in A[x]:
            if pre[y] == 0:
                pre[y] = x 
                q.append(y)
    if 0 in pre:
        print('No')
    else:
        print('Yes')
        for i in range(2,N+1):
            print(pre[i])

BFS()

Submission status: Accepted

Solution code:
def abc168d_double_dots():
    n, m = map(int, input().split())
    path_dict = {}
    for _ in range(m):
        a, b = map(int, input().split())
        if b not in path_dict.keys():
            path_dict[b] = [a]
        else:
            path_dict[b].append(a)
        a, b = b, a
        if b not in path_dict.keys():
            path_dict[b] = [a]
        else:
            path_dict[b].append(a)

    q = [1]
    cnt = 0
    ans = [0] * n
    ans[0] = 1
    while len(q) != 0:
        no = q.pop(0)
        for next_room in path_dict[no]:
            if ans[next_room - 1] == 0:
                ans[next_room - 1] = no
                q.append(next_room)
                cnt += 1

    if cnt != n-1:
        print('No')
        return
    print('Yes')
    for a in ans[1:]:
        print(a)


abc168d_double_dots()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
roads = []
for _ in range(N):
    roads.append([])
for _ in range(M):
    a, b = map(int, input().split())
    roads[a - 1].append(b - 1)
    roads[b - 1].append(a - 1)
visited = [float('inf')] * N
q = deque()
q.append(0)
visited[0] = 0
pre = [-1] * N
while q:
    now_room = q.popleft()
    for next_room in roads[now_room]:
        if visited[next_room] != float('inf'):
            continue
        visited[next_room] = visited[now_room] + 1
        if pre[next_room] == -1:
            pre[next_room] = now_room + 1
        q.append(next_room)
# print(*roads)
# print(*pre)

print('Yes')
for i in range(1, N):
    print(pre[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys
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

input = sys.stdin.readline

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

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

    visited = bfs(graph, N, 0)[1:]
    if all(visited):
        print("Yes")
        print(*visited, sep="\n")
    else:
        print("No")


main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

print('Yes')

q = deque()
d = [-1] * N
d[0] = 0
q.append(0)

while q:
    x = q.popleft()
    for i in route[x]:
        if d[i] == -1:
            d[i] = x + 1
            q.append(i)

for i in range(1, N):
    print(d[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys
N, M = list(map(int, input().split()))
ans = [-1] * N
visited = [False] * N
dq = deque([0])
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
while dq:
   i = dq.popleft()
   if visited[i]:
      continue
   visited[i] = True
   next_rs = path[i]
   for j in range(len(next_rs)):
      if not visited[next_rs[j]]:
         dq.append(next_rs[j])
         if ans[next_rs[j]] == -1:
            ans[next_rs[j]] = i
if sum(visited) == N:
   print('Yes')
   for i in range(N):
      if i == 0:
         continue
      else:
         print(ans[i]+1)
else:
   print(-1)

Submission status: Accepted

Solution code:
#ABC168D
from collections import deque

n,m=map(int,input().split())
lst=[[] for i in range(n)]
visited=[False for i in range(n)]
ans=[0]*n

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

Q=deque()
Q.append((0))
visited[0]=True

while Q:
  v=Q.popleft()
  for i in lst[v]:
        if visited[i]==False:
              visited[i]=True
              ans[i]=v
              Q.append((i))

print('Yes')

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

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])

Submission status: Accepted

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

to = [[] for i in range(100010)]

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

dist = [0] * (N+1)
q = [1]
dist[0] = -1
#print(to[:4])

dist = [0] * N
pre = [0] * N

while len(q) != 0:
    a = q.pop(0)
    for i in to[a]:
        if dist[i-1] == 0:
            dist[i-1] = dist[a-1] + 1
            pre[i-1] = a
            q.append(i)
    #print(q)

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

Submission status: Accepted

Solution code:
#import math
import collections
n, m = map(int, input().split( ))
lis = [[] for _ in range(n+1)]
for _ in range(m):
  a,b = map(int, input().split( ))
  lis[a].append(b)
  lis[b].append(a)
#print(lis)
ans = [0]*(n+1)
q = collections.deque()
q.append(1)
count = [0]*(n+1)
#1の時は動かない
count[1] = 1
while len(q) != 0:
  v = q.popleft()
#  print(lis[v], count)
  #まずは1につながっている部屋を探索その後順に探索
  for u in lis[v]:
    if count[u] == 0:
      count[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:
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
mark = [-1]*(n+1)
mark[0] - 0
mark[1] = 0


d = deque()
d.append(1)

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

if '-1' in mark:
    print('No')
else:
    print('Yes')
    print(*mark[2:], sep='\n')

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)

#  print(graph)

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

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if mark[i] != -1:
            continue
        mark[i] = v
        d.append(i)
if mark.count(-1) > 0:
    print("No")
else:
    print("Yes")
    ans = mark[2:]
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

n,m=nii()

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

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

que=deque()
que.append(0)

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

if -1 in ans:
  print('No')
else:
  print('Yes')
  for i in ans[1:]:
    print(i+1)

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

d = deque()
d.append(1)

#BFS実行部分
while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = v
        d.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

for a, b in 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:
# 幅優先探索, BFS

from collections import deque

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

neighbor = [[] for _ in range(n)]
for edge in edges:
    neighbor[edge[0]-1].append(edge[1]-1)  # 1- → 0-index
    neighbor[edge[1]-1].append(edge[0]-1)

queue = deque()
queue.append(0)

back = [-1] * n  # visitしたかどうかを兼ねる
back[0] = 0
while len(queue) > 0:
    vertex = queue.popleft()
    for nei in neighbor[vertex]:
        if back[nei] == -1:
            back[nei] = vertex
            queue.append(nei)
        
print('Yes')
for i in back[1:]:
    print(i+1)  # 0- → 1-index

Submission status: Accepted

Solution code:
from sys import stdin,stdout
from collections import defaultdict
def bfs(src):
    q=[src]
    par=[-1]*(n+1)
    vis=[0]*(n+1)
    ans=[]
    while q:
        cur=q.pop(0)
        for neigh in g[cur]:
            if not vis[neigh]:
                vis[neigh]=1
                q+=[neigh]
                par[neigh]=cur
    for i in range(2,n+1):
        if par[i]==-1:
            print('No')
            return
        ans+=[par[i]]
    print('Yes')
    for v in ans:
        print(v)
for i in range(1):#int(stdin.readline())):
    # n=int(stdin.readline())
    g=defaultdict(list)
    n,e=list(map(int,stdin.readline().split()))
    for _ in range(e):
        a,b=map(int,stdin.readline().split())
        g[a]+=[b]
        g[b]+=[a]
    bfs(1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

def input():
  return sys.stdin.readline()

N,M=map(int,input().split())
L=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  L[a-1].append(b)
  L[b-1].append(a)
A=[0]*N
a,b = N,0
d=deque([])
for l in L[0]:
  d.append((1,l))
while a>b:
  i,j=d.popleft()
  if A[j-1]==0:
    b+=1
    A[j-1]=i
    for l in L[j-1]:
      d.append((j,l))
if a==b:
  print("Yes")
  for i in range(1,N):
    print(A[i])
else:
  print("No")

Submission status: Accepted

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

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

d = deque()
d.append(1)
ans = [0 for _ in range(n+1)]
while d:
    v = d.popleft()
    for i in route[v]:
        if dist[i] != 0:
            continue
        dist[i] = dist[v]+1
        ans[i] = v
        d.append(i)

if len(dist[2:]) > 0:
    print('Yes')
    print(*ans[2:], sep="\n")
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(s):
    seen = [0]*(N+1)
    d = [0]*(N+1)
    prev = [0]*(N+1)
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return prev
  
prev = bfs(1)

print('Yes')
print(*prev[2:])

Submission status: Accepted

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

dist[1] = 1
q = deque([1])
while q:
    x = q.popleft()
    for j in graph[x]:
        if dist[j] == -1:
            q.append(j)
            dist[j] = x
ans = dist[2:]
if -1 in ans:
    print("No")
else:
    print("Yes")
    print(*ans, sep = "\n")

Submission status: Accepted

Solution code:
from collections import deque
[N,M] = list(map(int,input().split()))
AB = []
for i in range(M):
    AB.append(list(map(int,input().split())))

#そこから直で行けるところをまとめる
ikeru = [[] for i in range(N)]
for i in range(M):
    ikeru[AB[i][0]-1].append(AB[i][1]-1)
    ikeru[AB[i][1]-1].append(AB[i][0]-1)
# print('ikeru:',ikeru)



que = deque([])
que.append(0)
# print('que ini:',que)
out=[10**6]*N
out[0]=0

while que:
    p = que.popleft()
    # print('p,que:',p,que)

    for next in ikeru[p]:
        # print('next,out:',next,out)
        if out[next]==10**6:
            que.append(next)
            out[next]=p+1


# print(out)
print('Yes')
for i in range(1,N):
    print(out[i])

Submission status: Accepted

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

ars = [0] * N
todo = deque([0])
done = {0}
while todo:
    p = todo.popleft()
    for np in G[p]:
        if np in done:
            continue
        todo.append(np)
        ars[np] = p + 1
        done.add(np)

if len(done) == N:
    print("Yes")
    for i in range(1, N):
        print(ars[i])
else:
    print("No")

Submission status: Accepted

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

class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [-1] * self.n
        for start in range(self.n):
            if self.parent[start] == -1:
                cnt += 1
                self.bfs(start + self.decrement, save=True)
        return cnt

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def path_list(self, start=1):
        """
        :return: スタート地点から最短経路で進んだ時の、各頂点の一個前に訪問する頂点番号
                訪問しない場合は -1 を返す
        """
        self.distance_list(start)
        if self.decrement:
            start -= 1
        return list(p + self.decrement for p in self.parent[1:])

##################################################################################################

N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

res = graph.path_list()
if -1 in res:
    print("No")
else:
    print("Yes")
    print(*res, sep="\n")

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
from collections import deque
import marshal


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [-1] * self.n
        for start in range(self.n):
            if self.parent[start] == -1:
                cnt += 1
                self.bfs(start + self.decrement, save=True)
        return cnt

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

##################################################################################################

N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

if -1 in graph.distance_list():
    print("No")
else:
    print("Yes")
    print(*list(p+1 for p in graph.parent[1:]), sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
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 = deque([1])
closed = [False] * (N+1)
closed[1] = True
Ans = [0] * (N+1)
while q:
    v = q.popleft()
    for u in G[v]:
        if not closed[u]:
            closed[u] = True
            q.append(u)
            Ans[u] = v
print("Yes")
print("\n".join(map(str, Ans[2:])))

Submission status: Accepted

Solution code:
from collections import deque

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

ans=[0]*(N+1)
d=deque([1])
while d:
  c=d.popleft()
  for g in G[c]:
    if not ans[g]:
      d.append(g)
      ans[g]=c

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+1)]
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)

ans=[0]*(N+1)
d=[1]
while d:
  c=d.pop(0)
  for g in G[c]:
    if not ans[g]:
      d.append(g)
      ans[g]=c

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())

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

G = {i:[] for i in range(N+1)}
for a,b in AB:
    G[a].append(b)
    G[b].append(a)
    
parent = [0]*(N+1)
parent[0]==-1
parent[1]==-1
q = deque()
q.append(1)
while len(q)>0:
    room = q.popleft()
    child = G[room]
    
    for i in child:
        if parent[i] == 0:
            parent[i] = room
            q.append(i)
    
    
if min(parent[2:])==0:
    print('No')
else:
    print('Yes')
    for i in parent[2:]:
        print(i)

Submission status: Accepted

Solution code:
import queue

def main():
    n, m = map(int, input().split())
    graph = [[]for i in range(n + 1)]
    a = None
    b = None
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    sign = [0 for i in range(n + 1)]
    vis = [False for i in range(n + 1)]
    q = queue.Queue(0)
    q.put(1)
    vis[1] = True
    while q.empty() == False:
        u = q.get()
        for val in graph[u]:
            if vis[val] == False:
                vis[val] = True
                q.put(val)
                sign[val] = u
    for i in range(2, n + 1):
        if sign[i] == 0:
            print("No")
            return
    print("Yes")
    for i in range(2, n + 1):
        print(sign[i])



if __name__ == "__main__":
    main()

Submission status: Accepted

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

q = deque([0])
d = [-1]*n
d[0] = 0
ans = [0]*n
print("Yes")

while q:
    p = q.popleft() # 先に入れた要素を取り出す
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node) # リストへの追加
        else:
            if d[node] + 1 == d[p]: # 深さdに対してd+1の関係であるかのチェック
                ans[p] = node + 1

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