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())
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)
#dist = [-1]*(n+1)
route = [-1]*(n+1)
route[0] = 0
route[0] = 0
#dist[0] = 0
#dist[1] = 0
d = deque()
d.append(1)
while d:
  v = d.popleft()
  for i in graph[v]:
    if route[i] == -1:
      #dist[i] = dist[v] + 1
      route[i] = v
      d.append(i)
if route.count(-1) == 0:
  print("Yes")
  for i in range(2,len(route)):
    print(route[i])
else:
  print("No")

Submission status: Accepted

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

for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=deque([1])
f=set([1])


while st:
  x=st.popleft()
  for k in l[x]:
    if k not in f:
      st.append(k)
      f.add(k)
      vi[k]=x   
  
print("Yes")
for m in vi[2:]:
  print(m)

Submission status: Accepted

Solution code:
import queue

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

#sign:道しるべがどこを示しているか
sign = [-1]*N
sign[0] = 0

flag = True

# FIFOキューの作成
q = queue.Queue()
q.put(0)
r = queue.Queue()


while flag:
    flag = False
    num = 1

    while not q.empty():
        hoge = q.get()
        for i in range(len(root[hoge])):
            if sign[root[hoge][i]] == -1:
                sign[root[hoge][i]] = hoge
                r.put(root[hoge][i])
                flag = True

    while not r.empty():
        q.put(r.get())

    num += 1

if sign.count(-1) == 0:
    print("Yes")
    for i in range(1,N):
        print(sign[i]+1)
else:
    print("No")
    print(sign)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _i in range(m)]
 
visit = [-1 for _ in range(n)]
visit[0] = 0
tree = [[] for _ in range(n)]
for a, b in ab:
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
 
from collections import deque
q = deque([0])
while q:
    p = q.popleft()
    for i in tree[p]:
        if visit[i] < 0:
            visit[i] = p
            q.append(i)
if all(i >= 0 for i in visit):
    print("Yes")
    for i in visit[1:]:
        print(i+1)
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())
    to = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        to[a].append(b)
        to[b].append(a)
    q = deque([1])
    ans = [None]*(n+1)
    while q:
        p = q.pop()
        for child in to[p]:
            if ans[child] is None:
                ans[child] = p
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))
    
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = [[] for _ in range(N+1)]
    for _ in range(M):
        (A,B) = map(int, input().split())
        neighbor[A] += B,
        neighbor[B] += A,

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

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor[n]
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: guide[d] == 0, dests)
        # 道しるべを置く
        for d in dests:
            guide[d] = n
            checked += d,
            # 探索候補の末尾に追加
            target += d,

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

main()

Submission status: Accepted

Solution code:
import sys
import queue
s = sys.stdin.readlines

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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


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

def bfs():
    q = queue.Queue()
    q.put(0)

    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = v + 1
            q.put(nv)
    
bfs()

if -1 in dist:
    print("No")
else:
    print("Yes")
    dist.pop(0)
    for s in dist:
        print(s)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

INF = 1000000
N, M = map(int, input().split())
d = [INF]*(N+1)
d[1] = 0
prev = [0]*(N+1)
G = {}
for i in range(M):
  a, b = map(int, input().split())
  try:
    G[a].append(b)
  except:
    G[a] = [b]
  try:
    G[b].append(a)
  except:
    G[b] = [a]

que = []
heappush(que, (0, 1))
    
while True:
  if len(que) == 0:
    break
  p = heappop(que)
  v = p[1]
  
  for u in G[v]:
    if (d[u] > d[v] + 1):
      d[u] = d[v] + 1
      heappush(que, (d[u], u))
      prev[u] = v
      
if 0 in prev[2:]:print('No')
else:
  print('Yes')
  for i in range(2, N+1):
    print(prev[i])

Submission status: Accepted

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

for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=deque([1])
f=set([1])


while st:
  x=st.popleft()
  for k in l[x]:
    if k not in f:
      st.append(k)
      f.add(k)
      vi[k]=x   
  
print("Yes")
for m in vi[2:]:
  print(m)

Submission status: Accepted

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

for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=deque([1])
e=set()
f=set()


while st:
    x=st.popleft()
    if x not in e:
      e.add(x)
      for k in l[x]:
        if k not in f:
          st.append(k)
          f.add(k)
          vi[k]=x   
  
print("Yes")
for m in vi[2:]:
  print(m)

Submission status: Accepted

Solution code:
#NEED RE-SOLVE LATER.
from collections import deque
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
    a, b = map(lambda x: x-1, map(int, input().split()))
    G[a].append(b)
    G[b].append(a)

q = deque([0])
visited = [None]+[-1]*(n-1)
while q:
    nx = q.pop()
    for g in G[nx]:
        if visited[g] != -1:
            continue
        visited[g] = nx
        q.appendleft(g)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

print('Yes')

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

dq = deque()
dq.append(0)

while dq:
    v = dq.popleft()
    for u in g[v]:
        if ~ret[u]: continue
        ret[u] = v
        dq.append(u)

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

Submission status: Accepted

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

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

for _ in range(M):
  a, b = map(int, input().split())
  route[a].append(b)
  route[b].append(a)
  
q = deque([1]) # 頂点を設定して初期化
pre = [None] * (N+1) # 頂点までの最短に進む時の次の頂点のリスト
pre[1] = 0 # 頂点は0
depth = [None] * (N+1) # 頂点からの深さ(最短距離)のリスト
depth[1] = 0 # 頂点の距離は0
while len(q) > 0:
  x = q.popleft()
  for r in route[x]:
    if pre[r] is None:
      depth[r] = depth[x] + 1
      pre[r] = x
      q.append(r)

print("Yes")
for i in range(2, len(pre)):
  print(pre[i])

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(n+1)]# 隣接リスト

for i in range(m):# 隣接リストを格納
    a,b=map(int,input().split())
    templ=G[a]
    templ.append(b)
    G[a]=templ
    templ=G[b]
    templ.append(a)
    G[b]=templ


dist=[-1 for i in range(n+1)]
prev=[-1 for i in range(n+1)]
q=deque([1])
dist[1]=0

while len(q)!=0:
    v=q.popleft()
    for nv in G[v]:
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+1
        prev[nv]=v
        q.append(nv)
print('Yes')
for i in range(2,n+1):
    print(prev[i])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
routes = [[] for i in range(N-1)]
ans = [0]*(N-1)
li = []
for i in range(M):
  r = list(map(int, input().split()))
  if r[0] == 1:
    li.append(r[1])
    ans[r[1]-2] = 1
  elif r[1] == 1:
    li.append(r[0])
    ans[r[0]-2] = 1
  else:
    routes[r[0]-2].append(r[1])
    routes[r[1]-2].append(r[0])
    
flag = True
while 0 in ans:
  tmp = []
  if li == []:
    flag = False
    break
  for num in li:
    for route in routes[num-2]:
      if ans[route-2] == 0:
        ans[route-2] = num
        tmp.append(route)
  li = tmp
  
if flag:
  print('Yes')
  for i in range(N-1):
    print(ans[i])
else:
  print('No')

Submission status: Accepted

Solution code:
from collections import deque

mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    n, m = map(int,raw_input().split())
    
    adj_list = [[] for _ in range(n+5)]
    
    q = deque()
    
    ans = [-1] * (n+5)
    
    failed = False
    
    for _ in range(m):
        a, b = map(int,raw_input().split())    
        adj_list[a].append(b)
        adj_list[b].append(a)
    
    q.append(1)
    
    #print(adj_list)
    
    visited = set()
    
    visited.add(1)
    
    while len(q):
        sz = len(q)
        for _ in range(sz):
            cur = q.popleft()
            for nei in adj_list[cur]:
                if nei not in visited:
                    ans[nei] = cur
                    q.append(nei)
                    visited.add(nei)
    
    
    print('Yes')
    for i in range(2, n+1):
        print(ans[i])
            
            
        
        
    
    

main()

Submission status: Accepted

Solution code:
def mi(): return map(int,input().split())
def lmi(): return list(map(int,input().split()))
def ii(): return int(input())
def isp(): return input().split()
from collections import deque
n,m=mi()
adjacent_list=[[] for i in range(n+1)]
for i in range(m):
  a,b=mi()
  adjacent_list[a].append(b)
  adjacent_list[b].append(a)
#print(adjacent_list)

dp=[0]*(n+1)

que=deque()
que.append(1)
while que:
  p=que.popleft()
  for i in adjacent_list[p]:
    if dp[i]==0:
      dp[i]=p
      que.append(i)
      
print('Yes')
for i in range(2,n+1):
  print(dp[i])

Submission status: Accepted

Solution code:
from collections import deque

N,M = (int(a) for a in input().split())
g = [[] for _ in range(N)]
s = [0]*N
for i in range(M) :
    A,B = (int(a) for a in input().split())
    g[A-1].append(B)
    g[B-1].append(A)
visited = {0}
stack = [0]
for i in stack :
    for j in g[i] :
        if j-1 in visited :
            continue
        stack.append(j-1)
        visited.add(j-1)
        s[j-1] = i + 1
if s.count(0) > 1 :
    print("No")
else :
    print("Yes")
    print(*s[1:])

Submission status: Accepted

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

(n, m), g = map(int, input().split()), defaultdict(list)
for i in range(m): a, b = map(int, input().split()); g[a].append(b); g[b].append(a)
s, q = [0, 0] + [-1 for i in range(1, n)], deque([1])
for i in range(2, n + 1):
    x = q.popleft()
    for a in g[x]:
        if s[a] == -1: q.append(a); s[a] = x
if not all([a != -1 for a in s]): print('No')
else:
    print('Yes')
    for i in s[2:]: print(i)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

n, m = l()
g = [[] for i in range(n)]
for i in range(m):
    a, b = l()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = deque([0])
d = [-1] * n
d[0] = 0
while q:
    v = q.popleft()
    for w in g[v]:
        if d[w] != -1:
            continue
        d[w] = v
        q.append(w)
if -1 in d:
    print("No")
else:
    print("Yes")
    for di in d[1:]:
        print(di+1)

Submission status: Accepted

Solution code:
#create date: 2020-07-02 22:54

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m = na()
    g = [[] for i in range(n)]
    for i in range(m):
        a, b = na()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    q = deque([0])
    d = [-1] * n
    d[0] = 0
    while q:
        v = q.popleft()
        for w in g[v]:
            if d[w] != -1:
                continue
            d[w] = v
            q.append(w)
    if -1 in d:
        print("No")
    else:
        print("Yes")
        for di in d[1:]:
            print(di+1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

from collections import deque

def bfs(graph, queue, dist, prev):
    while queue:
        current = queue.popleft()

        for n in graph[current]:
            if dist[n] != -1:
                continue
            else:
                dist[n] = dist[current] + 1
                prev[n] = current
                queue.append(n)

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

bfs(graph, queue, dist, prev)

if -1 in prev:
    print('No')
else:
    print('Yes')
    for i in range(2, n+1):
        print(prev[i])

Submission status: Accepted

Solution code:
import sys


# import math
import heapq

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

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

    point = [0] *(n+1) #未踏0 その他　親
    d = deque([1])

    while len(d) > 0:
        p = d.popleft()
        for v in room[p]:
            if point[v] ==0:
                d.append(v)
                point[v] =p

    if 0 in point[1:]:
        print('No')
    else:
        print("Yes")
        print("\n".join(map(str,point[2:])))












if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
from collections import deque
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)

dist = [float('inf')]*(N)
ans = [0]*N
dist[0] = 0
q = deque([])
q.append((0,0))
while q:
    idx,d = q.popleft()
    for nxt in g[idx]:
        if d + 1 < dist[nxt]:
            ans[nxt] = idx+1
            dist[nxt] = d+1
            q.append((nxt,d+1))
for i in range(N):
    if dist[i]==float('inf'):
        print('No');exit()
print('Yes')
for i in range(1,N):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
q=deque()
def MI(): return map(int, input().split())
N,M=MI()
g=[[] for _ in range(N+1)]
for _ in range(M):
  a,b=MI()
  g[a].append(b)
  g[b].append(a)
check=[0]*(N+1)
check[1]=1
ans=[0]*(N+1)
q.append(1)
while len(q)>0:
  v=q.popleft()
  for u in g[v]:
    if check[u]==0:
      check[u]=1
      ans[u]=v
      q.append(u)
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Submission status: Accepted

Solution code:
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)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
ans=[0]*(n+1)
while len(q)!=0:
  v=q.popleft()
  for u in g[v]:
    if check[u]==0: #まだ探索していない頂点について、その頂点に親の頂点に移動する道しるべを置く
      check[u]=1
      ans[u]=v
      q.append(u)
print('Yes')
for i in range(2,n+1):
  print(ans[i])

Submission status: Accepted

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

N,M = list(map(int, input().rstrip().split()))
AB_list = [list(map(int, input().rstrip().split())) for i in range(M)]
#-----

edge_dic = {}

# "idx 0" doesn't use
# 1: visited, 0: not visited
visited = [1] + [0]*N

# We use on and after "idx 2"
guidepost = [0]*2 + [None]*(N-1)


for a,b in AB_list:
    edge_dic.setdefault(a, [])
    edge_dic[a].append(b)
    
    edge_dic.setdefault(b, [])
    edge_dic[b].append(a)


queue = deque([1])
visited[1] = 1

while queue:
    current = queue.popleft()
    
    for next_room in edge_dic[current]:
        if visited[next_room] == 0:
            guidepost[next_room] = current
            visited[next_room] = 1
            queue.append(next_room)


if (visited.count(0) == 0) and (guidepost.count(None) == 0):
    print("Yes")
    
    for num in guidepost[2:]:
        print(num)
    
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

point = [0 for i in range(n)]
d = deque([0])

while len(d) > 0:
    p = d.popleft()
    for v in room[p]:
        if point[v-1] == 0:
            d.append(v-1)
            point[v-1] = p+1

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

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/abc168/submissions/13358850
from collections import deque

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

    queue = deque([1])
    signposts = [0] * (N+1)
    signposts[1] = 1
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not signposts[v]:
                signposts[v] = u
                queue.append(v)

    if all(signposts[2:]):
        print("Yes")
        print("\n".join(map(str,signposts[2:])))
    else:
        print("No")
resolve()

Submission status: Accepted

Solution code:
import sys, math

input = sys.stdin.readline

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

cost = [[math.inf, -1]]*N
cost[0] = [0, 0]
pre = [0]

for d in range(N):
    next = []
    for i in pre:
        for j in path[i]:
            if cost[j][0] != math.inf:
                continue
            cost[j] = [d, i]
            next.append(j)
    pre = next
    if len(next)==0:
        break

if max(cost)[0] == math.inf:
    print('No')
    sys.exit()

print('Yes')
for d, pre_idx in cost[1:]:
    print(pre_idx+1)

Submission status: Accepted

Solution code:
import sys, heapq, math

input = sys.stdin.readline

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

h = [(0, 0, 0)] # 距離, id, 直前のid
heapq.heapify(h)
cost = [[math.inf, -1]]*N

while len(h) != 0:
    d, idx, pre_idx = heapq.heappop(h)
    if cost[idx][0] <= d:
        continue
    cost[idx] = [d, pre_idx]
    for next_idx in path[idx]:
        if cost[next_idx] == math.inf:
            continue
        heapq.heappush(h, (d+1, next_idx, idx))

if max(cost)[0] == math.inf:
    print('No')
    sys.exit()

print('Yes')
for d, pre_idx in cost[1:]:
    print(pre_idx+1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
route = [[] for _ in range(n+1)]
ans = [0]*n

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

q = [1]
l = set()

while True:
    if len(q) == 0:
        break
    p = q.pop(0)
    for i in route[p]:
        if i not in l:
            l.add(i)
            ans[i-1] = p
            q.append(i)

if ans.count(0) > 1:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(ans[i])

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)
queue=[0]
visit=[0]*n
visit[0]=1
ans=[0]*n

while len(queue)>0: 
  now=queue.pop(0)
  for p in l[now]:
    if visit[p]==0:
      visit[p]+=1
      queue.append(p)
      ans[p]=now+1
k=ans[1:]
if not all(kk!=0 for kk in k):
  print('No')
  exit()
print('Yes')
for kk in k:
  print(kk)

Submission status: Accepted

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

for i in range(m):
    c,d = map(int, input().split())
    if c not in root:
        root[c] = []
    if d not in root:
        root[d] = []
    root[c].append(d)
    root[d].append(c)
sirusi = [0] *(n+1)
dp = [2*m] * (n+1)
dp[1]=0
before = [1]
while True:
    tmp=[]
    flag=0
    for b in before:
        for r in root[b]:
            if dp[r] > dp[b] +1:
                dp[r] = dp[b] +1
                sirusi[r] = b
                flag += 1
                tmp.append(r)
    before = tmp
    if flag == 0:
        break

if sirusi.count(0)>2:
    print("No")
    exit()

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

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop
N, M = map(int, input().split())

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

task = [] 
used = [0 for _ in range(N)]
min_len = [0 for _ in range(N)]
length = [10**20 for _ in range(N)]
prev_points = [0 for _ in range(N)]
heappush(task, (0, 0, -1))
print("Yes")

while task:
  while task:
    l, p, prev = heappop(task)    
    if used[p] == 0:
      break
  #print(task)
  used[p] = 1
  min_len[p] = l
  prev_points[p] = prev +1 #番号を1ずらす
  
  for j in I[p]:
    if used[j] == 1: continue
    #print(p,j)
    if length[j] > l+1:
      length[j] = l+1
      heappush(task, (l+1, j, p))
    
for i in range(1, N):
  print(prev_points[i])

Submission status: Accepted

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

ans = [0]*(n-1)

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if ans[i-2] != 0 or i == 1:
            continue
        ans[i-2] = v
        d.append(i)
        
print('Yes')
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def main():
	
	from collections import deque
	n,m = map(int,input().split())
	l = [list(map(int, input().split())) for i in range(m)]
	graph = [[] for _ in range(n+1)]
	
	for i in range(m):
		a,b = l[i]
		graph[a].append(b)
		graph[b].append(a)

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

	d = deque()
	d.append(1)

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

	if graph[1] == '':
		print("No")
	else:
		print("Yes")
		for i in range(2,n+1):
			if dist[i] == 1:
				print(1)
			else:
				for room in range(len(graph[i])):
					if dist[i]-1 == dist[graph[i][room]]:
						print(graph[i][room])
						break
	


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

#a,b = 1 2 (頂点1,2が隣接)
#a,b = 2 3 (頂点2,3が隣接)
#a,b = 3 4 (頂点3,4が隣接)
#a,b = 4 2 (頂点2,2が隣接)

#G = [[],[2],[1,3,4],[2,4],[3,2]]

ans = [0] * (n-1)

d = deque()
d.append(1)
#頂点1を訪問した

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

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

Submission status: Accepted

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

q = [1]
visited = [-1] * (n + 1)

visited[1] = 0
while q:
    node = q.pop(0)
    for i in path[node]:
        if visited[i] == -1:
            q.append(i)
            visited[i] = node

if any([True for v in visited[2:] if v == -1]):
    print("No")
else:
    print("Yes")
    for v in visited[2:]:
        print(v)

Submission status: Accepted

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

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

list_tonari=[[] for i in range(n+1)]

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

const_vary=list()


while True:
  const_vary=const
  const=[]
  
  while len(const_vary):
    get=const_vary.pop()
    
    for n in list_tonari[get]:
      if ans[n] ==0:
        ans[n]=get
        list_tonari[n].remove(get)
        const.append(n)
        
  if len(const)==0:
    break
    
print("Yes")
for n in ans[2:]:
  print(n)

Submission status: Accepted

Solution code:
from collections import deque

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

way = {}
for i in range(m):
    a, b = map(int, input().split())
    if a not in way:
        way[a] = []
    if b not in way:
        way[b] = []
    way[a].append(b)
    way[b].append(a)

queue = deque([1])
ok = set([1])
ans = [0] * (n+1)

while queue:
    now = queue.popleft()
    for i in way[now]:
        if i in ok:
            continue
        ans[i] = now
        queue.append(i)
        ok.add(i)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, M = MI()
    E = [[] for _ in range(N)]
    for i in range(M):
        a, b = MI1()
        E[a].append(b)
        E[b].append(a)
    q = deque([0])
    used = [0] * N
    used[0] = 1
    ans = [0] * N
    ans[0] = 'Yes'
    while q:
        v = q.popleft()
        for nv in E[v]:
            if used[nv]: continue
            used[nv] = 1
            ans[nv] = v+1
            q.append(nv)
    printlist(ans, '\n')


if __name__ == '__main__':
    solve()

Submission status: Accepted

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


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, M = na()
node_dic = {}
for _ in range(M):
    A, B = na()
    if B in node_dic:
        node_dic[B].append(A)
    else:
        node_dic[B] = [A]
    if A in node_dic:
        node_dic[A].append(B)
    else:
        node_dic[A] = [B]


edge = deque()
edge.append(1)
d = [-1] * N
d[0] = 0
while len(edge):
    e = edge.popleft()
    for ee in node_dic[e]:
        if d[ee - 1] == -1:
            d[ee - 1] = e
            edge.append(ee)
if -1 in d:
    print("No")
else:
    print("Yes")
    print("\n".join(map(str, d[1:])))

Submission status: Accepted

Solution code:
from collections import deque

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

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

q = deque([1])
dist = [-1] * (n + 1)
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        q.append(u)
        dist[u] = v

print("Yes")
# print(dist)

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
lndmrk=[-1]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    e[a].append(b)
    e[b].append(a)
q=deque()
lndmrk[1]=0
q.append(1)
while(len(q) !=0):
    v=q.popleft()
    for i in e[v]:
        if lndmrk[i]==-1:
            lndmrk[i]=v
            q.append(i)
f=True
for i in range(2,n+1):
    if lndmrk[i]==-1:
        f=False
        break
if f:
    print('Yes')
    for i in range(2,n+1):
        print(lndmrk[i])
else:
    print('No')