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:
N,M = map(int,input().split())

V = [[] for _ in range(N)]

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

from collections import deque

q = deque([0])

ans = [-1]*N
ans[0] = 0

while q:
    v = q.popleft()
    for nv in V[v]:
        if ans[nv] == -1:
            ans[nv] = v + 1
            q.append(nv)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
ans = [0] * (N+1)
for i in range(M):
    f, t = map(int, input().split())
    graph[f].append(t)
    graph[t].append(f)

D = deque([1])
checked = [0] * (N+1)
checked[0] = 1
checked[1] = 1
while D:
    n = D.popleft()
    for i in graph[n]:
        if checked[i] == 1:
            continue
        checked[i] = 1
        ans[i] = n
        D.append(i)

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

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
d = {}
for i in range(m):
  a,b = map(int, input().split())
  if a in d:
    l = d[a]
    l.append(b)
    d[a] = l
  else:
    d[a] = [b]
  if b in d:
    l = d[b]
    l.append(a)
    d[b] = l
  else:
    d[b] = [a]
dpth = {}
dpth[1] = 0
l = [1]
ans = [0]*(n-1)
while(len(l)>0):
  l_ = []
  for i in l:
    dpth_ = dpth[i]
    for j in d[i]:
      if j not in dpth:
        ans[j-2] = i
        dpth[j] = dpth_+1
        l_.append(j)
  l = l_
print("Yes")
for i in ans:
  print(i)

Submission status: Accepted

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

adj = [[] for i in range(N)]
signs = [-1 for i in range(N)]
# not_patrolled = set(range(1, N))

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

queue = deque([0])

while len(queue) > 0:
  cur = queue.popleft()
  for i in adj[cur]:
    if signs[i] == -1:
      queue.append(i)
      signs[i] = cur
      # not_patrolled.remove(i)

if all([sign != -1 for sign in signs[1:]]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")

Submission status: Accepted

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

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]=0

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

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())
G = [[] for _ in range(N)]

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

q = deque([0])
dist = [-1]*N
dist[0] = 0

while q:
  v = q.popleft()
  for nv in G[v]:
    if dist[nv] == -1:
      dist[nv] = v+1
      q.append(nv)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N, M = [int(i) for i in input().strip().split()]
    graph = [[] for _ in range(N)]
    sign = [0] * N
    for _ in range(M):
        a, b = [int(i) for i in input().strip().split()]
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    candidates = deque([0])
    visited = [False] * N
    visited[0] = True
    while len(candidates) > 0:
        v = candidates.popleft()
        for i in graph[v]:
            if visited[i]:
                continue
            visited[i] = True
            sign[i] = v
            candidates.append(i)
    print("Yes")
    for i in sign[1:]:
        print(i+1)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

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

root = 1
q = [root]
checked = [0] * (N + 1)
checked[root] = 1
order = []
D = [0 for _ in range(N+1)]
d = 0
while q:
    x = q.pop(0)
    d = D[x]
    for y in graph[x]:
        if checked[y]:
            continue
        D[y] = d + 1
        checked[y] = 1
        q.append(y)

ans = [0 for _ in range(N+1)]
for a, b in AB:
    d_a, d_b = D[a], D[b]
    if d_a < d_b:
        ans[b] = a
    elif d_a > d_b:
        ans[a] = b

print('Yes')
print('\n'.join(map(str, ans[2:])))

Submission status: Accepted

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

adj = [list() for _ in range(N)]

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

parent = [None]*N
queue = deque([0])
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if parent[v] is None:
            parent[v] = u
            queue.append(v)

print('Yes')
print(*(x+1 for x in parent[1:]), sep='\n')

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x,'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x,'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x,'x') # rev => int(res, 16)
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(n=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## const ##
MOD=10**9+7
## libs ##
import itertools as it
import functools as ft
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#
def main():
    n, m = MII()
    ab = [MIIZ() for _ in range(m)]
    g = [[] for _ in range(n)]
    for a,b in ab:
        g[a].append(b)
        g[b].append(a)
    dist = [-1]*n
    dq = deque()
    dist[0] = 0
    dq.append(0)
    res = [0]*n
    while dq:
        v = dq.popleft()
        for nv in g[v]:
            if dist[nv] != -1: continue
            res[nv] = v
            dist[nv] = dist[v] + 1
            dq.append(nv)
    res = [i+1 for i in res[1:]]
    print('Yes')
    print(*res,sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans_list=[-1]*n

queue=[0]

while queue:
    qi=queue.pop(0)
    for gi in g[qi]:
        if ans_list[gi]==-1:
            queue.append(gi)
            ans_list[gi]=qi

print("Yes")
for ans in ans_list[1:]:
    print(ans+1)

Submission status: Accepted

Solution code:
from collections import deque

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

before=[None] * n
before[0] = -1
q=deque([0])
while len(q):
  node=q.popleft()
  for nxt in adj[node]:
    if before[nxt] is not None:
      continue
    q.append(nxt)
    before[nxt] = node
print("Yes")
for i in range(1, n):
  print(before[i] + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*100000)
n, m = map(int,input().split())
mark = [-2] * (n-1)
dist = [0] * (n-1)
path = [[] for _ in range(n-1)]
path0 = []

for _ in range(m):
    a, b = map(lambda x: int(x)-2, input().split())
    if a == -1:
        path0.append(b)
        dist[b] = 1
        mark[b] = -1
    elif b == -1:
        path0.append(a)
        dist[a] = 1
        mark[a] = -1
    else:
        path[a].append(b)
        path[b].append(a)

while len(path0) > 0:
    i = path0.pop(0)
    d = dist[i]
    for p in path[i]:
        if dist[p] > d + 1 or dist[p] == 0:
            dist[p] = d + 1
            mark[p] = i
            path0.append(p)

print("Yes")
for i in mark: print(i+2)

Submission status: Accepted

Solution code:
import queue
N, E = map(int, input().split(" "))
adj = [ [] for _ in range(N) ]  
for _ in range(E) :
    u,v = map(int, input().split(" "))
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)
ans = [""]*N
q = queue.Queue() 
q.put( (0, -1 ) )

visited = [False]*N
visited[0] = True
while not q.empty() :
    u, p = q.get()
    ans[u] = p+1
    for v in adj[u] :
        if visited[v] :
            continue
        q.put( (v, u) ) 
        visited[v] = True

for a in ans :
    if a==0 :
        print("Yes")
    else :
        print(a)

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np
from collections import Counter
import math

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

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
while count < N:
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
print('Yes')
for i in ans[2:]:
    print(i)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque as d

N, M = map(int, readline().split())
m = map(int, read().split())
AB = zip(m, m)
graph = [[] for _ in range(N + 1)]

for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
que = d([1])
ans = [0]*(N+1)
while que:
  x = d.popleft(que)
  for i in graph[x]:
    if ans[i] != 0:
        continue
    ans[i] = x
    que.append(i)
if 0 in ans[2:]:
    print('No')
    exit()
print('Yes')
print('\n'.join(map(str, ans[2:])))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

INF = float('inf')

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

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    prevs = [None] * numV
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2 in adjList[vNow]:
            c2 = cNow + 1
            if c2 < costs[v2]:
                costs[v2] = c2
                prevs[v2] = vNow
                heappush(PQ, (c2, v2))
    return (costs, prevs)

costs, prevs = Dijkstra(adjL, 0)

#print('costs:', costs)
#print('prevs:', prevs)

print('Yes')
print('\n'.join(map(lambda x: str(x+1), prevs[1:])))

Submission status: Accepted

Solution code:
import collections
n,m = list(map(int,input().split()))
ans = [0]*n
graph = [[] for _ in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
D = collections.deque([0])
visited = [False]*n
visited[0]=True

while D:
    v = D.popleft()
    for i in graph[v]:
        if visited[i]:continue
        visited[i]=True
        ans[i]=v
        D.append(i)
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 i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    
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:
import queue

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

q = queue.Queue()
q.put(1)
shirube = [0] * (n+1)
shirube[1] = 1

while not q.empty():
    v = q.get()
    for i in cave[v]:
        if shirube[i] == 0:
            shirube[i] = v
            q.put(i)

cnt = 0
for i in range(2, n+1):
    if shirube[i] == 0:
        cnt += 1
if cnt > 0:
    print("No")
else:
    print("Yes")
    for i in range(2, n+1):
        print(shirube[i])

Submission status: Accepted

Solution code:
# from collections import deque

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

ans = [0]*(N+1)
now = [1]
# next = deque()
next = []
 
while len(now):
    # print('now', now)
    for x in now:
        for y in L[x]:
            if (ans[y] == 0):
                ans[y] = x
                next.append(y)
    now = next.copy()
    # now.popleft()
    next = []
 
print("Yes")
for x in range(2, N+1):
    print(ans[x])

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np
from collections import Counter
import math

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

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
# if 0 in ans[1:]:
#     print('No')
#     exit()
# else:
print('Yes')
for i in ans[2:]:
    print(i)

Submission status: Accepted

Solution code:
def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque
def main():
  n,m=LI()
  edge=[[]for i in range(n)]
  for i in range(m):
    a,b=LI()
    edge[a-1]+=b-1,
    edge[b-1]+=a-1,    
  dq=deque([0])
  ans=[-1]*n
  while dq:
    g=dq.popleft()
    for i in edge[g]:
      if ans[i]==-1:
        ans[i]=g+1
        dq.append(i)
  yes()
  print(*ans[1:])
main()

Submission status: Accepted

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[[0,10**18] for _ in range(n+1)]
q=collections.deque()
q.append((1,0))
check=[0]*(n+1)
check[1]=1
while len(q)!=0:
  v,d=q.popleft()
  for u in g[v]:
    if ans[u][1]>d:
      ans[u][0]=v
      ans[u][1]=d
    if check[u]==0:
      check[u]=1
      q.append((u,d+1))
print('Yes')
for i in range(2,n+1):
  print(ans[i][0])

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 1000000007


INF = float("inf")
import heapq


ans = []
def dijkstra_heap(G, s, n):
    d = [INF] * n           # 始点sから各頂点への最短距離
    used = [False] * n
    d[s] = 0
    used[s] = False

    edgelist = []
    for edge in G[s]:
        heapq.heappush(edgelist, [edge[0], edge[1], s])

    while len(edgelist) > 0:
        minedge = heapq.heappop(edgelist)       # 距離最小の辺を取り出す
        dist, v, pv = minedge[0], minedge[1], minedge[2]
        
        if used[v]:
            continue
        ans[v] = pv
        d[v] = dist
        used[v] = True

        # v から伸びてる辺を edgelist に入れる
        for edge in G[v]:
            cost, nv = edge[0], edge[1]
            if used[nv]:
                continue
            heapq.heappush(edgelist, [d[v] + cost, nv, v])
    
    return d


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

    for _ in range(N):
        ans.append(-1)
    dijkstra_heap(G, 0, N)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())

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

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

def make_shirube(n):
    target_list = N_list[n]
    next_list = []
    for room in target_list:
        if ans_list[room] == -1:
            ans_list[room] = n
            next_list.append(room)
    return next_list

next_loop_list = make_shirube(1)
while len(next_loop_list) > 0:
    temp_list = []
    for room in next_loop_list:
        temp_list.append(make_shirube(room))
    next_loop_list = [flatten for inner in temp_list for flatten in inner]
if ans_list[1:].count(-1) == 0:
    print("Yes")
    print("\n".join(map(str, ans_list[2:])))
else:
    print("No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

import queue

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

    connedted_room_list = [ [] for i in range(N)] # ここでNとMを書き間違えていた。
    for i in range(M):
        A, B = map(int, input().split())
        connedted_room_list[A-1].append(B-1)
        connedted_room_list[B-1].append(A-1)

    answer_list = [ -1 for i in range(N)]
    answer_list[0] = 0

    next_rooms_queue = queue.Queue()
    next_rooms_queue.put(0)
    now_room = int()
    while not next_rooms_queue.empty():
        now_room = next_rooms_queue.get()
        for i in connedted_room_list[now_room]:
            if answer_list[i] == -1:
                answer_list[i] = now_room
                next_rooms_queue.put(i)

    
    is_escapable = True
    '''
    for i in range(1, N):
        if answer_list[i] == -1:
            is_escapable = False
            break
    '''

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    d[a].add(b)
    d[b].add(a)

queue=deque([1])
vs = set([1])
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)
print("Yes")
for x in parents[2:]:
    print(x)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    
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:
#d
n,m=map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
maze = []
inf = 9999999
dist = [inf]* n
dist[0] = 0
queue = []
answer = [0]*n

goto = [[] * 1 for i in range(n)]
for i in range(len(ab)):
    goto[ab[i][0]-1].append(ab[i][1]-1)
    goto[ab[i][1]-1].append(ab[i][0]-1)

queue.extend([0])

while queue != []:
    go = queue.pop(0)
    for h in goto[go]:
        if dist[h] == inf:
            queue.append(h)
            dist[h] = dist[go]+1
            answer[h] =go+1
            

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

Submission status: Accepted

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

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


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


ans = [-1] * (N + 1)
ans[1] = 0
ans[0] = 0
stack = deque([1])
def dfs():
    while len(stack) > 0:
        now = stack.popleft()
        for r in road[now]:
            if ans[r] == -1:
                ans[r] = now
                stack.append(r)
dfs()

temp = set(ans)
# 更新されていないもの(部屋に行けないもの)が一つでもあれば，"No"
if ((-1) in temp):
    print("No")
else:
    print("Yes")
    for a in ans[2:]:
        print(a)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def dijkstra(s):
    used = [1] * N
    dp = [INF] * N
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

INF = 10 ** 18
N, M = map(int, input().split())
cost = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    cost[a].append([1, b])
    cost[b].append([1, a])
dp1 = dijkstra(0)
for i in dp1:
    if i == INF:
        print('No')
        exit()
print('Yes')
for i in range(1, N):
    tmp = dp1[i] - 1
    for j in cost[i]:
        if dp1[j[1]] == tmp:
            print(j[1] + 1)
            break

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split(" "))
load = {i:[] for i in range(1, n+1)}
for _ in range(m):
    a, b = map(int, input().split(" "))
    load[a].append(b)
    load[b].append(a)

queue = deque([1])
visited = {1: 1}

while len(queue) != 0:
    curr = queue.popleft()
    for _next in load[curr]:
        if visited.get(_next, -1) == -1:
            visited[_next] = curr
            queue.append(_next)

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

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right

n,m=n1()
ab=n3(m)

node=defaultdict(list)
for a,b in ab:
    node[a].append(b)
    node[b].append(a)
    
p=deque([1])
d=[0]*(n+1)
while len(p)>0:
    c=p.popleft()
    for i in node[c]:
        if d[i]==0:
            d[i]=c
            p.append(i)
            
print("Yes")
for i in range(2,n+1):
    print(d[i])

Submission status: Accepted

Solution code:
import math

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

hist= []
visited_pos = [-1] * n

#初期情報
#print(ab)
ts = {}
for el in ab:
  wk = ts.get(el[0]) 
  if wk is None:
    sss  = set()
    ts[el[0]] = sss
  ts[el[0]].add(el[1])
  wk = ts.get(el[1]) 
  if wk is None:
    sss  = set()
    ts[el[1]] = sss
  ts[el[1]].add(el[0])
#print(ts)


#幅優先探索
def tsk(pos):
  wk = ts.get(pos)
  if ts.get(pos) is None:
    return
  else:
    #print(pos,wk)
    for e in wk:
      if visited_pos[e-1] < 0:
        visited_pos[e-1] = pos # idx 値　0-
        hist.append(e) # 実値　1-

idx = 0
hist.append(1) #実値　1-
while True:
  if idx >= len(hist):
    break
  else:
    tsk(hist[idx])
    idx += 1
#print(hist)
#print(visited_pos)
ans = 'Yes'
for i in range(n):
  if visited_pos[i] == -1:
    ans = 'No'
    break

print(ans)
if ans == 'Yes':
  for i in range(1,n):
    print(visited_pos[i])

Submission status: Accepted

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

q = deque()
q.append(1)
d = defaultdict(lambda : float("inf"))
d[1] = 0
while q:
    u = q.popleft()
    for v in D[u]:
        if d[v] == float("inf"):
            d[v] = u
            q.append(v)

if len(d) == N:
    print("Yes")
else:
    print("No")
    exit()
for i in range(2, N+1):
    print(d[i])

Submission status: Accepted

Solution code:
import sys
from collections import deque

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


def solve():
    N, M = map(int, rl().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    ans = [0] * N
    que = deque([0])
    while que:
        cur = que.popleft()
        for child in graph[cur]:
            if ans[child] == 0:
                ans[child] = cur + 1
                que.append(child)
    
    if any(ansi == 0 for ansi in ans[1:]):
        print('No')
    else:
        print('Yes')
        print(*ans[1:], sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np
from collections import Counter
import math

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

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
if 0 in ans[1:]:
    print('No')
    exit()
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Submission status: Accepted

Solution code:
def main():
  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)
  
  l=deque([1])
  ans=[-1]*n
  while l:
    x=l.popleft()
    for i in ab[x]:
      if ans[i-1]==-1:
        ans[i-1]=x
        l.append(i)
  print('Yes')
  for i in ans[1:]:
    print(i) 
    
if __name__=='__main__':
  main()