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: Runtime Error

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

P = {}
A = []
B = []

for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

for i in range(1, N + 1):
    P[i] = []

for a, b in zip(A, B):
    P[b].append(a)
    P[a].append(b)

ans = [0] * (N + 1)
ans[1] = 1

def search(numbers):
    next_numbers = []
    for number in numbers:
        for x in P[number]:
            if ans[x] == 0:
                ans[x] = number
                next_numbers.append(x)
    if next_numbers:
        search(next_numbers)

search([1])

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

Submission status: Runtime Error

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

P = {}

for i in range(1, N + 1):
    P[i] = []

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

ans = [0] * (N + 1)
ans[1] = 1

def search(numbers):
    next_numers = []
    for number in numbers:
        for x in P[number]:
            if ans[x] == 0:
                ans[x] = number
                next_numers.append(x)
    if next_numers:
        search(next_numers)


search([1])

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

Submission status: Runtime Error

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

P = {}

for i in range(1, N + 1):
    P[i] = []

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

ans = [0] * (N + 1)
checker = [0] * (N + 1)
checker[1] = 1

def search(number, level):
    level += 1
    for x in P[number]:
        if checker[x] == 0:
            checker[x] = level
            ans[x] = number
            search(x, level)
        elif checker[x] > level:
            checker[x] = level
            ans[x] = number
            search(x, level)


search(1, 0)

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

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
road=[[] for i in range(m)]
#隣接行列表現だとo(n^2)で間に合わないので隣接リスト表現でいく
for i in range(m):
  a,b=list(map(int,input().split()))
  road[a-1].append(b)
  road[b-1].append(a)
from collections import deque
q=deque([1])
check=[0 for i in range(n)]
check[0]=1
ans=[0 for i in range(n)]
while len(q)>0:
  p=q.popleft()
  for i in range(len(road[p-1])):
    if check[road[p-1][i]-1]==0:
      q.append(road[p-1][i])
      check[road[p-1][i]-1]=1
      ans[road[p-1][i]-1]=p
print("Yes")

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
road = [[] for _ in range(M+1)]
ans = [-1]*(N+1)
d = deque()
for i in range(M):
    A, B = map(int, input().split())
    road[A].append(B)
    road[B].append(A)
d.append(1)
while len(d) != 0:
    look = d.popleft()
    for i in road[look]:
        if ans[i] == -1:
            d.append(i)
            ans[i] = look

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

Submission status: Runtime Error

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

graph = [[0]] + [[] for _ in range(N)]
weight = [0, 0] + [10**6 for _ in range(N-1)]

def search(N):
    for r in graph[N]:
        if weight[r] > weight[N] + 1:
            weight[r] = weight[N] + 1
            search(r)

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

search(1)

if 10**6 not in weight:
    print("Yes")
    
    for i in range(2, len(graph)):
        min_cost = 10**6
        min_route = -1
        for j in range(len(graph[i])):
            if min_cost >= weight[graph[i][j]]:
                min_cost = weight[graph[i][j]]
                min_route = j
        print(graph[i][min_route])

else:
    print("No")

Submission status: Runtime Error

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

a = [0] * (m + 1)
b = [0] * (m + 1)
road = [[] for _ in range(m + 1)]

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

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

q = deque()
q.appendleft(1)

while len(q):
    i = q.pop()
    for j in road[i]:
        if ans[j] == -1:
            ans[j] = i
            q.appendleft(j)

if ans.count(-1) != 0:
    print("No")
    exit()
else:
    print("Yes")
    print(*ans[2:], sep="\n")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst=[[] for i in range(n)]
visited=[True]+[False]*(n-1)
ans=[0]*n

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

Q=[0]

While Q:
  v=Q.pop(0)
  for i in lst[v]:
        if visited[i]==False:
              visited[i]=True
              ans[i]=v
              Q.append(v)

print('Yes')

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

Submission status: Runtime Error

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


def search(now,sum) :
    if depth[now]!=0 : #すでに訪れていた場合
        sum+=1
        if sum<depth[now] :
            depth[now]=sum
            for i in A[now] :
                now=i
                search(now,sum)

    if depth[now]==0 :
        sum+=1
        depth[now]=sum
        for i in A[now] :
            now=i
            search(now,sum)
 
    return depth

B=search(0,0)
if B.count(0)==0 :
    print("Yes")
    for i in B[1:] :
        print(i-1)

else :
    print("No")

Submission status: Runtime Error

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy

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

road = [ [] for i in range(N) ]

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

rets_ct = [N for i in range(N)]
rets = [0 for i in range(N)]

def dfs(second, num, ct, done):
    global road, rets_ct, rets
    
    if ct > rets_ct[start]:
        return

    if num == 0:
        rets[start] = second
        rets_ct[start] = ct
        return

    if done[num]:
        return
    done[num] = 1
    
    ct += 1
    next = road[num]
    for i in next:
        if second == 0:
            dfs(i, i, ct, copy.copy(done))
        else:
            dfs(second, i, ct, copy.copy(done))

for start in range(1, N):
    ct = 0
    done = [0 for i in range(N)]
    dfs(0, start, ct, done)

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

Submission status: Runtime Error

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy

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

road = [ [] for i in range(N) ]

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

rets_ct = [N for i in range(N)]
rets = [0 for i in range(N)]

def dfs(second, num, ct, done):
    global road, rets_ct, rets
    
    if num == 0:
        if rets_ct[start] > ct:
            rets[start] = second
            rets_ct[start] = ct

    if done[num]:
        return
    done[num] = 1
    
    ct += 1
    next = road[num]
    for i in next:
        if second == 0:
            dfs(i, i, ct, copy.copy(done))
        else:
            dfs(second, i, ct, copy.copy(done))


for start in range(1, N):
    ct = 0
    done = [0 for i in range(N)]
    dfs(0, start, ct, done)

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

Submission status: Runtime Error

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy

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

road = [ [] for i in range(N) ]

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

rets = [N for i in range(N)]

def dfs(start, num, ct, done):
    global rets, road
    
    if num == 0:
        rets[start] = min(rets[start], ct)

    if done[num]:
        return
    done[num] = 1
    
    ct += 1
    next = road[num]
    for i in next:
        dfs(start, i, ct, copy.copy(done))

for start in range(1, N):
    ct = 0
    done = [0 for i in range(N)]
    dfs(start, start, ct, done)

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

Submission status: Runtime Error

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy

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

road = [ [] for i in range(N) ]

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

print(road)
rets = [N for i in range(N)]

def dfs(start, num, ct, done):
    global rets, road
    
    print(start, done, num, ct)
    if num == 0:
        rets[start] = min(rets[start], ct)

    if done[num]:
        return
    done[num] = 1
    

    
    ct += 1
    next = road[num]
    for i in next:
        dfs(start, i, ct, copy.copy(done))

for start in range(1, N):
    ct = 0
    done = [0 for i in range(N)]
    dfs(start, start, ct, done)

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

Submission status: Runtime Error

Solution code:
from collections import deque

mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

N,M = MI()
links = [[] for _ in range(N)]

for _ in range(M):
    a, b = MI()
    a -= 1
    b -= 1
    links[a].append(b)
    links[b].append(a)

ans = [-1] * N
ans[0] = 0
q = deque([(0, 0)])
while q:
  print(ans)
  room, prev = q.popleft()
  for next_ in links[room]:
    if ans[next_] < 0:
      ans[next_] = room
      q.append((next_, room))
for i in range(1,N):
  print(ans[i]+1)

Submission status: Runtime Error

Solution code:
from collections import deque

mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

N,M = MI()
links = [[] for _ in range(N)]

for _ in range(M):
    a, b = MI()
    a -= 1
    b -= 1
    links[a].append(b)
    links[b].append(a)

ans = [-1] * N
ans[0] = 0
q = deque([(0, 0)])
while q:
    room, prev = q.popleft()
    for next_ in links[room]:
        if ans[next_] < 0:
            ans[next_] = ans[room+1]+1
            q.append((next_, room))
for i in range(1,N):
  print(ans[i])

Submission status: Runtime Error

Solution code:
"""AtCoder."""

from typing import List

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

ways = {}

for _ in range(m):
    a, b = input().split(' ')
    ways[a] = ways.get(a, []) + [b]
    ways[b] = ways.get(b, []) + [a]

success = False


def search(room, route):
    return [i for i in ways.get(room, []) if i not in route]


def get_routes(room, route=None, goal='1') -> List[List[str]]:
    if not route:
        route = [room]
    results = []
    next_rooms = search(room, route)

    if goal in next_rooms:
        results.append(route + [goal])
    else:
        for next_room in next_rooms:
            route.append(next_room)
            results += get_routes(next_room, route)

    return results


# print(ways)

for i in range(2, n + 1):
    # print('---------------------------------')
    # print(i)
    room = str(i)

    results = get_routes(room)
    # print(results)

    if len(results) > 0:
        if not success:
            success = True
            print('Yes')
        min_count = min(len(v) for v in results)
        print(min_count - 1)

if not success:
    print('No')

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,m = [int(x) for x in stdin.readline().rstrip().split()]

d = {}
for i in range(n):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]

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

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

sol = {}

m = [1]
while True:
    next_m = []
    for mm in m:
        b = d[mm]
        for bb in b:
            if bb not in sol:
                sol[bb] = mm
                next_m.append(bb)

    if len(next_m) == 0: break
    m = next_m

sol = sorted(sol.items())

print("Yes")
for v in sol[1:]:
    print(v[1])

Submission status: Runtime Error

Solution code:
#分析中。続きは明日。
from collections import deque
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
print(edges)  #

que = deque()
dist = [float('inf')] * n
dist[0] = 0
print(dist)#

prev = [-1] * n
print(prev)  #

que.append(0)
while que:
    now = que.popleft()
#    print(now)#
    for edge in edges[now]:
#        print(edge)  #
        print(dist[edge],dist[now])  #
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            prev[edge] = now + 1
            print(dist)
            print(prev)
            que.append(edge)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
input = sys.std.readline

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

que = deque()
dist = [float('inf')] * n
prev = [-1] * n
dist[0] = 0
que.append(0)
while que:
    now = que.popleft()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            prev[edge] = now + 1
            que.append(edge)


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

Submission status: Runtime Error

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

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

def dfs(v, u, depth):

    depth_min[v] = depth
    memo[v] = u

    for next_v in G[v]:
        if next_v == 0:
            continue
        if depth_min[next_v] > depth+1:
            dfs(next_v, v, depth+1)

depth_min = [float("inf")] * N
memo = [-1] * N
dfs(0, 0, 0)
if -1 in memo:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(memo[i]+1)

Submission status: Runtime Error

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

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

def dfs(v, u, depth):

    depth_min[v] = depth
    memo[v] = u

    for next_v in G[v]:
        if depth_min[next_v] > depth+1:
            dfs(next_v, v, depth+1)

depth_min = [float("inf")] * N
memo = [-1] * N
dfs(0, 0, 0)
if -1 in memo:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(memo[i]+1)

Submission status: Runtime Error

Solution code:
import networkx as nx
n, m = 4,4
AB = [[1,2],[2,3],[3,4],[4,2]]
G = nx.Graph()
G.add_nodes_from(range(1, n+1))
G.add_edges_from(zip(AB[::2], AB[1::2]))
print('Yes')
d = dict(nx.bfs_predecessors(G, 1))
for i in range(2, n+1):
    print(d[i])

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

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

Submission status: Runtime Error

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

turo = [[] for i in range(n)]
q = deque()
his = []

def root(x):
    if par[x] == x:
        return x
    else:
        return root(par[x])

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

par = [i for i in range(n)]
q.append(0)
his.append(0)

while len(q) > 0:
    #print(q)
    room = q.popleft()
    #print(room+1)
    for room2 in turo[room]:
        if room2 not in his:
            his.append(room2)
            q.append(room2)
            par[room2] = room

#print(turo,par)
for i in range(1,n):
    if (root(i) != 0):
        print("No")
        exit()
 
print("Yes")
for i in range(1,n):
    print(par[i]+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
par = []
rank = []
def init(n):
    for i in range(n):
        par.append(i)
        rank.append(sys.maxsize)
    rank[0] = 0
 
def root(x):
    if par[x] == x:
        return x
    else:
        return root(par[x])
        
 
def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False
 
def unite(x,y):
    #print(par[x],par[y],rank[root(x)],rank[root(y)])
    if par[x]==par[y]:
        return
    if rank[x] != sys.maxsize and rank[x] == rank[y]:
        pass
    elif(rank[x] < rank[y]):
        par[y] = x
        rank[y] = rank[x] + 1
    else:
        par[x] = y
        rank[x] = rank[y] + 1
        #if rank[x]==rank[y]:
         #   rank[x] += 1
    #print(par,rank)
 
n,m = map(int,input().split())

turo = [[] for i in range(n)]
q = deque()
his = []

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

init(n)
q.append(0)
his.append(0)

while len(q) > 0:
    #print(q)
    room = q.popleft()
    #print(room+1)
    for room2 in turo[room]:
        if room2 not in his:
            his.append(room2)
            q.append(room2)
            unite(room,room2)

print(turo,par)
for i in range(1,n):
    if (root(i) != 0):
        print("No")
        exit()
 
print("Yes")
for i in range(1,n):
    print(par[i]+1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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


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

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

    return nodes, nodeStatus


def calculate(n, nodes, nodeStatus):
    nodeMarks = [-1 for i in range(n)]

    q = deque()

    q.append((0, -1))

    while len(q) > 0:
        currentNode, parentNode = q.popleft()

        if nodeStatus[currentNode] == True:
            continue

        nodeStatus[currentNode] = True
        nodeMarks[currentNode] = parentNode
        childNodes = nodes[currentNode]

        for childNode in childNodes:
            if nodeStatus[childNode] == True:
                continue
            q.append((childNode, currentNode))

    minusNumber = nodeMarks.count(-1)
    if minusNumber > 1:
        print("No")
        return

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


nodes, nodeStatus = prepare(N, M, ARR)

calculate(N, nodes, nodeStatus)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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


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

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

    return nodes, nodeStatus


def calculate(n, nodes, nodeStatus):
    nodeMarks = [-1 for i in range(n)]

    q = deque()

    q.append((0, -1))

    while len(q) > 0:
        currentNode, parentNode = q.popleft()

        if nodeStatus[currentNode] == True:
            continue

        nodeStatus[currentNode] = True
        nodeMarks[currentNode] = parentNode
        childNodes = nodes[currentNode]

        for childNode in childNodes:
            q.append((childNode, currentNode))

    minusNumber = nodeMarks.count(-1)
    if minusNumber > 1:
        print("No")
        return

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


nodes, nodeStatus = prepare(N, M, ARR)

calculate(N, nodes, nodeStatus)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
neighbors = {key:[] for key in range(1, n+1)}
answers = {key:0 for key in range(1, n+1)}
answers[1] = 1
for i in range(m):
    a,b = map(int, input().split())
    neighbors[a].append(b)
    neighbors[b].append(a)
hosts = neighbors[1]
now = 1
def register(hs, n):
    for h in hs:
        if answers[h] == 0:
            answers[h] = n
            register(neighbors[h], h)
register(hosts, now)
flag = 0
for key, item in answers.items():
    if item == 0:
        flag = 1
if flag == 0:
    print("Yes")
    for key, item in answers.items():
        if key != 1:
            print(item)
else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import deque
n,m=map(int,input().split())
adj=[[] for _ in range(n)]
for _ in range(m):
  a,b =map(int,input().split())
  a-=1
  b-=1
  adj[a].append(b)
  adj[b].append(a)
ans=[0]*n
que=deque([])
que.append(0)
while que:
  e=que.popleft
  for i in adj[e]:
    if ans[i]!=0:
      continue
    ans[i]=e+1
    que.append(i)
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n,M = list(map(int,input().split()))
m = [[0]*n for _ in range(M)]
dp = [0]*n

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

from collections import deque
que = deque()
for i in range(n):
  if m[0][i] == 1:
    que.append(i)
    dp[i] = 1

while que:
  c = que.popleft()
  for i in range(n):
    cn = dp[c]
    if m[c][i] == 1 and dp[i] == 0 :
      dp[i] = c+1
      que.append(i)
      if cn == 1 and i == 0:dp[0] = 0

for i in range(1,n):
  if dp[i] == 0:exit(print('No'))


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

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(graph, visited, ss, g):
  queue = deque([ss])
  visited[ss] = 0
  while queue:
    s = queue.popleft()
    #　返り値に関する条件
    if visited[g] != -1 :
        return visited
    for new_s in graph[s] :
      if graph[new_s][s] == 1 and visited[new_s] == -1:
        #　移動回数の計算
        visited[new_s] = visited[s] + 1
        queue.append(new_s)
  return visited

n,m = map(int,input().split())
graph = [[] for j 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)
 
d = [0]*n
for g in range(1,n) :
    visited = [-1]*n
    d[g] = bfs(graph, visited, 0, g)[g]

Submission status: Runtime Error

Solution code:
n, m = [int(w) for w in input().split()]
links = [[] for i in range(n + 1)]
ldist = [10 ** 7] * (n + 1)
mark = [10 ** 7] * (n + 1)


def marking(node, dist, parent):
    if dist < ldist[node]:
        ldist[node] = dist
        mark[node] = parent
        for l in links[node]:
            marking(l, dist + 1, node)


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

marking(1, 0, 0)

if 10 ** 7 in mark[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join([str(w) for w in mark[2:]]))

Submission status: Runtime Error

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

for _ in range(m):
    a,b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)
d = deque([1])
s = set([1])

while d:
    x = d.popleft()
    for k in l[x]:
        if k not in s:
            s.add(k)
            d.appendleft(k)
            vi[k] = x
print('Yes')
for i in vi[2:]:
    print(i)

Submission status: Runtime Error

Solution code:

Copy
Copy
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: Runtime Error

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(M):
        (A,B) = map(int, input().split())
        na = neighbor.get(A, [])
        nb = neighbor.get(B, [])
        neighbor.update({A:na+B})
        neighbor.update({B:nb+A})

    guide = {1:1}

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

    if set(range(1,N+1)) <= set(guide.keys()):
        print('Yes')
        for i in range(2,N+1):
            print(guide[i])
    else:
        print('No')

main()

Submission status: Runtime Error

Solution code:
from collections import deque
q=deque()
def MI(): return map(int, input().split())
N,M=MI()
g=[[] for _ in range(M+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: Runtime Error

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

    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: Runtime Error

Solution code:
N = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N[1])]

# N = [6, 9]
# A = [[3, 4], [6, 1], [2, 4], [5, 3], [4, 6], [1, 5], [6, 2], [4, 5], [5, 6]]

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

for s in A:
    if s[1]==1:
        direction[s[0]-2] = s[1]
        counter += 1
    if s[0]==1:
        direction[s[1]-2] = s[0]
        counter += 1

k = 0
while counter <= N[0]-2:
    if direction[A[k][1]-2] != 0 and direction[A[k][0]-2] == 0:
        direction[A[k][0]-2] = A[k][1]
        counter += 1
    if direction[A[k][0]-2] != 0 and direction[A[k][1]-2] == 0:
        direction[A[k][1]-2] = A[k][0]
        counter += 1
    k += 1
    k %= N[0]