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

def bfs():
    d = deque()
    d.append(0)
    while d:
        now = d.popleft()
        for i in l[now]:
            if reached[i] == -1:
                reached[i] = now
                d.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int, input().split())
dic = {} 

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

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

array = [-1] * (n+1)

d = deque()
d.append(1)

while len(d) != 0:
  tmp = d.popleft()
  arr = dic.get(tmp, [])
  
  for v in arr:
    if array[v] == -1:
      array[v] = tmp
      d.append(v)
      
print('Yes')
for i in range(2,n+1):
  print(array[i])

Submission status: Accepted

Solution code:
from collections import deque


n, m = map(int, input().split())
edg = [[] for i in range(n+1)]
ans = [-1]*(n+1)


for _ in range(m):
	u, v = map(int, input().split())
	edg[u].append(v)
	edg[v].append(u)



def bfs():
	q = deque()
	q.append(1)
	ans[1] = 1

	while q:
		top = q[0]
		q.popleft()
		for child in edg[top]:
			if ans[child] == -1:
				# print(str(top) + " --> " + str(child))
				ans[child] = top
				# print(ans[child])
				q.append(child)


bfs()
if -1 in ans[1:]:
	print("No")
else:
	print("Yes")
	for i in ans[2:]:
		print(i)

Submission status: Accepted

Solution code:
from collections import deque

n,m=map(int,input().split())
turo=[[] for _ in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  turo[a].append(b)
  turo[b].append(a)
  
q=deque([1])
heya=[0]*(n+1)
heya[1]=1
mejirushi=[0]*(n+1)
while len(q)!=0:
  v=q.popleft()
  for i in turo[v]:
    if heya[i]==0:
      heya[i]=1
      mejirushi[i]=v
      q.append(i)
print("Yes")
for i in range(2,n+1):
  print(mejirushi[i])

Submission status: Accepted

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

q = deque([0])
d = [-1 for _ in range(N)]
d[0] = 0
ans = [0]*N
while q:
    p = q.popleft()
    for node in G[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node)
        else:
            if d[node] + 1 == d[p]:
                ans[p] = node + 1
print('Yes')
for i in range(1, N):
    print(ans[i])

Submission status: Accepted

Solution code:
import copy
import collections
import numpy as np

class Graph(object):
    def __init__(self, v, e):
        self.v = [i for i in range(v)]
        self.e = e
    
    def nodes(self):
        return self.v
    
    def edges(self, v):
        return self.e[v]

def bfs(G):
    V = copy.copy(G.nodes())
    deq = collections.deque([V[0]])
    searched = {v:False for v in V}
    searched[V[0]] = True
    T = [0] * len(G.v)
    while len(deq) != 0:
        v = deq.popleft()
        edges = [(v,i) for i in G.edges(v) if not searched[i]]
        for edge in edges:
            v,i = edge
            deq.append(i)
            T[i] = v+1
            searched[i] = True
    return T

if __name__ == "__main__":
    n,m = map(int,input().split())
    e = [[]*n 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)
    
    G = Graph(n,e)

    T = bfs(G)
    print("Yes")
    print(*T[1:],sep="\n")

Submission status: Accepted

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


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


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


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

q = queue.Queue()
for p in path[1]:
    q.put((1, p))

while not q.empty():
    current, to = q.get()
    if flag_directions[to] == -1:
        flag_directions[to] = current 
        for next_room in path[to]:
            q.put((to, next_room))


print('Yes')
for f in flag_directions[2:]:
    print(f)

Submission status: Accepted

Solution code:
import queue
N,M=map(int,input().split())
ans=[0] * N
q=queue.Queue()
q.put(1)

import sys
s = sys.stdin.readlines()
G=[[] for _ in range(N)]

for e in s:
  a, b = map(int, e.split())
  G[a-1].append(b)
  G[b-1].append(a)
  
c=0

while c!=N-1:
  r=q.get()
  for i in G[r-1]:
    if ans[i-1]==0 and i!=1:
      ans[i-1]=r
      q.put(i)
      c+=1

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    ab = [LI() for _ in range(m)]
    e = collections.defaultdict(set)
    for a,b in ab:
        e[a].add(b)
        e[b].add(a)

    v = set()
    v.add(1)
    r = [0] * (n+1)
    q = [1]
    qi = 0
    while len(q) > qi:
        t = q[qi]
        qi += 1
        for u in e[t]:
            if u not in v:
                v.add(u)
                r[u] = t
                q.append(u)

    return JA(["Yes"] + r[2:], "\n")

print(main())

Submission status: Accepted

Solution code:

import sys, os, re
from pprint import pprint
from math import sin, cos, sqrt, radians

n, m = list(map(int, sys.stdin.readline().strip().split()))
g = [[] for x in range(n)]

for i in range(m):
    x, y = map(int, sys.stdin.readline().strip().split())
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

if [] in g:
    print("No")
    exit(0)

ans = {0: -1}
tmp = [0]

while len(ans) < n:
    tmp_next = []
    for k in tmp:
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                tmp_next.append(node) 
                flag = True

        tmp = tmp_next
        if flag == False:
            break

    """
    flag = False    
    for k, v in list(ans.items()):
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                flag = True
    if flag == False:
        break
    """

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

Submission status: Accepted

Solution code:
import queue
q=queue.Queue()
n,m=map(int,input().split())
room=[]
singpost=[0]*(n+1)
 
for i in range(n+1):
    room.append([])
 
for _ in range(m):
    r1,r2=map(int,input().split())
    if r1==1 :
        singpost[r2]=1
        q.put(r2)
    elif r2==1:
        singpost[r1]=1
        q.put(r1)
    else:
        room[r1].append(r2)
        room[r2].append(r1)
 
while not(q.empty()):
    loca=q.get()
    for x in room[loca]:
        if singpost[x]==0:
            singpost[x]=loca
            q.put(x)
 
if singpost.count(0)>2:print("No")
else:
    print("Yes")
    for x in range(2,n+1):
        print(singpost[x])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    path[A-1].append(B)
    path[B-1].append(A)
parent = [-1 for _ in range(N)]
parent[0] = 0

current_positions = [1]
while current_positions:
    next_positions = []
    for current_position in current_positions:
        for n_p in path[current_position - 1]:
            if parent[n_p - 1] == -1:
                parent[n_p - 1] = current_position
                next_positions.append(n_p)
    current_positions = next_positions

for v in parent:
    if v == -1:
        print('No')
        exit()

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

Submission status: Accepted

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

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

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

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

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

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

d=deque()
seen=[-1]*n
d.append(0)

while d:
  vi=d.popleft()
  for i in node[vi]:
    if seen[i]==-1:
      d.append(i)
      seen[i]=vi

if "-1" in seen:
  print("No")
else:
  print("Yes")
  for i in range(1,len(seen)):
    print(seen[i]+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

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

par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

N, M=map(int, sys.stdin.readline().split())
p = []
for i in range(M):
    p.append(list(map(int, sys.stdin.readline().split())))

graph = [[] for _ in range(N + 1)]
for pi in p:
    graph[pi[0]].append(pi[1])
    graph[pi[1]].append(pi[0])

q = deque([1])
p = [0] * (N + 1)
p[1] = 1
while q:
    u = q.popleft()
    for v in graph[u]:
        if not p[v]:
            p[v] = u
            q.append(v)
            
result = p[2:]
        
if all(result):
    print("Yes")
    [print(r) for r in result] 
else:
    print("No")

Submission status: Accepted

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

seen=[False]*n
depth=[-1]*n
todo=deque([])
todo.append(0)
depth[0]=1

    
while len(todo)>0:
    p=todo[0]
    
    seen[p]=True
    to=node[p]
    for i in to:
        if seen[i]:continue
        if depth[i]==-1:
            depth[i]=depth[p]+1
            todo.append(i)
    todo.popleft()
 
 

if min(depth)==-1:
    print('No')
else:
    print("Yes")
    for i in range(1,n):
        for j in node[i]:
            if depth[i]>depth[j]:
                print(j+1)
                break

Submission status: Accepted

Solution code:
from collections import deque

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,m = nm()

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

for i in range(m):
  a,b = nm()
  p[a-1].append(b-1)
  p[b-1].append(a-1)

visited = [False]*n

visited[0]=True

q = deque()
q.append(0)

ans = [0]*n

while len(q) > 0:
  num = q.popleft()
  for i in p[num]:
    if visited[i]:
      continue
    ans[i]=num+1
    visited[i]=True
    q.append(i)

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

Submission status: Accepted

Solution code:

roomNum, aisleNum = map(int, input().split())
aisles = [ list(map(int, input().split())) for _ in range(aisleNum) ]

aisleTree = [ [] for _ in range(roomNum+1) ]

for roomA, roomB in aisles:
    aisleTree[roomA].append(roomB)
    aisleTree[roomB].append(roomA)

from collections import deque
que = deque()
distanceFromRoom1 = [-1] * (roomNum+1)
distanceFromRoom1[0] = 0
distanceFromRoom1[1] = 0
for room in aisleTree[1]:
    que.append(room)
    distanceFromRoom1[room] = 1

while que:
    room = que.popleft()
    dist = distanceFromRoom1[room]
    for nextRoom in aisleTree[room]:
        if distanceFromRoom1[nextRoom] == -1:
            que.append(nextRoom)
            distanceFromRoom1[nextRoom] = room

if min(distanceFromRoom1) == -1:
    print('No')
else:
    print('Yes')
    for ans in distanceFromRoom1[2:]:
        print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(N + 1)]
for i in range(M):
  graph[a[i]].append(b[i])
  graph[b[i]].append(a[i])

    # bfs
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")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
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]
isSearched = [False]*(n+1)
isSearched[0] = True
cnt_l = [0]*(n+1)
pre = [-1]*n
def bfs():
    while(queue):
        now = queue.pop(0)
        
        for x in l[now]:
            if(isSearched[x]):
                continue
            cnt_l[x] = cnt_l[now]+1
            pre[x] = now+1
            isSearched[x] = True
            queue.append(x)
bfs()

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

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
v = [[] for i in range(n)]
f = [False]*n
step = [-1]*n
for i in range(m):
    a,b = map(int,input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
q = deque([(0,0)])
while(q):
    vi,s = q.popleft()
    #print(vi,s)
    if not(f[vi]):
        f[vi]=True
        step[vi]=s
        s+=1
        for vij in v[vi]:
            q.append((vij,s))
print("Yes")
for i in range(1,n):
    si = step[i]
    for vij in v[i]:
        if step[vij]==si-1:
            print(vij+1)
            break

Submission status: Accepted

Solution code:
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def solve():
  N, M = read_int_list()
  A = [0] * M
  B = [0] * M
  v = [set() for i in range(N)] 
  for i in range(M):
    A[i], B[i] = read_int_list()
    v[A[i] - 1].add(B[i])
    v[B[i] - 1].add(A[i])

  res = [0] * (N - 1)
  done = set()
  l = set([1])
  for i in range(N):
    l2 = set()
    for t in l:
      for r in v[t - 1]:
        if r not in l and r not in done:
          l2.add(r) 
          res[r - 2] = t

    # done = done.union(set(l))
    done.update(l)
    l = l2

  return res


def solve0():
  N, M = read_int_list()
  A = [0] * M
  B = [0] * M
  v = [set()] * N
  for i in range(M):
    A[i], B[i] = read_int_list()
    v[A[i] - 1].add(B[i])
    v[A[i] - 1].add(B[i])

  res = [0] * (N - 1)
  done = set()
  l = set([1])
  for i in range(N):
    l2 = set()
    for k in range(M):
      for t in l:
        if t == A[k]:
          if B[k] not in l and B[k] not in done:
            l2.add(B[k]) 
            res[B[k] - 2] = A[k]

        if t == B[k]:
          if A[k] not in l and A[k] not in done:
            l2.add(A[k])
            res[A[k] - 2] = B[k]

    # done = done.union(set(l))
    done.update(l)
    l = l2

  return res


def main():
    res = solve()
    print('Yes', *res, sep='\n')


main()

Submission status: Accepted

Solution code:
import queue
q = queue.Queue()
bool = True


def bfs():
    q.put(0)
    while not q.empty():
        now = q.get()
        for i in nodes[now]:
            if dist[i] != -1:
                continue
            dist[i] = dist[now] + 1
            q.put(i)
            ans[i] = now
    bool = False


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

dist = [-1] * N
ans = [-1] * N
bfs()
if bool:
    print("Yes")
    for i in range(1, N):
        print(ans[i]+1)
else:
    print("No")

Submission status: Accepted

Solution code:
import copy
import queue
q = queue.Queue()
N, M = map(int, input().split())
nodes = [[] for i in range(N)]
idxStock = []
for i in range(M):
    a, b = map(int, input().split())
    nodes[a - 1].append(b - 1)
    nodes[b - 1].append(a - 1)

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

q.put(0)
while not q.empty():
    now = q.get()
    for i in nodes[now]:
        if dist[i] != -1:
            continue
        dist[i] = dist[now] + 1
        q.put(i)
        ans[i] = now
print("Yes")
for i in range(1, N):
    print(ans[i]+1)

Submission status: Accepted

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

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

from collections import deque
arrow = [0]*n
def bfs(u, n):
    queue = deque([u]) # uからの距離の初期化
    d = [False]*n
    d[u] = 1
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i]:continue
            d[i] = True
            arrow[i] = v
            queue.append(i)
    return arrow

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split(' '))
c = [[] for i in range(n)]
r = [0] * n
q = deque()
for i in range(m):
    a, b = map(int, input().split(' '))
    c[a - 1].append(b - 1)
    c[b - 1].append(a - 1)
q.append(0)
while len(q) > 0:
    ix = q.popleft()
    for i in c[ix]:
        if r[i] == 0:
            r[i] = ix + 1
            q.append(i)

jg = 'Yes' if r.pop(0) > 0 else 'No'
print(jg)
for i in r:
    print(i)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

gw = [0]*(N+1)
gw[1] = 1
ng=1
hq = []
heapq.heapify(hq) 
heapq.heappush(hq,(0,1))
while hq:
  c, n = heapq.heappop(hq)
  for i in node[n]:
    if gw[i] == 0:
      gw[i] = n
      ng += 1
      heapq.heappush(hq,(c+1,i))
#
if ng < N:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(gw[i])
#

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
que = deque()
que.append(1)
rote = [0]*(n+1)
rote[1] = -1
while que:
    now = que.popleft()
    nx = g[now]
    for next_room in nx:
        if  rote[next_room] == 0:
            rote[next_room] = now
            que.append(next_room)

flag = True
for i in range(2,n+1):
    if rote[i] == 0:
        flag = False
if flag:
    print("Yes")
    for j in range(2,n+1):
        print(rote[j])
    exit()
else:
    print("No")

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)
    

queue = deque([0])
d = [None]*n
d[0] = 0
while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] == None:
            d[i] = v + 1
            queue.append(i)
            
if all(type(i) is int for i in d):
    print('Yes')
    for i in d[1:]:
        print(i)
else:
    print('No')

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)
    

queue = deque([0])
d = [None]*n
d[0] = 0
while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] == None:
            d[i] = v + 1
            queue.append(i)
            
if all(type(i) is int for i in d):
    print('Yes')
    for i in d[1:]:
        print(i)
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque

# 入力
n, m = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
# 処理
q = deque([0])
dist = [1000000000] * n
pre = [-1] * n
dist[0] = 0 # 始点
q.append(0)
while q:
    v = q.popleft()
    for i in to[v]:
        if dist[i] != 1000000000:
            continue
        dist[i] = dist[v] + 1
        pre[i] = v
        q.append(i)
print("Yes")
for i in range(n):
    if i == 0:
        continue
    ans = pre[i]
    ans += 1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

while d:
    hop = d.popleft()
    for i in path[hop]:
        if dis[i-1] == -1:
            d.append(i-1)
            dis[i-1] = hop+1
            
if -1 in dis:
    print('No')
else:
    print('Yes')
    for i in range(1,len(dis)):
        print(dis[i])

Submission status: Accepted

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

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

ct = [-1]*N

i = 0
stack = []
ct[0] = 0
stack.append(0)
while len(stack) != 0:
  v = stack.pop(0)
  for e in node[v]:
    if ct[e] == -1:
      ct[e] = v
      stack.append(e)

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

Submission status: Accepted

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

ans = [-1]*(n+1)
que = deque([1])
while que:
    q = que.popleft()
    for i in ab[q]:
        if ans[i] == -1:
            que.append(i)
            ans[i] = q
print('Yes')
for i in range(2, n+1):
    print(ans[i])

Submission status: Accepted

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

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

ct = [-1]*N

i = 0
queue = []
ct[0] = 0
queue.append(0)
while len(queue) != 0:
  v = queue.pop(0)
  for e in node[v]:
    if ct[e] == -1:
      ct[e] = v
      queue.append(e)

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

Submission status: Accepted

Solution code:
from collections import deque
n,m = [int(x) for x in input().split()]

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

for _ in range(m):
    u,v = [int(x) for x in input().split()]
    g[u].append(v)
    g[v].append(u)


vis = [0]*(n+1)

d = deque()
for x in g[1]:
    vis[x] = 1
    d.append(x)


while d:
    cur = d.popleft()

    for x in g[cur]:
        if vis[x] == 0:
            vis[x] = cur
            d.append(x)


vis[0],vis[1] = 1,1

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

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [None] * (N+1)
    signpost[0] = signpost[1] = 0
    q = deque([1])
    dist = [0 for i in range(N+1)]
    while q:
        node = q.popleft()
        for e in edge[node]:
            if signpost[e] is None:
                dist[e] = dist[node] + 1
                signpost[e] = node
                q.append(e)
    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - .. (Double Dots)
from collections import deque


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

    print("Yes")
    print("\n".join(map(str, signposts[2:])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N,M,*AB=map(int,open(0).read().split())
to=[[] for _ in range(N)]

for a,b in zip(*[iter(AB)]*2):
  to[a-1].append(b-1)
  to[b-1].append(a-1)
  
q=deque([0])
r=[None]*N

while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
      
print("Yes",*r[1:],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
def main():
	N,M,*AB=map(int,open(0).read().split())
	to=[[] for _ in range(N+1)]
	for a,b in zip(*[iter(AB)]*2):
		to[a].append(b)
		to[b].append(a)
	q=deque([1])
	r=[None]*(N+1)
	while q:
		x=q.popleft()
		for i in to[x]:
			if r[i] is None:
				q.append(i)
				r[i]=x
	print("Yes",*r[2:],sep="\n")
if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque
N,M,*AB=map(int,open(0).read().split())
to=[[] for _ in range(N+1)]
for a,b in zip(*[iter(AB)]*2):
  to[a].append(b)
  to[b].append(a)
q=deque([1])
r=[None]*(N+1)
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x
print("Yes",*r[2:],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
def main():
	N,M,*AB=map(int,open(0).read().split())
	to=[[] for _ in range(N)]
	for a,b in zip(*[iter(AB)]*2):
		to[a-1].append(b-1)
		to[b-1].append(a-1)
	q=deque([0])
	r=[0]*N
	while q:
		x=q.popleft()
		for i in to[x]:
			if not r[i]:
				q.append(i)
				r[i]=x+1
	print("Yes",*r[1:],sep="\n")
if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
	N,M,*AB=map(int,open(0).read().split())
	to=[[] for _ in range(N)]
	for a,b in zip(*[iter(AB)]*2):
		to[a-1].append(b-1)
		to[b-1].append(a-1)
	q=deque([0])
	r=[None]*N
	while q:
		x=q.popleft()
		for i in to[x]:
			if not r[i]:
				q.append(i)
				r[i]=x+1
	print("Yes",*r[1:],sep="\n")
if __name__=='__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
	N,M,*AB=map(int,open(0).read().split())
	to=[[] for _ in range(N)]
	for a,b in zip(*[iter(AB)]*2):
		to[a-1].append(b-1)
		to[b-1].append(a-1)
	q=deque([0])
	r=[None]*N
	while q:
		x=q.popleft()
		for i in to[x]:
			if r[i] is None:
				q.append(i)
				r[i]=x+1
	print("Yes",*r[1:],sep="\n")
if __name__=='__main__':
	main()

Submission status: Accepted

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

done=[False for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True:
        continue
      ans[i]=now+1
      done[i]=True
      stack.append(i)

bfs()
print("Yes")
print(*ans[1:])