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:
import numpy as np
N, M = map(int, input().split())
K = [list(map(int, input().split()))]
if M > 1:
    for i in range(M - 1):
        K.append(list(map(int, input().split())))

S = [0] * N
A = np.eye(N)
for i in range(M):
    A[K[i][0]-1,K[i][1]-1] = 1
    A[K[i][1]-1,K[i][0]-1] = 1

x = [0]
while len(x) != 0:
    y = []
    for i in range(len[x]):
        for j in range(x[i],N):
            if A[x[i], j] == 1 and S[j] != 0:
                S[j] = 1
                y.append(j)
    x = y

flag = 0
for i in range(1, len(S)):
    if S[i] == 0:
        flag = 1
        print("No")
        break
if flag == 0:
    print("Yes")
    for i in range(1, len(S)):
        print(S[i]-1)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
que=deque([])
que.append(1)
count=0
while que:
  if count==N:
    exit()
  p=que.popleft
  for i in range(M):
    if ab[i][0]==p:
      if ab[i][1] not in que:
      	que.append(ab[i][1])
        count+=1
      
    if ab[i][1]==p:
      if ab[i][0] not in que:
      	que.append(ab[i][0])
      	count+=1
print("Yes")
print(*l)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
A = np.full((N, N), np.inf)
B = []*N
S = []*N

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

for i in range(N):
  for j in range(N):
    if i == j:
      A[i][j] = 0


for i in range(1, N):
  for j in range(i):
    for k in range(i, N):
    if A[j][k] < A[i][j] + A[i][k]:
      A[j][k] = A[i][j] + A[i][k]
      A[k][j] = A[i][j] + A[i][k]
      if j == 0:
        S[k] = i

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
c=[0]*(n+1)
l=[1]
count=n
while count>0:
    for _ in range(m):
        a,b=map(int,input().split())
        if l.count(a)!=0 and l.count(b)==0:
            l.append(b)
            c[b]==a
            count-=1
        elif l.count(b)!=0 and l.count(a)==0:
            l.append(a)
            c[a]==b
            count-=1
print('Yes')
for i in range(1,n+1):
    print(c[i])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
P = [list(map(int, input().split())) for i in range(M)]
nxt = [1]
res = [0] * (M - 1)
cnt = 1

while cnt < M:
    nxt_t = []
    dlist = []
    for item in nxt:
        for p in range(len(P)):
            if item in P[p]:
                if P[p][1 - P[p].index(item)] not in nxt:
                    nxt_t.append(P[p][1 - P[p].index(item)])
                    res[P[p][1 - P[p].index(item)] - 2] = item
                    cnt += 1
                if p not in dlist:
                    dlist.append(p)
    dlist.sort(reverse=True)
    nxt = nxt_t
    for d in dlist:
        del(P[d])

print("Yes")
for item in res:
    print(item)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
L=[set() for i in range(n)]
for i in range(m):
    a, b =  map(int, input().split())
    L[a-1] |= {b}
    L[b-1] |= {a}
Y = {range(1, n+1)}
Z = [0]*(n-1) 
S = {1}
def f(X):
    global S, Z
    D = set()
    for j in X:
        R = L[j-1]-S
        S |= L[j-1]
        D |= R
        for k in R:
          Z[k-2]=j
    if S == Y:
        print("Yes")
        print(Z[i] for i in range(n-1))
    else:
      f(D)
f({1})

Submission status: Runtime Error

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

def recursive(num, array):
    array = array[:]
    for i in range(m):
        if num == paths[i][0]:
            if array[paths[i][1]-2] == 0:
                array[paths[i][1]-2] = num
                array = recursive(paths[i][1], array)
        if num == paths[i][1]:
            if array[paths[i][0]-2] == 0:
                array[paths[i][0]-2] = num
                array = recursive(paths[i][0], array)
    return array

def main():
    array = [0]*(n-1)
    array = recursive(1,array)
    if 0 in array:
        print('No')
        return
    print('Yes')
    print(array)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class RoomClass:
    mitisirube = 0
    linknode = []
    linkline = []

    def __init__(self):
        self.mitisirube = 0
        self.linknode = []
        self.linkline = []


heyasu, turosu = map(int, input().split())

heyabango = [0] * heyasu

for i in range(heyasu):
    heyabango[i] = RoomClass()

for i in range(turosu):
    h1, h2 = map(int, input().split())
    heyabango[h1].linknode = h2
    heyabango[h2].linknode = h1
    # heyabango[h1].linkline

movecount = []
mc = 0

for i in heyabango:
    if i == 0:
        continue

    current = 0
    mc = 0

    if 1 in heyabango[i].linknode:
        mc += 1
        continue
    
    for l in len(heyabango[i].linknode):
        if current == 1:
            
            break
        else:
            mc +=1
        if 1 in heyabango[heyabango[i].linknode[l]].linknode:
            break
        
    movecount.append(mc)

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)

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

Submission status: Runtime Error

Solution code:
N,M=(int(x) for x in input().split())
map=[]
ikisaki=[]
ans=[0]*(N+1)
for n in range(M):
    A=list(int(x) for x in input().split())
    map.append(A)

for n in range(M):
    if map[n][0]==1:
        ikisaki.append(map[n][1])
        ans[map[n][1]]=1
    if map[n][1]==1:
        ikisaki.append(map[n][0])
        ans[map[n][0]]=1
ans[1]=1
while ikisaki:

    u=ikisaki.pop(0)
    for n in range(M):
        if (map[n][0]==u and ans[map[n][1]]==0):
            ikisaki.append(map[n][1])
            map.pop(n)
            ans[map[n][1]]=map[n][0]
        if (map[n][1]==u and ans[map[n][0]]==0):
            ikisaki.append(map[n][0])
            map.pop(n)
            ans[map[n][0]]=map[n][1]
c=0
for n in range(N-1):
    if ans[n+2]==0:
        c=1
if c==1:
    print('No')
else:
    print('Yes')
    for n in range(N-1):
        print(ans[n+2])

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
a = []
res = [0 for i in range(n-1)]
f = False

for i in range(m):
    a1,b1 = list(map(int,input().split()))
    a.append([a1,b1])
    if a1 == 1 or b1 == 1:
        f = True

temp = [1]
temp2 = [1]

if n == 2:
    n1 = 1
else:
    n1 = n

if f:
    for l in range(n):
        temp = temp2.copy()
        temp2 = []
        for j in temp:
            for p in [0,1]:
                for q in range(n1):
                    if a[q][p] == j:
                        if p == 0:
                            temp2.append(a[q][1])
                        else:
                            temp2.append(a[q][0])
            for k in temp2:
                if res[k-2] == 0:
                    res[k-2] = j
        if res.count(0) == 0:
            break
    if res.count(0) == 0:    
        print("Yes")
        for i in res:
            print(i)
    else:
        print("No")
else:
    print("No")

Submission status: Runtime Error

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n,m = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
for i in range(m):
    x,y = map(int,input().split())
    cost[x][y] = 1
    cost[y][x] = 1
d = dijkstra(0,n,m,cost)
if all(i < n for i in d):
  print("No")
else:
  print('Yes')
for x in d[1:]:
    print(x)

Submission status: Runtime Error

Solution code:
from collections import deque
inf = 10 ** 7
N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]
a = [[] for i in range(N)]
for i in P:
    a[i[0]-1].append(i[1]-1)
    a[i[1]-1].append(i[0]-1)
path = [-1] * N
path[0] = 0
checked = [False] * N
stack = deque([(0,0)])
while (len(stack) != 0):
    kk = stack.pop(0)
    now = kk[0]
    pre = kk[1]
    if  not checked[now]:    
        nextP = a[now]
        checked[now] = True
        path[now] = pre
        for i in nextP:
            stack.append((i,now))
if False in checked:
    print("No")
else:
    print("Yes")
    for i in path[1:]:
        print(i + 1)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
K = [list(map(int, input().split()))]
if M > 1:
    for i in range(M - 1):
        K.append(list(map(int, input().split())))

S = [0] * N
A = np.eye(N)
for i in range(M):
    A[K[i][0]-1,K[i][1]-1] = 1
    A[K[i][1]-1,K[i][0]-1] = 1

x = [0]
while len(x) != 0:
    y = []
    for i in range(len[x]):
        for j in range(x[i],N):
            if A[x[i], j] == 1 and S[j] != 0:
                S[j] = 1
                y.append(j)
    x = y

flag = 0
for i in range(1, len(S)):
    if S[i] == 0:
        flag = 1
        print("No")
        break
if flag == 0:
    print("Yes")
    for i in range(1, len(S)):
        print(S[i])

Submission status: Runtime Error

Solution code:
def func1(lst):
    return [i for i, x in enumerate(lst) if x == -1]

n,m = map(int, input().split(" "))
route = []
for i in range(m):
    route.append(list(map(int, input().split(" "))))
answer = [-1 for i in range(n + 1)]
answer[0], answer[1] = 0, 0
chokuzen = [1]
while(True):
    if not -1 in answer:
        print('Yes')
        for i in range(2, n + 1):
            print(answer[i])
        break
    temp = []
    tsuika = True
    for i in func1(answer):
        if route[i][0] in chokuzen:
            tsuika = False
            temp.append(route[i][1])
            answer[route[i][1]] = route[i][0]
        elif route[i][1] in chokuzen:
            tsuika = False
            temp.append(route[i][0])
            answer[route[i][0]] = route[i][1]
    if tsuika:
        print('No')
        break
    chokuzen = temp

Submission status: Runtime Error

Solution code:
from itertools import combinations

N, M = map(int, input().split(' '))
print("部屋Nは{0}個, 通路Mは{1}本".format(N, M))

roads = []
roads_in_rooms = {}

# 部屋ごとの通路配置を整理
print(roads_in_rooms)
for i in range(M):
  Ai, Bi = map(int,input().split(' '))
  if not(Ai in roads_in_rooms):
    roads_in_rooms[Ai] = []
  if not(Bi in roads_in_rooms):
    roads_in_rooms[Bi] = []
  roads_in_rooms[Ai].append(Bi)
  roads_in_rooms[Bi].append(Ai)  
  
print(roads_in_rooms)

# 任意の部屋でループさせ、そこから通じるルートの組み合わせを取って1につくことがあれば、
# その最小数のときのそれぞれのルートを記録して出力
for room in roads_in_rooms:
# out

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
    depth += 1
    # print(vum[s])
    for u in vum[s]:
        # print('now', str(s), str(u), str(depth))
        if visit[u-1] >= 0:
            # print('skip', str(u))
            if visit[u-1] > depth:
                visit[u-1] = depth
                # print('update', str(u))
            continue
        visit = dfs(vum,u,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())
d = {}
for i in range(m):
  a,b = map(int, input().split())
  if a in d:
    l = d[a]
    l.append(b)
    d[a] = l
  else:
    d[a] = [b]
  if b in d:
    l = d[b]
    l.append(a)
    d[b] = l
  else:
n,m = map(int, input().split())
d = {}
for i in range(m):
  a,b = map(int, input().split())
  if a in d:
    l = d[a]
    l.append(b)
    d[a] = l
  else:
    d[a] = [b]
  if b in d:
    l = d[b]
    l.append(a)
    d[b] = l
  else:
    d[b] = [a]
clear = [1]
ans_ = [1]
ans = [0]*(n-1)
while(0 in ans):
  for i in ans_:
    ans__ = []
    for j in d[i]:
      if j in clear:
        continue
      else:
        clear.append(j)
        ans__.append(j)
        ans[j-2] = i
  ans_ = ans__
  if len(ans_) == 0:
    break
if 0 in ans:
  print("No")
else:
  print("Yes")
  for i in ans:
    print(i)

Submission status: Runtime Error

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

result ={}


paths={}
for i in range(N):
    paths[i+1] = []

for i in range(M):
    A, B = map( int ,input("").split(" "))
    if( B!=1):
        paths[A].append(B)
    if( A!=1):
        paths[B].append(A)

def paths_shrink( paths, ids ):
    for i in paths.keys():
        paths[i].remove(ids)

    return paths


def search( fid, cnt, paths):
    idss = paths[fid]
    for ids in idss:
        if( ids in result.keys()):
            if( result[ids][0] <= cnt ):
                continue
        result[ids]=[cnt,fid]
        paths = paths_shrink(paths, ids)
        search( ids, cnt+1, paths )

search(1,1,paths)

err_flg = 0
for i in range(2,N+1):
    if( not (i in result.keys())):
        err_flg = 1
        break

if(err_flg == 1):
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(result[i][1])

Submission status: Runtime Error

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

Map = [[False]*N for i in range(N)]
# print(Map)
for i in range(M):
  A, B = map(int,input().split())
  Map[A-1][B-1] = True
  Map[B-1][A-1] = True

MAX = 1e+10
def func(place,times):
  if Map[place-1][0] == True:
      return times+1
  
  for i in range(N):
    Map[place-1][i] == True
    return func(i,times+1)


ans = [MAX]*N
for p in range(1,N+1):
  ans[p-1] = func(p,0)

if max(ans) == MAX:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(ans[i-1])

Submission status: Runtime Error

Solution code:
N,M= map(int, input().split())
A=[]
B=[]
N=1
NL=0
dn=0
ans=[]
ansx=[]
Lall=list()
moji="No"
for i in range(M):
    L=list(map(int, input().split()))
    Lall.append(L)




for j in range(M-1):
    dn=0
    for i in range(M):
        if N in Lall[i]:
            ansx.append(N)
            if Lall[i][0]==1:
                NL=1
            else:
                NL=0
        
            del Lall[i]
            dn+=1
            
        
        if i+1>=M-dn:
            break
        if len(Lall)==0:
            break
    if len(Lall)==0:
        moji="Yes"
        break
        
    ans.append(N)
    N=L[NL]
   
print(moji)
for i in range(M-1):
    print(ansx[i])

Submission status: Runtime Error

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

# from math import gcd
from fractions 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)]

goal = 1
rets = []
road = {i:[] for i in range(1, N+1)}

for A, B in AB:
    road[A] += [B]
    road[B] += [A]

ret, retind = [], []

def dfs(ind, inds, dis, inddict):

    global goal, ret, retind

    if inddict[ind]:
        return

    inds += [ind]
    dis += 1
    inddict[ind] = 1

    if ind == goal:
        ret += [dis]
        retind += [inds]
        return

    for i in road[ind]:
        dfs(i, copy.copy(inds), dis, dict.copy(inddict))

for start in range(2, N+1):
    ret, retind = [], []
    dfs(start, [], 0, {i:0 for i in range(1, N+1)})
    if ret:
        rets += [retind[ret.index(min(ret))][1]]
    else:
        rets += [None]

ch = list(set(rets))
if len(ch) == 1 and ch[0] == None:
    print("No")
else:
    print("Yes")
    for i in rets:
        print(i)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(n)]
b=[[0]* n for j in range(n)] 
bb=[]
for i in range(n-1):
    bb.append(i)
c=[]
d=[0]*n-1
for i in range(n):
    for j in range(n):
        b[a[i][0][a[i][1]] = a[i][1]
        b[a[i][1]][a[i][0]] = a[i][0]
while len(bb)!=0:
    for i in range(n):
        if b[i][j]=-1:
            c.append(b[i][j])
            bb.deque(b[i][j])
            d[b[i][j]]=i+1
            print(b[i][j]+1)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
A = np.full((N, N), np.inf)
B = []*N
S = []*N

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

for i in range(N):
  for j in range(N):
    if i == j:
      A[i][j] = 0


for i in range(1, N):
  for j in range(i):
    for k in range(i, N)
    if A[j][k] < A[i][j] + A[i][k]:
      A[j][k] = A[i][j] + A[i][k]
      A[k][j] = A[i][j] + A[i][k]
      if j == 0:
        S[k] = i

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

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,a])
    tree[b].append([a,b])

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 or result[i[1]] != -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:
from collections import deque
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
l=[0]*N
que=deque([])
que.append(1)
count=0
while que:
  if 0 not in l:
    exit()
  p=que.popleft
  for i in range(M):
    if ab[i][0]==p:
      if ab[i][1] not in que:
      	que.append(ab[i][1])
        count+=1
      
    if ab[i][1]==p:
      if ab[i][0] not in que:
      	que.append(ab[i][0])
      	count+=1
print("Yes")
print(*l)

Submission status: Runtime Error

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

connect_list = [set() for _ in range(N)]
ranking = [set() for _ in range(N)]
ranked_set = set()
full_set = {i for i in range(1, N+1)}


def do_ranking(set, rank):
    global connect_list, ranking, ranked_set, full_set
    if ranked_set == full_set:
        return 0
    for j in list(set):
        for i in list(connect_list[j-1]):
            if i not in ranked_set:
                ranking[rank].add(i)
                ranked_set.add(i)
    do_ranking(ranking[rank], rank+1)



for A, B in AB:
    connect_list[A-1].add(B)
    connect_list[B-1].add(A)
ranking[0] = connect_list[0]
ranked_set = ranked_set | ranking[0]
ranked_set.add(1)
do_ranking(ranking[0], 1)

root_list = [0]*N
root_list[0] = "Yes"
count = 0
no_flag = False
for i in range(1, N):
    flag = True
    j = 0
    while flag:
        if len(ranking[j]) == 0:
            no_flag = True
            break
        seki = connect_list[i] & ranking[j]
        if 1 in connect_list[i]:
            root_list[i] = 1
            flag = False
        elif len(seki) != 0:
            root_list[i] = list(seki)[0]
            flag = False
        else:
            j += 1
    if no_flag:
        print("No")
        break
if no_flag == False:
    for i in root_list:
        print(i)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop

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

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

INF = 10**18
ans = []


def dijkstra(N, G, s):
    dist = [INF] * n
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t in G[v]:
            if dist[v] + 1 < dist[t]:
                dist[t] = dist[v] + 1
                heappush(que, (dist[t], t))
    ans.append(dist[0])


for i in range(1, n):
    dijkstra(n, edges, i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    print(*ans, sep='\n')

Submission status: Runtime Error

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

def recursive(num, array):
    array = array[:]
    for i in range(m):
        if num == paths[i][0]:
            # print(paths[i][0])
            if array[paths[i][1]-2] == 0:
                array[paths[i][1]-2] = num
                array = recursive(paths[i][1], array)
        if num == paths[i][1]:
            if array[paths[i][0]-2] == 0:
                array[paths[i][0]-2] = num
                array = recursive(paths[i][0], array)
    return array

def main():
    array = [0]*(n-1)
    array = recursive(1,array)
    print(array)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def g(i):
    for j in graph[i]:
        next = []
        if 1 in graph[j]:
            return j
            break
            #print(j)
        else:
            next.append(j)
    if next != []:
        for k in next:
            g(k)

N,M = LI()
#print(N,M)
AB = list(LI() for _ in range(M))
#print(AB)

graph = {i:[] for i in range(1,N+1)}

for i in AB:
    a = i[0]
    b = i[1]
    graph[a] += [b]
    graph[b] += [a]

#print(graph)
print("Yes")
for i in range(2,N+1):
    #print(i)
    if 1 in graph[i]:
        print(1)
    else:
        print(g(i))

Submission status: Runtime Error

Solution code:
import heapq

max_v,m = input().split()
max_v = int(max_v)
m = int(m)

class Edge(object):
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


edges = [[] for j in range(max_v)]
for i in range(max_v):
  a, b = input().split()
  a = int(a)
  b = int(b)
  edges[a-1].append(Edge(b-1,1))
  edges[b-1].append(Edge(a-1,1))

d = [float("inf")]*max_v
fire = [-1]*max_v
#fire = [[[]for j in range(max_v)] for i in range(max_v)]
def dijkstra(s):
	h = []
	d[s] = 0
	heapq.heappush(h, [0,0])
	while(len(h) != 0):
		p = heapq.heappop(h)
		v = p[1]
		if d[v] < p[0]:continue
		for i in range(len(edges[v])):
			e = edges[v][i]
			if d[e.to] > d[v] + e.cost:
				d[e.to] = d[v] + e.cost
				heapq.heappush(h, [d[e.to], e.to])
				fire[e.to] = v
dijkstra(0)
if 2 <= fire.count(-1):
  print("No")
else:
  print("Yes")
  for i in range(1, max_v):
    print(fire[i]+1)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split(' ')]
connections = [[] for i in range(n)]
symbol = [-1 for i in range(n)]
generations = [-1 for i in range(n)]

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

def set_symbol(room_number, g):
  if not connections[room_number]:
    return
  for c in connections[room_number]:
    if generations[c] == -1 or generations[c] > g:
      symbol[c] = room_number
      generations[c] = g
      set_symbol(c, g+1)
  return

set_symbol(0, 0)
if -1 in symbol[1:]:
  print('No')
else:
  print('Yes')
  for i in symbol[1:]:
    print(i+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 ai, bi in zip( a, b ):
        if ai == x and l[ bi-1 ] > l[ ai-1 ]:
            l[ bi-1 ] = l[ ai-1 ] + 1
            s[ bi-1 ] = ai
            search( bi )
        elif bi == x and l[ ai-1 ] > l[ bi ]:
            l[ ai-1 ] = l[ bi-1 ] + 1
            s[ ai-1 ] = bi
            search( ai )



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:
# cook your dish here
def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path


from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

N,M = map(int,input().split())
edge = [[10**9 for j in range(N+1)] for i in range(N+1)]

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

G = csgraph_from_dense(edge, null_value=10**9)
d = dijkstra(G,indices = 1)
ck = 0
for i in range(2,len(d)):
  if d[i] == float('inf'):
    ck = 1
if ck == 1:
  print("No")
else:
  print("Yes")
  for i in range(2,len(d)):
    d = dijkstra_back(1,i,N,M,edge)
    print(d[-2])

Submission status: Runtime Error

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
l=[0]*N
que=deque([])
que.append(1)
count=0
while que:
  if 0 not in l:
    exit()
  p=que.popleft
  for i in range(M):
    if ab[i][0]==p:
      if ab[i][1] not in que:
      					que.append(ab[i][1])
          				count+=1
      
    if ab[i][1]==p:
      if ab[i][0] not in que:
      						que.append(ab[i][0])
      						count+=1
print("Yes")
print(*l)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = {}
r = 0
for i in range(n):
    if a[i][0] == 0 and a[i][1]:
        r += 1
    elif a[i][0] == 0:
        if 0 in d:
            d[0][0] = d[0][0] +1
        else:
            d[0] = [1, 0]
    elif a[i][1] == 1:
        if 0 in d:
            d[0][1] = d[0][1] +1
        else:
            d[0] = [0, 1]
    else:
        if a[i][0] * a[i][1] > 0:
            s = a[i][0] / a[i][1]
            if s in d:
                d[s][0] = d[s][0] +1
            else:
                d[s] = [1, 0]
        else:
            s = -a[i][1] / a[i][0]
            if s in d:
                d[s][1] = d[s][1] +1
            else:
                d[s] = [0, 1]
ans = 1
m = 0
for i in d:
    m += 1
    ans *= 2**d[i][0] + 2**d[i][1] - 1
    if m != 1:
        ans -= 1
    print(ans)
ans += r
ans = ans%1000000007
#print(d)
print(ans)

Submission status: Runtime Error

Solution code:
def search_min_path(current_point, num_count, ns, ps, pl):
    if ns[current_point] <= num_count + 1:
        return - 1
        
    for next_point in pl[current_point]:
        next_count = ns[next_point] + num_count + 1
        if next_count < ns[current_point]:
            ps[current_point] = next_point
            ns[current_point] = next_count
            #return

        search_min_path(next_point, num_count + 1, ns, ps, pl)


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

ns = [N+1] * N #num to start
ps = [-1] * N  #next path to start
pl = []  #path list

for i in range(N):
    pl.append([])

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

    if A == 0:
        ns[B] = 1
        ps[B] = 0
    elif B == 0:
        ns[A] = 1
        ps[A] = 0

for i in range(1,N):
    search_min_path(i, 0, ns, ps, pl)

ok_flag = True
for i in range(1, N):
    if ps[i] == -1:
        ok_flag = False
        break

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

else:
    print('No')