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 Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node):
    check=[False for _ in range(n)]
    check[s]=True
    queue=[n for _ in range(n)]
    now=0
    queue[now]=s
    ans=[-1 for _ in range(n)]
    ans[0]=[0]
    last_ind=1
    while last_ind<n:

        
        if now>=n or queue[now]==n:
            return []

        for i in node[queue[now]]:
            edge=i[0]
            
            ind=i[1]
            if check[edge]:
                continue

            queue[last_ind]=edge
            last_ind+=1
            #check[edge]=True
            
            ans[edge]=queue[now]
            check[edge]=True
        now+=1
        #print(queue)
        #print(last_ind)
        #print()
    return ans



n,m=input_list()
node=[[] for _ in range(n)]
for i in range(m):
    u,v=input_list()
    u-=1
    v-=1
    node[u].append([v,i])
    node[v].append([u,i])

#print(np.array(node))

ans=bfs(0,n,node)
if len(ans)==0:
    print("No")
    exit()

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

Submission status: Accepted

Solution code:
from collections import deque

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


## ----main
N, M = list(map(int,input().split()))
graph = [[] for _ in range(N)]

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

visited = bfs(graph,N,0)

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

Submission status: Accepted

Solution code:
from collections import deque

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

checked = [False for _ in range(N)]
queue = deque([0])
checked[0] = True
ans = [0 for _ in range(N)]
while queue:
    now = queue.popleft()
    for i in X[now]:
        if not checked[i]:
            ans[i] = now +1
            queue.append(i)
            checked[i] = True
for i in range(N):
    if i == 0:
        print('Yes')
    else:
        print(ans[i])

Submission status: Accepted

Solution code:
import heapq

N,M = map(int, input().split())
nl = {i:[] for i in range(1,N+1)}
rlt = [-1]*(N+1)

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

ds = [float('inf')]*(N+1)
ds[1] = 0
h = []
heapq.heappush(h,[0,1])

while(len(h) > 0):
  tmp = heapq.heappop(h)
  v = tmp[1]
  if ds[v] < tmp[0]:
    continue
  for j in nl[v]:
    if ds[j] > ds[v] + 1:
      ds[j] = ds[v] + 1
      rlt[j] = v
      heapq.heappush(h,[ds[j],j])

if -1 in rlt[2:]:
  print('No')
else:
  print('Yes')
  for i in rlt[2:]:
    print(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)]

graph = [[] for _ in range(n + 1)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    graph[a].append(b)
    graph[b].append(a)

inf = 100100100
ans = [[inf, inf] for _ in range(n + 1)]
ans[0] = [0, 0]
ans[1] = [0, 0]

q = deque([1])
while q:
    now = q.popleft()
    depth = ans[now][1]
    for x in graph[now]:
        if ans[x][0] == inf:
            q.append(x)
            if ans[x][1] > depth + 1:
                ans[x][0] = now
                ans[x][1] = depth + 1

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

Submission status: Accepted

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])

for x in s:
    g.add_edge(x[0],x[1])
di=nx.predecessor(g,source=1)

if len(di)!=n:
    print("No")
    exit()

print("Yes")
for x in range(2,n+1):
    print(di[x][0])

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

def bfs(x):
    dist = [None] * (N+1)
    que = deque([1])
    dir = [None] * (N+1)
    popleft = que.popleft; append = que.append    
    while que:
        x = popleft()
        d = dist[x]
        for next in graph[x]:
            if dir[next] != None:
                continue
            dir[next] = str(x)
            append(next)
    return dir

dir = bfs(1)
print('Yes')
print('\n'.join(dir[2:]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = [[] for _ in range(n)] 

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0 
    l = [[] for _ in range(n)] 
    dic = {}
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                l[i].append(v)
                dic[i] = v
    return d,l,dic
d,l,dic = bfs(0)
if None in d:
    print("No")
else:
    print("Yes")
    l.remove(l[0])
    [print(i[0]+1) for i in l]

Submission status: Accepted

Solution code:
#4問目
import sys
from collections import deque

N, M = map(int, input().split())
#どこの配列番号と繋がっているか保存
link = [[] for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    link[A-1].append(B-1)
    link[B-1].append(A-1)
visited = [False for _ in range(N)]
visited[0] = True

Q = [0]
mark = [0 for i in range(N)]

while Q:
    #v:= 階層(0からはじまり)
    v = Q.pop(0)
    for i in link[v]:
        if not visited[i]:
            visited[i] = True
            mark[i] = v
            Q.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

while que:
    c = que.popleft()
    for i in arr[c]:
        if dist[i] != -1:
            continue
        dist[i] = 0
        pre[i] = c
        que.append(i)

print("Yes")  # 必ずYesになる
for i in pre[1:]:
    print(i+1)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

N, M = map(int, input().split())
graph = defaultdict(list)

# defaultdictにグラフ構造（双方向）を格納
for _ in range(M):
    a, b = map(lambda x: int(x), input().split())
    graph[a].append(b)
    graph[b].append(a)

# 訪れたかどうかを判定するリストを準備
visited = [False] * (N + 1)

# 0は捨て番、1はstart地点のため更新されないようにvisitedにしておく
visited[0] = True
visited[1] = True

# 開始地点を指定
que = deque([1])

while que:
    # 幅優先なのでFIFO。最初はスタート地点をpop
    node = que.popleft()

    # popしたノードから辿れるノードがまだ訪れていないノードであれば更新し、キューにappend
    for n in graph[node]:
        if not visited[n]:
            visited[n] = node
            que.append(n)

# 判定結果はindex:2以降でスライスしたもの
visited = visited[2:]

# 全てTrue（全ノード訪れている）ならYes、そうでなければNo
if all(visited):
    print("Yes")
    print(*visited, sep="\n")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
arr = [[] for n in range(N)]
que = deque([1])

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

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

print("Yes")
while que:
    c = que.popleft()
    for i in arr[c - 1]:
        if dist[i - 1] != -1:
            continue

        dist[i - 1] = 0
        arr2[i - 2] = c
        que.append(i)

for i in arr2:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

n, m = list(map(int, input().split()))
edge = {}
for i in range(m):
    ai, bi = list(map(int, input().split()))
    if ai in edge:
        edge[ai].append(bi)
    else:
        edge[ai] = [bi,]
    if bi in edge:
        edge[bi].append(ai)
    else:
        edge[bi] = [ai,]
# print(edge)

is_visited = np.zeros((n+1,), dtype=np.bool)
parent = np.zeros((n+1,), dtype=np.int)

q = deque()
q.append(1)
is_visited[1] = True
while len(q) != 0:
    node = q.popleft()
    for child in edge[node]:
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
q = deque([1])
p = [0]*(n+1)
while q:
    v = q.popleft()
    for u in G[v]:
        if p[u] == 0:
            p[u] = v
            q.append(u)
print("Yes\n"+"\n".join(map(str, p[2:])))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

graph = defaultdict(set)

for _ in range(m):
    a, b = list(map(int, input().split()))
    graph[a].add(b)
    graph[b].add(a)

# 幅優先探索
# https://qiita.com/drken/items/4a7869c5e304883f539b
seen = [False for _ in range(n + 1)]  # 既に道しるべを設置したか? # idx 0 は使わない
todo = set()  # 検知したけどまだ探索してない
ans = defaultdict(int)
seen[1] = True
todo.update(graph[1])
for d in graph[1]:
    ans[d] = 1  # 1と繋がってる部屋の道しるべは1
    seen[d] = True
# 出発ノード
while len(todo) > 0:
    todo_next = set()
    for v in todo:
        for d in graph[v]:
            if seen[d]:
                continue
            seen[d] = True
            todo_next.add(d)
            ans[d] = v
    todo = todo_next

if not all(seen[1:]):
    print("No")
    exit()

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

Submission status: Accepted

Solution code:
from collections import deque

# print('input >>')
N, M = map(int,(input().split()))
ABs = [map(int,(input().split())) for _ in range(M)]

INF = 10 ** 10
ds = [INF] * (N+1)
marks = [0] * (N+1)

nodes = [None] * (N+1)

for AB in ABs:
    A, B = AB
    if nodes[A] is None:
        nodes[A] = []
    nodes[A].append(B)

    B, A = A, B
    if nodes[A] is None:
        nodes[A] = []
    nodes[A].append(B)

# print(nodes)

queue = deque([1])
visited = [0] * (N+1)
visited[1] = 1

# d = 0
# ds = [INF] * (N+1)
marks = [0] * (N+1)
parent = 1

while len(queue) > 0:
    p = queue.popleft()
    # print(p)
    # parent, node = p[0], p[1]
    # visited[node] = 1
    # marks[node] = parent
    for n in nodes[p]:
        if visited[n] == 0:
            visited[n] = 1
            marks[n] = p
            queue.append(n)

print('Yes')
for mark in marks[2:]:
    print(mark)

Submission status: Accepted

Solution code:
import collections
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)
q = collections.deque()
q.append(0)
dist = [-1]*N
dist[0] = 0
while len(q) != 0:
    v = q.popleft()
    for w in graph[v]:
        if dist[w] > -1:
            continue
        dist[w] = v + 1
        q.append(w)
print('Yes')
for i in range(1,N):
    print(dist[i])

Submission status: Accepted

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

from collections import defaultdict
from heapq import *

def solve(N, M, AB):
    rs = defaultdict(set)
    for a, b in AB:
        rs[a].add(b)
        rs[b].add(a)
    h = []
    t = {1: 0}
    heappush(h, (0, 1))
    while h:
        d, x = heappop(h)
        for dx in rs[x]:
            if dx not in t:
                t[dx] = x
                heappush(h, (d + 1, dx))
    return t

result = solve(N, M, AB)

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

Submission status: Accepted

Solution code:
from collections import deque

n, m = list(map(int, input().split(' ')))
graph = {}

for i in range(m):
    a, b = list(map(int, input().split(' ')))

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

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

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

que = deque()

for c in graph[1]:
    ans[c-1] = 1
    que.appendleft(c)

while len(que) != 0:
    target = que.pop()
    candidates = graph[target]

    for c in candidates:
        if c != 1 and ans[c - 1] == -1:
            ans[c - 1] = target
            que.appendleft(c)

ans = ans[1:]

if -1 in ans:
    print("No")
else:
    print("Yes")
    for i in ans:
        print(i)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
root = [[] for _ in range(n)]
answer = [-1]*n
answer[0]=0
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[:]
    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 as dq
import sys
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    lst = [[] for _ in range(n + 1)]
    ans = [0] * (n + 1)
    que = dq()
    for _ in range(m):
        a, b = map(int, input().split())
        lst[a].append(b)
        lst[b].append(a)

    limit = 10 ** 5
    d = {i: limit + 1 for i in range(1, n + 1)}
    d[1] = 0
    que.append(1)
    while que:
        visit = que.popleft()
        for next_v in lst[visit]:
            if d[next_v] > d[visit] + 1:
                d[next_v] = d[visit] + 1
                que.append(next_v)
                ans[next_v] = visit

    if all([i != 0 for i in ans[2:]]):
        print('Yes')
        print(*ans[2:], sep='\n')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import deque

p=[0]*n
ans=[0]*n
d=deque()
d.append(0)
while len(d)!=0:
    now=d.popleft()
    for to in l[now]:
        if p[to]==0:
            p[to]=p[now]+1
            d.append(to)
            ans[to]=now
print("Yes")
for i in range(1,n):
    print(ans[i]+1)

Submission status: Accepted

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

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

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
t = [[] for i in range(n)]
near = [-1 for i in range(n)]
near[0] = 0
c = []
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    near[t[0][i]] = 0
    c.append(t[0][i])
while len(c) > 0:
    e = c[0]
    for j in range(len(t[e])):
      if near[t[e][j]] == -1:
        near[t[e][j]] = e
        c.append(t[e][j])
    del c[0]
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)

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):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
q = deque([1])
p = [0]*(n+1)
while q:
    v = q.popleft()
    for u in G[v]:
        if p[u] == 0:
            p[u] = v
            q.append(u)
print("Yes\n"+"\n".join(map(str, p[2:])))

Submission status: Accepted

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

v = [[i,-1] for i in range(n+1)]
v[1][1] = 0
for i in range(m):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
dq = deque([])
dq.append(v[1])
# print(v)
while dq:
    t = list(deque.popleft(dq))
    # print(t)
    for i in t[1:]:
        if v[i][1] == -1:
            v[i][1] = t[0]
            dq.append(v[i])
print("Yes")
for i in range(n-1):
    print(v[i+2][1])

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n,m = map(int,input().split())
    arr = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        arr[a-1].append(b-1)
        arr[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = {i:0 for i in range(1, n)}
    while q:
        now = q.popleft()
        for i in arr[now]:
            if i == 0:
                continue
            if ans[i] == 0:
                ans[i] = now+1
                q.append(i)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque


class BreadthFirstSearch:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.adj_list = [[] for _ in range(self.n)]

    # Edge数分回すことを想定
    def add_edge(self, start, end, undirected=True):
        self.adj_list[start].append(end)
        if undirected:
            self.adj_list[end].append(start)

    # depth = distance
    def search(self, start_node):
        order = [-1] * self.n  # a bfs ordering of each vertex
        parent = [-1] * self.n  # parent of each vertex in the bfs search tree
        depth = [-1] * self.n  # the depth of each vertex
        q = deque([(start_node, -1, 0)])  # (vertex, parent, depth)
        num = 0  # current ordering
        while len(q) > 0:
            v, p, d = q.popleft()
            if order[v] < 0:  # visited v for the first time
                order[v] = num
                parent[v] = p
                depth[v] = d
                num += 1
                for u in self.adj_list[v]:
                    if order[u] >= 0:
                        continue
                    q.append((u, v, d+1))
        return order, parent, depth


def get_result(data):
    N, M = data[0]
    A = data[1:]
    solver = BreadthFirstSearch(N)
    for val in A:
        solver.add_edge(val[0]-1, val[1]-1)
    order, parent, depth = solver.search(0)
    print('Yes')
    for p in parent[1:]:
        print(p+1)
    return None


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    # print(result)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, a):
  queue = deque([1])

  while queue:
    x = queue.popleft()
    for i in maze[x - 1]:
      if(a[i - 1] == -1):
        a[i - 1] = x
        queue.append(i)
      
if __name__ == '__main__':
  n, m = map(int, input().split())
  maze = [[] for i in range(n)]
  for i in range(m):
    a, b = map(int, input().split())
    maze[a - 1].append(b)
    maze[b - 1].append(a)

  visit = [(-1)] * n
  visit[0] = 0

  bfs(maze, visit)

if(-1 in maze):
  print('No')
else:
  print("Yes")
  for i in range(1, n):
    print(visit[i])

Submission status: Accepted

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

stack=deque([1])
visited=[-1 for i in range(N+1)]
visited2=[-1 for i in range(N+1)]
visited[1]=0

while stack:
    x=stack.popleft()
    for i in graph[x]:
        if visited[i]==-1:
            visited[i]=visited[x]+1
            visited2[i]=x
            stack.append(i)
print('Yes')
print(*visited2[2:],sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(m)]
b=[[] for j in range(n)] 

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

N, M = map(int, input().split())
graph = defaultdict(list)

# defaultdictにグラフ構造を格納
for _ in range(M):
    a, b = map(lambda x: int(x), input().split())
    graph[a].append(b)
    graph[b].append(a)

# 訪れたかどうかを判定。
visited = [False] * (N + 1)

# 0は捨て番、1は更新されないようにvisitedにしておく
visited[0] = True
visited[1] = True

# start地点を指定
que = deque([1])

while que:
    # 幅優先なのでFIFO。最初はスタート地点をpop
    node = que.popleft()

    # popしたノードを訪れていなければ、ノード番号を格納し、キューにノードをappend
    for n in graph[node]:
        if not visited[n]:
            visited[n] = node
            que.append(n)

# 判定結果はindex:2以降でスライスしたもの
visited = visited[2:]

if all(visited):
    print("Yes")
    print(*visited, sep="\n")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n,m = map(int,input().split())
    arr = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        arr[a-1].append(b-1)
        arr[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.popleft()
        for i in arr[now]:
            if ans[i] == -1:
                ans[i] = now+1
                q.append(i)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
t = [[] for i in range(n)]
near = [-1 for i in range(n)]
near[0] = 0
q = deque()
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    c = t[0][i]
    near[c] = 0
    q.append(c)
while len(q) > 0:
    e = q.popleft()
    for j in range(len(t[e])):
        c = t[e][j]
        if near[c] == -1:
            near[c] = e
            q.append(c)
print('Yes')
for i in range(1,len(near)):
    print(near[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())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

# bfs
queue = deque([0])
d = [None] * n # init fromt rooms
d[0] = 0
while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] is None:
            d[i] = v
            queue.append(i)
print('Yes')
for i in range(1, n):
    print(d[i]+1)

Submission status: Accepted

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

adj = [[] for _ in range(n)]

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

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

que.append(0)
while len(que) != 0:
    now = que.popleft()
    for to in adj[now]:
        if dist[to] != -1: continue
        dist[to] = dist[now]+1
        que.append(to)
        ans[to]=now

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

Submission status: Accepted

Solution code:
from collections import deque


r, p = map(int, input().split())
graph = [[] for _ in range(r)]

for x in range(p):
    x1, x2 = map(int, input().split())
    graph[x1-1].append(x2-1)
    graph[x2-1].append(x1-1)

q = [0]
res = [-1]*r
res[0] = 0
while q:
    l = q.pop(0)
    for x in graph[l]:
        if res[x] == -1:
            res[x] = l
            q.append(x)
if -1 in res[1:]:
    print("No")
    exit()
print("Yes")
for x in res[1:]:
    print(x+1)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(n)]
sirusi=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
D=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
        sirusi[i]=v
        D.append(i)
print("Yes")
for i in range(1,n):
    print(sirusi[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    RoomNum,PathNum=map(int,input().split())

    G=[[] for _ in range(RoomNum)]

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

    dist=[-1]*RoomNum
    que=deque([])
    dist[0]=0
    que.append(0)

    while len(que)>0:
        v=que.popleft()

        for i in G[v]: #vからつながっている頂点をすべて調べる
            if dist[i]!=-1: #すでに発見済み（キューに追加済み）は無視
                continue
            dist[i]=v #発見したら深さを更新するが今回は看板の数字
            que.append(i)

    if (-1 in dist): #未発見のものが残っているとき
        print("No")
    else:
        print("Yes")
        for i in dist[1:]:
            print(i+1)

if __name__=="__main__":
    main()

Submission status: Accepted

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

e = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
visited = [0]*N
visited[0] = 1
que = [0]
while que:
    x = que.pop(0)
    for i in e[x]:
        if visited[i] == 0:
            visited[i] = x+1
            que.append(i)

print("Yes")


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

Submission status: Accepted

Solution code:
from _collections import deque


def bfs(init, n, gi):
    queue = deque([init])
    d = [-1] * n
    d[init] = 0
    while queue:
        popped = queue.popleft()
        for ii in gi[popped]:
            if d[ii] == -1:
                d[ii] = popped + 1
                queue.append(ii)
    return d


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)

get = bfs(0, N, g)
ans = [0] * N
if -1 in get:
    print('No')
else:
    print('Yes')
    for i in range(1, len(get)):
        print(get[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 q:
        now = q.popleft()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.append(next)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import queue
n, m = map(int, input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
dic = {}
for i in range(1, n+1):
    dic[i] = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    dic[a[i]].append(b[i])
    dic[b[i]].append(a[i])
res = 0
INF = 100010
l = [0 for i in range(n+1)]
l[1] = 1
michi = [INF for i in range(n+1)] 
michi[1] = 0
p = [1]
shi = 1
while True:
    tmp = []
    for i in p:
        for j in dic[i]:
            if l[j] == 0:
                l[j] = 1
                tmp.append(j)
    if not tmp:
        break
    for i in tmp:
        michi[i] = shi
    p = tmp
    shi = p[0]
flag = True
for i in range(2, n+1):
    if michi[i] == INF:
        flag = False
if flag:
    print("Yes")
    for i in range(2, n+1):
        print(michi[i])
else:
    print("No")