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:
#d
m,n=map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
maze = []
inf = 9999999
dist = [inf]* n
dist[0] = 0
queue = []
answer = [0]*n

goto = [[] * 1 for i in range(n)]
for i in range(len(ab)):
    goto[ab[i][0]-1].append(ab[i][1]-1)
    goto[ab[i][1]-1].append(ab[i][0]-1)

queue.extend([0])

while queue != []:
    go = queue.pop()
    for h in goto[go]:
        if dist[h] == inf:
            queue.append(h)
            dist[h] = dist[go]+1
            answer[h] =go+1
print("Yes")
for i in answer[1:]:
    print(i)

Submission status: Runtime Error

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

ans = [None]*(n-1)
check = [i for i in range(2,n+1)]
tmp = []
for j in graph[1]:
    ans[j-2] = 1
    check.remove(j)
    tmp.append(j)

while check != []:
    new_tmp = []
    for i in tmp:
        for j in graph[i]:
            if ans[j-2] == None and j != 1:
                ans[j-2] = i
                check.remove(j)
                new_tmp.append(j)
    tmp = new_tmp
if None in ans:
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
road = [tuple(map(int, input().split())) for _ in range(m)]

table = [list() for _ in range(n+1)]
ans = [0 for _ in range(n+1)]
hush = {}

for i in range(1, n+1):
    hush[i] = False

for a, b in road:
    table[a].append(b)
    table[b].append(a)

def bfs(i):
    hush[i] = True
    rec = []
    for j in table[i]:
        if hush[j] == False:
            ans[j] = i
            hush[j] = True
            rec.append(j)
    for j in rec:
        bfs(j)

bfs(1)

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

Submission status: Runtime Error

Solution code:
#d
m,n=map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
maze = []
inf = 9999999
dist = [inf]* n
dist[0] = 0
queue = []
answer = [0]*n

goto = [[] * 1 for i in range(n)]
for i in range(len(ab)):
    goto[ab[i][0]-1].append(ab[i][1]-1)
    goto[ab[i][1]-1].append(ab[i][0]-1)

queue.extend([0])

while queue != []:
    go = queue.pop()
    for h in goto[go]:
        if dist[h] == inf:
            queue.append(h)
            dist[h] = dist[go]+1
            answer[h] =go+1
print("yes")
for i in answer[1:]:
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import itertools

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

n, m = map(int,input().split())
p = [list(map(int,input().split())) for i in range(m)]

for v in itertools.combinations(p, n-1): #n-1本の道で、全ての場所から辿り着けるか
    l = [[0]*n for i in range(n)]
    #重み1の隣接行列
    for pi in v:
        l[pi[0]-1][pi[1]-1] = 1
        l[pi[1]-1][pi[0]-1] = 1
    l = np.array(l)
    
    #経路取得
    x = []
    for i in range(1,n):
        x.append(get_path(0, i, p))

    if x.count([]) == 0:
        print("Yes")
        ans = d[0][1:]
        for i in ans:
            print(int(i))
        exit()

print("No")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [0]
b = [0]
for i in range(1, m+1):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)
dir = [[] for _ in range(m+1)]
for i in range(1, m+1):
    dir[a[i]].append(b[i])
    dir[b[i]].append(a[i])
ans = [0 for i in range(n+1)]
flag = [0 for i in range(n+1)]
flag[1] = 1
que = [1]
while len(que) != 0:
    print('que: ', len(que), que)
    now = que.pop()
    flag[now] = 1
    for to in dir[now]:
        if flag[to] != 1 and not (to in que):
            que.append(to)
            flag[to] != 1
            ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)


def min_one(visit, rinsetu, idx1, dist):
    if 0 in rinsetu[idx1]:
        return idx1, dist
    min_t = (-1, 1001001001)
    for idx2 in rinsetu[idx1]:
        if visit[idx2]:
            continue
        if 0 in rinsetu[idx2]:
            return idx2, dist+1
        visit[idx2] = True
        m, d = min_one(visit, rinsetu, idx2, dist+1)
        visit[idx2] = False
        if m > 0:
            if min_t[1] > m:
                min_t = (d, m)
    if min_t[0] == 1001001001:
        return 0, 0
    else:
        return min_t

if __name__ == '__main__':
    N, M = mulinputs()
    datas = []
    for _ in range(M):
        A, B = mulinputs()
        datas.append((A,B))
    rin = []
    for _ in range(N):
        rin.append(set())
    for data in datas:
        rin[data[0]-1].add(data[1]-1)
        rin[data[1]-1].add(data[0]-1)
    ans = [(-1,-1)] * N
    for idx in range(1,N):
        visit = [False] * N
        visit[idx] = True
        m, d = min_one(visit, rin, idx, 1)
        visit[idx] = False
        if m == 0:
            print('No')
            exit()
        if ans[idx][0] < 0:
            ans[idx] = (d, m)
        else:
            t = ans[idx]
            if t > m:
                ans[idx] = (d, m)

    print('Yes')
    for t in ans[1:]:
        print(t[0])

Submission status: Runtime Error

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


def dfs(i, d, frag):
    for j in d[i]:
        if j not in frag:
            frag[j] = i
            dfs(j, d, frag)

frag = defaultdict()
dfs(1, graph, frag)
if len(frag.keys()) < n - 1:
    print('No')
else:
    print('Yes')
    for i in range(2, n + 1):
        print(frag[i])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
num=[]
ans=[]
c=0

for _ in range(n):
  num.append([])
  ans.append([])

  
for _ in range(m):
  a,b=map(int,input().split())
  num[a-1].append(b)
  num[b-1].append(a)
  
for i in range(1,n):
  
  if 1 in num[i]:
    ans[i].append(1)
    continue
    
  for j in num[0]:
    if j in num[i]:
      ans[i].append(j)
      continue
      
print("Yes")
del ans[0]
for i in ans:
  print(i[0])

Submission status: Runtime Error

Solution code:
from sys import *
ip = stdin.readline
N,M = map(int,ip().split())
arr = [[] for i in range(N+1)]
ret = [0]*(N+1)
for i in range(M):
    a,b = map(int,ip().split())
    arr[a].append(b)
    arr[b].append(a)

def dfs(nd,vi):
    if nd == 1:
        if len(vi):
            print(vi[1])
    v[nd] = 1
    for i in sorted(arr[nd]):
        if not v[i]:
            dfs(i,vi+[i])
print("YES")
for i in range(2,N+1):
    v = [0]*(N+1)
    dfs(i,[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import itertools
import math

def dfs(vum,s,visit,depth):
    # print('first')
    # print(s,depth,visit)
    if visit[s-1] >= 0:
        return visit
    visit[s-1] = depth
    # print(vum[s])
    for u in vum[s]:
        # print('now', str(u))
        if visit[u-1] >= 0:
            # print('skip', str(u))
            if visit[u-1] > depth:
                visit[u-1] = depth
                # print('update', str(u))
            continue
        s = u
        depth += 1
        visit = dfs(vum,s,visit,depth)
    return visit


def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    s = 1 # 現在地 (初期値はゴールを設定)
    visit = [-1]*N # 訪問リスト
    depth = 0 # 移動数(深さ)
    visit = dfs(vum,s,visit,depth)
    if -1 in visit:
        print('No')
        return
    else:
        print('Yes')
    for v in visit[1:]:
        print(v)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split( ))
AB = [list(map(int,input().split( ))) for _ in range(M)]
all_ = set([i for i in range(1,N)])
child = [[] for _ in range(N)]
ans = [[] for _ in range(N)]
for ab in AB:
    child[ab[0]-1].append(ab[1]-1)
    child[ab[1]-1].append(ab[0]-1)
child = list(map(set,child))
check = [0]
while len(all_ ) != 0:
    checkk = {}
    for c in check:
        a = child[c] & all_
        ans[c] = list(a)
        checkk = check | set(a)
        all_ = all_ - child[c]
    check = checkk
anss = [[] for i in range(N)]
for i in range(N):
    for a in ans[i]:
        anss[a] = i
print('Yes')
for a in anss[1:]:
    print(a + 1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [0]
b = [0]
for i in range(1, m+1):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)
dir = [[] for _ in range(m+1)]
for i in range(1, m+1):
    dir[a[i]].append(b[i])
    dir[b[i]].append(a[i])
ans = [0 for i in range(n+1)]
flag = [0 for i in range(n+1)]
flag[1] = 1
que = [1]
while len(que) != 0:
    print('que: ', len(que), que)
    now = que.pop(-1)
    flag[now] = 1
    for to in dir[now]:
        if flag[to] != 1 and not (to in que):
            que.append(to)
            flag[to] != 1
            ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
def solve(a, b, ab_list):

    route = {}

    for a, b in ab_list:
        if a not in route:
            route[a] = []
        if b not in route:
            route[b] = []

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

    route_memo = {}
    def func(x, memo):
        if x in route_memo:
            memo = route_memo[x]
            return True

        if  1 in route[x]:
            route_memo[x] = memo
            return True
        else:
            tmp = False
            for y in route[x]:
                if y not in memo:
                    memo.append(y)
                    tmp = func(y, memo)
                if tmp:
                    return True
            return False
    ans = []
    flg = True
    for i in range(2, n+1):
        memo = []
        if func(i, memo):
            if len(memo) == 0:
                memo.append(1)
            ans.append(memo[-1])
        else:
            flg = False
            break

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

if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    ab_list = [[int(i) for i in input().split()] for j in range(m)]
    solve(n, m, ab_list)

Submission status: Runtime Error

Solution code:

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def resolve():
    N, M = map(int, input().split())
    G = np.zeros((N + 1, N + 1), dtype=np.int64)

    for _ in range(M):
        x, y = map(int, input().split())
        G[x, y] += 1
        G[y, x] += 1
    csr = csr_matrix(G)
    dist, pred = dijkstra(csgraph=csr ,return_predecessors=True)

    ans = pred[1,2:]
    impos = any(ans >=0)
    if impos:
        print("Yes")
        print(*ans, sep="\n")
    else:
        print("No")

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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

ans = [deque([]) for _ in range(10)]
ans2 = [[] for _ in range(10)]
for i in range(m):
    s = li[i][0]
    t = li[i][1]

    ans[s].append(t)
    ans[t].append(s)
print(ans)

stack = deque([1])
while stack:
    v = stack[0]

    if ans[v]:
        w = ans[v].popleft()
        if ans2[w] == []:
            ans2[w].append(v)
        stack.append(w)
    else:
        stack.popleft()

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

Submission status: Runtime Error

Solution code:
import queue
N,M = map(int,input().split())
tree = [[] for _ in range(M+1)]
for i in range(M):
    a,b = map(int,input().split())
    tree[a].append([b,-1])
    tree[b].append([a,-1])

que = queue.Queue()
que.put(1)
result = [-1]*(N+1)
for i in range(len(tree[1])):
    tree[1][i][1] = 1
while(True):
    if que.empty():
        break
    nex = que.get()
    
    for i in tree[nex]:
        if result[i[0]] == -1:
            result[i[0]] = nex
            que.put(i[0])


result = result[2:]
if result.count(-1) != 0:
    print("No")
else :
    print("Yes")
    for i in result:
        print(i)

Submission status: Runtime Error

Solution code:
import copy
n, m = map( int, input().split() )
connect = []

for _ in range( n+1 ):
    connect.append( [ 0 ] * ( n+1 ) )

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

guide = [ 0 ] * ( n+1 )
path = [ 0, 0 ] + [ m+1 ] * ( n-1 )
unvisited = [ a for a in range( 1, n+1 ) ]

def solve( a, unvisited ): # aに隣接したやつのguideをaにする．またそれのpathをpath[a]+1にする．
    for b in unvisited:
        if connect[a][b] == 1 and path[a] + 1 < path[b]:
            path[b] = path[a] + 1
            guide[b] = a
    for b in unvisited:
        if connect[a][b] == 1:
            next_unvisited = copy.deepcopy( unvisited )
            next_unvisited.remove( a )
            solve( b, list( next_unvisited)  )

solve( 1, list( unvisited ) )

if 0 not in guide[2:]:
    print( "Yes" )
    for i in range( 2, n+1 ):
        print( guide[i] )
else:
    print( "No" )

Submission status: Runtime Error

Solution code:
def check(room_checked):
    for i in room_checked:
        if not i:
            return True
    return False


raw_input = list(map(int, input().strip().split()))
n = raw_input[0]
m = raw_input[1]
lines = [[0 for _ in range(m)] for __ in range(m)]
for i in range(m):
    line = list(map(int, input().strip().split()))
    a = line[0] - 1
    b = line[1] - 1
    lines[a][b] = 1
    lines[b][a] = 1
is_checked_all_room = [False for _ in range(n)]
sign = [0 for _ in range(n)]
queue = [0]
while check(is_checked_all_room):
    target = queue[0]
    is_checked_all_room[target] = True
    queue.pop(0)
    line = lines[target]
    for i, l in enumerate(line):
        if l:
            if not is_checked_all_room[i]:
                is_checked_all_room[i] = True
                sign[i] = target
                queue.append(i)
    if not queue:
        print('No')
else:
    print('Yes')
    for i in range(1, n):
        print(sign[i] + 1)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
tr = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    tr[a-1].append(b)
    tr[b-1].append(a)
if not tr[0]:
    print('No')
else:
    mark = [10**7]*n
    mark[0] = -1
    cnt = 0
    i=0
    def mk(mark,i,cnt):
        for j in range(len(tr[i])):
            if tr[i][j]!=1:
                mark[tr[i][j]-1] = min(i+1,mark[tr[i][j]-1])
                cnt+=1
                if cnt == n-1:
                    return mark
            else:
                continue
        else:
            for j in range(len(tr[i])):
                mark = mk(mark,tr[i][j]-1,cnt)
            else:
                return mark
    mark=mk(mark,0,cnt)
    if 10**7 in mark:
        print('No')
    else:
        print('Yes')
        for i in range(1,n):
            print(mark[i])

Submission status: Runtime Error

Solution code:
line1 = input().split()
n = int(line1[0])
m = int(line1[1])

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

for i in range(m):
  line = input().split()
  a = int(line[0]) - 1
  b = int(line[1]) - 1
  road_map[a].append(b)
  road_map[b].append(a)
  
current_goal = [0]
route = [-1] * n
none = True
while none:
  goal = current_goal
  current_goal = []
  for i in range(n):
    none = False
    road = road_map[i]
    if route[i] >= 0:
      continue
    dist = -1
    for r in road:x
      if r in goal:
        dist = r
    if dist >= 0:
      current_goal.append(i)
      route[i] = dist
      none = True
if min(route) == -1:
  print("No")
else:
  print("Yes")
  for r in route[1:n]:
    print(r + 1)

Submission status: Runtime Error

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

a = [ 0 ] * m
b = [ 0 ] * m

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


def search( x ):
    for i, ai in enumerate( a ):
        y = b[ i ]
        if ai == x and l[ y-1 ] > l[ x-1 ]:
            l[ y-1 ] = l[ x-1 ] + 1
            s[ y-1 ] = x
            search( y )
    for i, bi in enumerate( b ):
        y = a[ i ]
        if bi == x and l[ y-1 ] > l[ x-1 ]:
            l[ y-1 ] = l[ x-1 ] + 1
            s[ y-1 ] = x
            search( y )



l = [ 10000000000 ] * n
l[ 0 ] = 0
s = [ 0 ] * n
search( 1 )

print( "Yes" )
for i in range( n-1 ):
#    print( l[ i ], s[ i ] )
    print( s[ i+1 ] )

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
root_list = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    if tmp[0] != tmp[1] and tmp not in root_list:
        root_list.append(list(map(int, input().split())))

answer_list = [0] * (n-1)
done_list = [1]
already_list = [1]
while len(root_list) > 0 and 0 in answer_list:
    if len(done_list) == 0:
        break
    tmp_list = []
    copy_root_list = root_list.copy()
    for num in done_list:
        for l in root_list:
            if l[1] == num:
                if answer_list[int(l[0]-2)] == 0:
                    answer_list[int(l[0]-2)] = num
                    tmp_list.append(l[0])
                    already_list.append(l[0])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
            elif  l[0] == num and l[0] != l[1]:
                if answer_list[int(l[1]-2)] == 0:
                    answer_list[int(l[1]-2)] = num
                    tmp_list.append(l[1])
                    already_list.append(l[1])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
    root_list = copy_root_list
    done_list = tmp_list

if 0 not in answer_list:
    print("Yes")
    for i in answer_list:
        print(int(i))
else:
    print("No")

Submission status: Runtime Error

Solution code:
import math


def to_minutes(hour: int, minute: int) -> int:
    return 60 * hour + minute


def to_degree(total_minutes: int, unit_of_rotation: int) -> float:
    number_of_rotation = total_minutes / unit_of_rotation

    fractional_part = math.modf(number_of_rotation)[0]

    return 360 * fractional_part


def actual(a, b, hour, minute):
    """作戦: それぞれの回転数 → それぞれの角度 → 狭角の角度 → 余弦定理"""
    total_minutes = to_minutes(hour, minute)

    unit_of_rotation_hours = 720
    degree_of_hours = to_degree(total_minutes, unit_of_rotation_hours)

    unit_of_rotation_minute = 60
    degree_of_minutes = to_degree(total_minutes, unit_of_rotation_minute)

    degree_of_C = abs(degree_of_hours - degree_of_minutes)
    C_radian = math.radians(degree_of_C)

    cosC = math.cos(C_radian)

    return math.sqrt(a ** 2 + b ** 2 - 2 * a * b * cosC)
  
a, b, h, m = map(int, input().split())

print(actual(a, b, h, m))

Submission status: Runtime Error

Solution code:
import sys
import networkx as nx
n,m=map(int,input().split())
g = nx.Graph()
l = sys.stdin.readlines()
for x in l:
    if 4 <= len(x) :
        g.add_edge(int(x[0]), int(x[2]))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
tr = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    tr[a-1].append(b)
    tr[b-1].append(a)
if not tr[0]:
    print('No')
    exit()
else:
    mark = [10**7]*n
    mark[0] = -1
    cnt = 0
    i=0
    def mk(mark,i,cnt):
        for j in range(len(tr[i])):
            if tr[i][j]!=1:
                mark[tr[i][j]-1] = min(i+1,mark[tr[i][j]-1])
                cnt+=1
                if cnt == n-1:
                    return mark
            else:
                continue
        else:
            for j in range(len(tr[i])):
                mark = mk(mark,tr[i][j]-1,cnt)
            else:
                return mark
    mark=mk(mark,0,cnt)
    if 10**7 in mark:
        print('No')
    else:
        print('Yes')
        for i in range(1,n):
            print(mark[i])

Submission status: Runtime Error

Solution code:
from collections import deque

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

g = [[] for _ in range(N+1)] # 隣接リスト

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

#road_list=[]
#for i in range(M):
#  road_list.append(list(map(int,input().split())))

queue = deque([1])
d = [None] * (N+1) # uからの距離の初期化
d[1] = 0 # 自分との距離は0
while queue:
  v = queue.popleft()
  for i in g[v]:
    if d[i] is None:
      d[i] = v
      queue.append(i)

#print(d)


#ans_dict=dict([])
#before_room=[1]
#while True:
#  temp_room=[]
#  for j in range(len(before_room)):
#    for i in road_list:
#      if i[0]==before_room[j]:
#        if i[1] not in ans_dict:
#          ans_dict[i[1]]=before_room[j]
#          temp_room.append(i[1])
#      if i[1]==before_room[j]:
#        if i[0] not in ans_dict:
#          ans_dict[i[0]]=before_room[j]
#          temp_room.append(i[0])
#  before_room=temp_room
#  if len(ans_dict)==N:
#    break
    
d[0]=0
if None in d:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(d[i])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
rank = [1] * n
root = [[] for i in range(m)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])  # 経路圧縮
        return par[x]

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if rank[x] < rank[y]:
        rank[y] += rank[x]
        par[x] = y
    else:
        rank[x] += rank[y]
        par[y] = x


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

flg = True
for i in range(1, n - 1):
    if not same(0,i):
        flg = False

if not flg:
    print("No")
    exit()
else:
    print("Yes")
    for i in range(1, n):
        print(min(root[i])+1)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
root_list = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    if tmp[0] != tmp[1] and tmp not in root_list:
    root_list.append(list(map(int, input().split())))

answer_list = [0] * (n-1)
done_list = [1]
already_list = [1]
while len(root_list) > 0 and 0 in answer_list:
    if len(done_list) == 0:
        break
    tmp_list = []
    copy_root_list = root_list.copy()
    for num in done_list:
        for l in root_list:
            if l[1] == num:
                if answer_list[int(l[0]-2)] == 0:
                    answer_list[int(l[0]-2)] = num
                    tmp_list.append(l[0])
                    already_list.append(l[0])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
            elif  l[0] == num and l[0] != l[1]:
                if answer_list[int(l[1]-2)] == 0:
                    answer_list[int(l[1]-2)] = num
                    tmp_list.append(l[1])
                    already_list.append(l[1])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
    root_list = copy_root_list
    done_list = tmp_list

if 0 not in answer_list:
    print("Yes")
    for i in answer_list:
        print(int(i))
else:
    print("No")

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N,M = map(int,input().split())
graph = np.zeros((N,N),dtype=int)
for _ in range(M):
    A,B = map(int,input().split())
    A,B = A-1,B-1
    graph[A,B] = 1
    graph[B,A] = 1
print("Yes")
"""
for i in range(1,N):
    d,p = shortest_path(graph,directed=False,return_predecessors=True)
    print(p[0][i]+1)
"""