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

N, M = map(int, input().split())
dist = [-1] * N
dist[0] = 0
G = [[] for i in range(N)]
prev = [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)
    

que = deque([0])

while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
        prev[w] = v
print("Yes")
for i in range(1, len(prev)):
    print(prev[i]+1)

Submission status: Accepted

Solution code:
from queue import Queue as que
q=que()
n,m=map(int,input().split())
e=[[] for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    e[a-1].append(s-1);e[s-1].append(a-1)
table=[0]*(n)
table[0]=1
ok=0
q.put(0)
while not q.empty():
    now=q.get()
    for to in e[now]:
        if table[to]==0:
            table[to]=now+1
            q.put(to)
            ok+=1
if n-1==ok:
    print("Yes",*table[1:],sep="\n")
else:print("No")

Submission status: Accepted

Solution code:
from collections import deque as que
q=que()
n,m=map(int,input().split())
e=[[] for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    e[a-1].append(s-1);e[s-1].append(a-1)
table=[0]*n
ok=0
table[0]=1
q.append(0)
while len(q):
    now=q.popleft()
    for to in e[now]:
        if table[to]==0:
            table[to]=now+1
            q.append(to)
            ok+=1
if n-1==ok:
    print("Yes",*table[1:],sep="\n")
else:print("No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

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

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

q = deque([0])
while q:
    now = q.popleft()
    for v in path[now]:
        if ans[v] == -1:
            ans[v] = now
            q.append(v)
print('Yes')
for i in ans[1:]:
    print(i+1)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
from heapq import heappush, heappop, heapify

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	G = defaultdict(lambda: [])
	n, m = rli()
	for _ in range(m):
		u, v = rli()
		G[u].append(v)
		G[v].append(u)
	Q = deque([])
	seen = defaultdict(lambda: False)
	Q.appendleft((1, -1)) #curr node, prev node
	posts = [-1 for _ in range(n + 1)]
	while Q:
		for _ in range(len(Q)):
			curr, prev = Q.pop()
			if seen[curr]: continue
			seen[curr] = True
			posts[curr] = prev
			for nbhr in G[curr]:
				if seen[nbhr]: continue
				Q.appendleft((nbhr, curr))
	print("Yes")
	for i in range(2, n+1):
		print(posts[i])
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def resolve():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split()))for i in range(m)]
    ans = [0] * n
    edge = [[]for _ in range(n)]
    for a, b in ab:
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)
    visited = {0}
    stack = [0]
    for i in stack:
        for j in edge[i]:
            if j in visited:
                continue
            stack.append(j)
            visited.add(j)
            ans[j] = i + 1
    print("Yes")
    print('\n'.join(map(str, ans[1:])))


resolve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split()))for i in range(m)]
ans = [0] * n
edge = [[]for _ in range(n)]
for a, b in ab:
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
visited = {0}
stack = [0]
for i in stack:
    for j in edge[i]:
        if j in visited:
            continue
        stack.append(j)
        visited.add(j)
        ans[j] = i + 1
print("Yes")
print(*ans[1:])

Submission status: Accepted

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

from collections import deque

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

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

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print("Yes")
print("\n".join(str(i) for i in result[2:]))

Submission status: Accepted

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

queue = deque([1]) 
flag = [-1] * (N + 1)

while queue: 
    node = queue.popleft()
    children = graph[node] 
    for child in children:
        if flag[child] == -1:
            flag[child] = node
            queue.append(child)

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    edg[a].append(b)
    edg[b].append(a)
visited=[False for i in range(n)]
visited[0]=True
parent=[None for i in range(n)]
q=deque([0])
while len(q)>0:
    now=q.popleft()
    for i in edg[now]:
        if not visited[i]:
            q.append(i)
            visited[i]=True
            parent[i]=now
print("Yes")
for i in parent[1:]:
    print(i+1)

Submission status: Accepted

Solution code:
from collections import deque


N,M = (int(x) for x in input().split())
connected = [[] for _ in range(N+1)]
searched = [0] * (N+1)
signs = [0] * (N+1)
for i in range(M):
    A,B = (int(x) for x in input().split())
    connected[A].append(B)
    connected[B].append(A)
d = deque()
for edge in connected[1]:
    d.append(edge)
    signs[edge] = 1
    searched[edge] = 1
searched[1] = 1
while d:
    temp = d.popleft()
    for edge in connected[temp]:
        if searched[edge] == 0:
            d.append(edge)
            signs[edge] = temp
            searched[edge] = 1
    searched[temp] = 1
print('Yes')
for x in signs[2:]:
    print(x)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
import sys


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


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)

tokens = [-1] * N
tokens[0] = N
q = deque([0])
while q:
    v = q.popleft()
    for nv in graph[v]:
        if tokens[nv] < 0:
            tokens[nv] = v
            q.append(nv)

if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    print('\n'.join(map(lambda x: str(x + 1), tokens[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)]

q = deque([])
path = [-1] * n
ver = [[] for _ in range(n)]
for i in range(m):
    ab[i].sort()
    if ab[i][0] == 1:
        q.append([ab[i][0]-1,ab[i][1]-1])
        #path[ab[i][1]-1] = 1
    ver[ab[i][0]-1].append(ab[i][1]-1)
    ver[ab[i][1]-1].append(ab[i][0]-1)

#print(ver)
def bfs(q, visited_list):
    while len(q) > 0:
        now = q.popleft()
        go = now[1]
        #print(q)
        if path[go] == -1:
            path[go] = now[0]+1
            for i in range(len(ver[go])):
                q.append([go,ver[go][i]])
    return path
ans = bfs(q,path)
print('Yes')
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
import sys


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


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)
if len(set(graph.keys())) != N:
    print('No')
    exit()

tokens = [-1] * N
tokens[0] = N
q = deque([0])
while q:
    v = q.popleft()
    for nv in graph[v]:
        if tokens[nv] < 0:
            tokens[nv] = v
            q.append(nv)

print('Yes')
[print(t + 1) for t in tokens[1:]]

Submission status: Accepted

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

lists = [False for i in range(N)]
lists[0] = True
a = N - 1
dicts = {i:[] for i in range(N)}
d = deque([0])

for i in range(M):
    tmpa, tmpb = map(lambda x: int(x) - 1, input().split()) 
    dicts[tmpa] += [tmpb]
    dicts[tmpb] += [tmpa]

print('Yes')
while a > 0:
    tmp = d.popleft()
    for i in dicts[tmp]:
        if not lists[i]:
            if tmp != 0:
                lists[i] = tmp
            else:
                lists[i] = -1
            d.append(i)
            a -= 1
    
for i in range(1, N):
    print(lists[i] + 1 if lists[i] != -1 else 1)

Submission status: Accepted

Solution code:
import queue

n,m = map(int,input().split())
hen = [[] for i in range(n)]
ans = [0 for i in range(n)]
a,b = 0,0



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

q = queue.Queue()
q.put(1)

while q.empty() == False:
    head = q.get()
    for h in hen[head-1]:
        if h != 1 and ans[h-1] == 0:
            ans[h-1] = head
            q.put(h)

flag = 0

for i in range(n):
    if i != 0 and ans[i] == 0:
        flag = 1

if flag == 0:
    print('Yes')
    for i in range(n-1):
        print(ans[i+1])
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque

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

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

q = deque()
q.append(1)

visited = set()
mark = [-1 for _ in range(n+1)]

while len(visited) < n:
    _from = q.popleft()
    if _from in visited:
        continue
    visited.add(_from)
    for i in adj[_from]:
        q.append(i)
        if mark[i] == -1:
            mark[i] = _from

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
X = [[] for x in range(N+1)]
for m in range(M):
    A, B = map(int, input().split())
    X[A].append(B)
    X[B].append(A)

Q = deque()
Q.append(1)

D = [-1]*(N+1)
D[0] = 0
D[1] = 0
while Q:
    v = Q.pop()
    for i in X[v]:
        if D[i] == -1:
            D[i] = v
            Q.appendleft(i)
if -1 in D:
    print('No')
else:
    print('Yes')
    print(*D[2:])

Submission status: Accepted

Solution code:
from queue import Queue

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

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

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


placas = [0] * (n)

def bfs(a):
    q = Queue(maxsize = n)
    placas[0] = 1
    q.put(a)
    while not q.empty():
        popado = q.get()
        for adj in grafo[popado-1]:
            if not placas[adj-1]:
                placas[adj-1] = popado
                q.put(adj)

    if placas.count(0) == 0:
        print("Yes")
        for x in placas[1::]:
            print(x)
    else:
        print("No")

bfs(1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n,m=map(int,input().split())
    graph=[[] for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    queue=deque([0])
    visited=[False]*n
    visited[0]=True
    ans=[0]*n
    while queue:
        node=queue.popleft()
        for xnode in graph[node]:
            if visited[xnode]:continue
            ans[xnode]=node+1
            visited[xnode]=True
            queue.append(xnode)
    print("Yes")
    for a in ans[1:]:
        print(a)


if __name__=='__main__':
    main()

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)
 
seen = [0 for _ in range(N+1)]
seen[1] = 1
shirube = [-1 for _ in range(N+1)]
 
stack = deque([1])
while stack:
  now = stack.popleft()
  #print(now)
  for i in G[now]:
    if seen[i] == 0:
      seen[i] = 1
      stack.append(i)
      shirube[i] = now
      #print(shirube)
#print(G)
#print(seen)
#print(shirube)

for i in range(2,N+1):
  if seen[i] == 0:
    print('No')
    exit()
    
print('Yes')
for j in range(2,N+1):
  print(shirube[j])

Submission status: Accepted

Solution code:
n,m=list(map(int, input().split()))
root = [[] for _ in range(n)]
answer=[-1]*n
answer[0]=1
for i in range(m):
    c=list(map(int, input().split()))
    root[c[1]-1].append(c[0]-1)
    root[c[0]-1].append(c[1]-1)
count=1#最初から1の部屋はOKにしとく
queue=[0]
#print(root)
newqueue=[]
while(count<n and len(queue)!=0):
    for j in queue:
        for rootnum in root[j]:
            if(answer[rootnum]==-1):
                answer[rootnum]=j
                newqueue.append(rootnum)
                count+=1
    queue=newqueue
    #print(newqueue)
    newqueue=[]
if(count<n):
    print('No')
else:
    print('Yes')
    for l in range(n-1):
        print(answer[l+1]+1)

Submission status: Accepted

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

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

    net[a].append(b)
    net[b].append(a)

a = [-1] * (n+1)
d = deque()
d.append(1)
while d:
    u = d.popleft()
    for child in net[u]:
        if a[child] != -1:continue
        a[child] = u
        d.append(child)
print("Yes")
print(*a[2:], sep = " ")

Submission status: Accepted

Solution code:
from collections import deque

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

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

while q:
    now = q.popleft()
    for room in connection[now]:
        if check[room] == 0:
            ans[room]=now
            check[room]=1
            q.append(room)

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

Submission status: Accepted

Solution code:
import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import itertools
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

n,m = ri()
edge=[[] for _ in range(n)]
for i in range(m):
    a, b = ri()
    a+=-1
    b+=-1
    edge[a].append(b)
    edge[b].append(a)

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    visited[now]=1
    while len(q):
        now, p, d = q.popleft()
        dis[now] = d+1
        ans[now]=p+1
        
        for e in edge[now]:
            if visited[e]==1:
                continue
            q.append((e, now, dis[now]))
            visited[e]=1
        
        
        
        
bfs(0)
flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i])
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    A = [[] for j in range(N + 1)]
    ans = [0] * (N + 1)

    for a, b in AB:
        A[a].append(b)
        A[b].append(a)

    q = collections.deque()
    v = set()

    q.append(1)
    v.add(1)
    while q:
        c = q.popleft()

        for n in A[c]:
            if n not in v:
                v.add(n)
                q.append(n)
                ans[n] = c

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import itertools
#input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

n,m = ri()
edge=[[] for _ in range(n)]
for i in range(m):
    a, b = ri()
    a+=-1
    b+=-1
    edge[a].append(b)
    edge[b].append(a)

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    while len(q):
        now, p, d = q.popleft()
        dis[now] = d+1
        visited[now]=1
        ans[now]=p+1
        
        for e in edge[now]:
            if visited[e]==1:
                continue
            if e==now:
                continue
            q.append((e, now, dis[now]))
            visited[e]=1
        
        
        
        
bfs(0)
flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i])
else:
    print("No")

Submission status: Accepted

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

from collections import deque

q = deque()
q.append(1) # 頂点 1 をenque

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

while len(q) != 0:
    now = q.popleft() # queueから取り出す（deque）
    for to in adj[now]: # 隣接している頂点について
        if dist[to] != -1: # すでに書き換えられている場合は何もしない
            continue
        dist[to] = dist[now] + 1
        q.append(to)
        res[to] = now

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

stack=deque([0])
check = [-1]*n
check[0] = 0

while len(stack)>0:
    v = stack.popleft()
    for i in root[v]:
        if check[i] == -1:
            check[i]=v+1
            stack.append(i)
if -1 in check:
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(check[i])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
root = [[] for _ in range(N+1)]
 
for i in range(M):
    a, b = map(int, input().split())
    root[a].append(b)
    root[b].append(a)
 
ans = [10**9] * (N+1)
ans[0] = 0
ans[1] = 0
 
from collections import deque
q = deque([1])
 
while q:
    p = q.popleft()
    for i in root[p]:
        if ans[i] == 10**9:
            ans[i] = p
            q.append(i)
 
if 10**9 in set(ans):
    print('No')
else:
    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())
G = [[] for _ in range(N)]
for i in range(M):
  A, B = map(int, input().split())
  G[A-1].append(B-1)
  G[B-1].append(A-1)

seen = [0 for _ in range(N)]
seen[0] = 1
shirube = [-1 for _ in range(N-1)]

stack = deque([0])
while stack:
  now = stack.popleft()
  for i in G[now]:
    if seen[i] == 0:
      seen[i] = 1
      stack.append(i)
      shirube[i-1] = now
    
for i in range(N):
  if seen[i] == 0:
    print('No')
    exit()
    
print('Yes')
for j in range(N-1):
  print(shirube[j]+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def main():
    input = sys.stdin.readline
    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] * (N + 1)
    ans[1] - 1
    cnt = 1
    q = deque([1])
    while q:
        v = q.popleft()
        for to in G[v]:
            if ans[to] > 0: continue
            ans[to] = v
            q.append(to)
            cnt += 1
    if cnt < N:
        print('No')
        return
    print('Yes')
    for i in range(2, N + 1):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [-1] * N
minDist = [10**18] * N
minDist[0] = 0
que = deque([0])

while que:
    now = que.popleft()
    dist = minDist[now] + 1
    for to in edges[now]:
        if minDist[to] > dist:
            minDist[to] = dist
            ans[to] = now
            que.append(to)

print('Yes')
for a in ans[1:]:
    print(a + 1)

Submission status: Accepted

Solution code:
#coding: utf-8
from collections import deque
N, M = map(int, input().split())
dd = {i:[] for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    dd[a-1].append(b-1)
    dd[b-1].append(a-1)
ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
queue = []
for i in range(len(dd[0])):
    queue.append([0, dd[0][i]])
queue = deque(queue)
while queue:
    q = queue.popleft()
    if visited[q[1]]:
        continue
    visited[q[1]] = True
    ans[q[1]] = q[0] + 1
    for v in dd[q[1]]:
        if not visited[v]:
            queue.append([q[1], v])
print("Yes")
print(*ans[1:], sep="\n")

Submission status: Accepted

Solution code:
N, M = [int(n) for n in input().split()]

# node:connected
graph = {node:set() for node in range(1,N+1)}

for _ in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].add(B)
    graph[B].add(A)

to_visit = set(range(2,N+1))
level = 0

posts = {}

while to_visit:
    # base
    if level == 0:
        levels = {0:{1:None}}
        current_level = {1}
    
    # loop
    else:
        prevs = levels[level-1]
        levels[level] = {}
        for prev in prevs:
            for nbr in graph[prev]:
                if nbr in to_visit:
                    levels[level][nbr] = prev
                    posts[nbr] = prev
                    to_visit.remove(nbr) 
    
    level += 1

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

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while len(q) != 0:
        now = q.popleft()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.append(next)

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



if __name__=='__main__':
    main()

Submission status: Accepted

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



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N, M = 6, 9
ARR = [
    [3, 4],
    [6, 1],
    [2, 4],
    [5, 3],
    [4, 6],
    [1, 5],
    [6, 2],
    [4, 5],
    [5, 6],
]

N, M = 4, 4
ARR = [
    [1, 2],
    [2, 3],
    [3, 4],
    [4, 2],
]

N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))

from collections import deque


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [-1 for i in range(n)]
    prevs = [-1 for i in range(n)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStates, prevs


nodes, nodeStates, prevs = prepare(N, M, ARR)


def bfs(nodes, nodeStates, prevs, n):
    q = deque()
    q.append({'prev': -1, 'to': 0})
    while len(q) > 0:
        first = q.popleft()
        currentNode = first['to']
        previousNode = first['prev']
        if nodeStates[currentNode] != -1:
            continue
        prevs[currentNode] = previousNode
        childNodes = nodes[currentNode]
        nodeStates[currentNode] = 1
        for childNode in childNodes:
            q.append({'prev': currentNode, 'to': childNode})

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


bfs(nodes, nodeStates, prevs, N)

Submission status: Accepted

Solution code:
def main():

    from collections import defaultdict
    from collections import deque
    N, M = map(int, input().split())

    dic = defaultdict(lambda :[])
    INF = 10 ** 6
    A = [INF] * N
    A[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        dic[a].append(b)
        dic[b].append(a)
        if a == 0 :
            A[b] = 0
        elif b == 0:
            A[a] = 0

    for i in range(1, N):
        l = len(dic[i])
        if l == 0:
            print('No')
            return
        elif l == 1:
            A[i] = dic[i][0]

    q = deque()
    for n in dic[0]:
        q.append((n, 1))
        A[n] = 0

    while len(q) > 0:
        n, d = q.popleft()
        for x in dic[n]:
            if A[x] == INF:
                A[x] = n
                q.append((x, d + 1))

    if any([v == 10 ** 6 for v in A]):
        print('No')
    else:
        print('Yes')
        for v in A[1:]:
            print(v + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

root = [set()for i in range(N+1)]
ans = [0 for i in range(N+1)]

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

task = deque([1])
itta = {1}

while len(task) > 0:
    now = task.popleft()
    additionanl = root[now] - itta #到達済みを排除している
    for i in additionanl: #ノードチェック
        ans[i] = now 
        itta.add(i)
    task.extend(list(additionanl)) #チェックしたノードを追加
print("Yes")
for i in range(2,N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
N, M, *AB = map(int, open(0).read().split())

graph = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    graph[a].append(b)
    graph[b].append(a)
    
# bfs
from collections import deque

queue = deque([1])
numsigns = [0] * (N + 1) # ←なるほど、0行および0列は定義するが使わないということか
numsigns[1] = 1

while queue:
    p = queue.popleft() # ←現在地
    for nxt in graph[p]: # ←現在地がつながっているところを探索
        if not numsigns[nxt]: # ←印が付いていなかったら
            numsigns[nxt] = p
            queue.append(nxt)

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

Submission status: Accepted

Solution code:
mNM = map(int, input().split())
lNM = list(mNM)

mWay = [map(int, input().split()) for i in range(lNM[1])]
lWay = [list(mWay[i]) for i in range(lNM[1])]

maps = [-1 for i in range(lNM[0])]
deep = [-1 for i in range(lNM[0])]
ways = [[] for i in range(lNM[0])]

for i in range(lNM[1]):
    ways[lWay[i][0] - 1].append(lWay[i][1])
    ways[lWay[i][1] - 1].append(lWay[i][0])

maps[0] = 0
deep[0] = 0
nexts = [0]

for i in range(lNM[0]):
    try:
        index = nexts     
        nexts = []
        
        for x in index:
            for w in ways[x]:
                if(deep[w - 1] == -1):
                    deep[w - 1] = i + 1
                    maps[w - 1] = x + 1
                    nexts.append(w - 1)
        
    except:
        pass
    
if(-1 in maps):
    print('No')
else:
    print('Yes')
    for i in maps[1:]:
        print(i)

Submission status: Accepted

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

q = deque([1])
flg = [-1]*n
flg[0] = 0

while q:
	item = q.popleft()
	for i in ab[item]:
		if put[i]:
			flg[i-1]=item
			q.append(i)
			put[i]=0
 
if -1 in flg:
	print("No")
	exit()
 
print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Submission status: Accepted

Solution code:
from collections import deque
import math
N,M=map(int,input().split())
"""
BFSする。探索される側をメモ。
"""
dist = [-1 for i in range(N)]
graph = [[] for i in range(N+1)]
for i in range(M):
  A,B=map(int,input().split())
  graph[A].append(B)
  graph[B].append(A)
  
#print(dist, graph)

# init
ans = [-1]*(N+1)
q = deque()
q.append(1)
while len(q)>0:
  #print(q,dist)
  node = q.popleft()
  for j in graph[node]:
    if ans[j] == -1:
      ans[j]=node
      q.append(j)
print("Yes")
print("\n".join(list(map(str,ans[2:]))))