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: Wrong Answer

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LI() for _ in range(M)]
path = [[0] * (N+1) for _ in range(N+1)]
mp = []
ans = [0] * (N+1)

for ab in AB:
  a = ab[0]
  b = ab[1]
  path[a][b] = 3
  path[b][a] = 3

def print_map(tree):
  for v in tree[1:]:
    for w in v[1:]:
      print(w, end=' ')
    print()

def bfs(tree, st, end):
  queue = collections.deque()
  queue.append([0,-1,st])
  now = [-1,-1,-1]
  pre = []
  depth = 0
  histind = -1
  node = -1
  hist = []
  while queue:
    pre = now[:]
    now = queue.popleft()
    depth = now[0]
    histind = now[1]
    node = now[2]
    hist.append([depth,histind,node])
    if node == end:
      #print("endpoint reached. depth={0}".format(depth))
      res = [node]
      ident = histind
      while res[len(res)-1]!=1:
        res.append(hist[ident][2])
        ident = hist[ident][1]
      return [depth,res[::]]
    for ind,v in enumerate(path[node]):
      if v&1 == 1 and ind != pre:
        queue.append([depth+1,len(hist)-1,ind])
  return None

#print_map(path)
for i in range(2,N+1):
  tmp = bfs(path, 1, i)
  if tmp is None:
    print("No")
    exit(0)
  mp.append(tmp[::])
  #print(i, tmp)

mp.sort(key=lambda x:x[0], reverse=True)
mx = mp[0][0]
for s in mp:
  if s[0] < mx:
    break
  else:
    t = 0
    while s[1][t] != 1:
      ans[s[1][t]] = s[1][t+1]
      t+=1
print("yes")
for a in ans[2:]:
  print(a)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
path = []
for i in range(m):
    path.append(tuple(map(int, input().split())))

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

def f(room):
    v = []
    for i in path:
        to = 0
        if room == i[0]:
            to = i[1]
        elif room == i[1]:
            to = i[0]
        if to > 0 and mark[to] == -1:
            mark[to] = room
            v.append(to)
    for i in v:
        f(i)

f(1)
if mark.count(-1) > 0:
    print("No")
else:
    print("Yes")
    for i in mark[2:]:
        print(i)

Submission status: Wrong Answer

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

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

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

#print(mp2)

inf=float('inf')
d=[[inf for i in range(N)]for j in range(N)]
for i,j in mp2:
    d[i-1][j-1]=1
    d[j-1][i-1]=1
#print(d)

csr = csr_matrix(d)
ans=shortest_path(csr, indices=0)
if sum(ans)>0:
    print('Yes')
else:
    print('No')
for i in ans[1:]:
    print(int(i), sep='')

Submission status: Wrong Answer

Solution code:
import numpy as np
# スペース区切りの整数の入力
N, M = map(int, input().split())

Root = []
for _ in range(M):
    A_, B_ = map(int, input().split())
    Root.append([A_, B_])
    
root = np.array(Root).reshape(-1,2)


# 入り口からの距離と道知るベを測る
depth = np.array([-1] * N)
toward = depth

## 1 番の部屋は距離0
depth[0] = 0

# 終わったか
Finflag = False

# 距離が近い順に埋めていく
for i in range(N):
    # 距離iの部屋を表す複数のindex
    indices = np.where(depth==i)[0]
    
    rooms = []
    newdepth = i+1
    for index in indices:
        # index につながる部屋を抽出
        x, y = np.where(root == index+1)
        # 該当する場所にdepthと道しるべを置く
        room = root[x, 1 - y]
        
        # こう書きたかった：depth[room - 1] = newdepth
        for ro in room:
          # 埋まってなければ
          if depth[ro - 1]==-1: 
            depth[ro - 1] = newdepth
            toward[ro - 1] = index+1
        # 不要な部分を消す
        root = np.delete(root,obj=x,axis=0)
        
    # 処理が終われば終了
    if not np.any(depth == -1):
        Finflag = True
        break

# output
if Finflag:
    print("Yes")
    for tow in toward[1:]:
        print(tow)
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = list(map(int,input().split()))
linked_list ={i:[] for i in range(1,N+1)}
# A_list = []
# B_list = []
depths = [-1 for _ in range(N)]
# depths[0] = 0
for m in range(M):

    A, B = list(map(int,input().split()))
    linked_list[A].append(B)
    linked_list[B].append(A)

    # A_list.append(A)
    # B_list.append(B)
node = []
simbols =[]
q = deque()
q.append(1)
while len(q) >0:
    node_no  = q.pop()
    for i in linked_list[node_no]:
        if depths[i-1] != -1 :
            continue
        q.append(i)
        depths[i-1]=node_no

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

# for _ in range(N):
#     node.append(float("inf"))
#     simbols.append(0)
#
# for n in range(N):
#     _node = node.copy()
#     memo = []
#

# for k,link in linked_list.items():
#     if k == 1:
#         continue

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(adj, sign):
  queue = deque([0])
  sign[0] = 0
  while queue:
    x = queue.popleft()
    for y in adj[x]:
      if sign[y] == -1:
        sign[y] = x
        queue.append(y)

if __name__ == "__main__":
  n, m = map(int, input().split())
  adj = [set() for _ in range(n)]
  for _ in range(m):
    a, b = map(int, input().split())
    adj[a-1].add(b-1)
    adj[b-1].add(a-1)
  sign = [-1]*n
  bfs(adj, sign)
  if all([x != -1 for x in sign]):
    print("yes")
    for x in sign[1:]:
      print(x+1)
  else:
    print("no")

Submission status: Wrong Answer

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LS() for _ in range(M)]
path = {}
allpath = []

for ind,ab in enumerate(AB):
  if ab[0] not in path:
    path[ab[0]] = []
  tmp = []
  tmp.append(ind+1)
  tmp.append(ab[1])
  path[ab[0]].append(tmp[::])
  if ab[1] not in path:
    path[ab[1]] = []
  tmp = []
  tmp.append(-ind-1)
  tmp.append(ab[0])
  path[ab[1]].append(tmp[::])

#print(path)

# すべての部屋を通る方法があるはず
# 1から全部屋通って1に行くルートがあるはず

def dfs(st, end):
  global allpath
  stack = []
  #res = []
  is_passed = [False] * (M*2+1)
  hist = [[0, '0']]
  now = [0, st]
  pre = None
  st_flag = (st!=end)
  while True:
    #print(now)
    #print(stack)
    hist.append(now)
    #print(hist)
    if now[0] != 0:
      if now[1] != '1':
      	is_passed[now[0]] = True
    if st_flag and now[1] == end:
      # ended
      #print("\tsuccess! route is below:\n\t\t{0}".format(hist))
      allpath.append(hist)
      if not stack:
        break
      next = stack[len(stack)-1]
      target_p = AB[abs(next[0])-1]
      if target_p[0] == next[1]:
        target = target_p[1]
      else:
        target = target_p[0]
      for i,v in enumerate(hist[-2::-1]):
        if v[1] == target:
          break
        is_passed[v[0]] = False
      #print("hit id is {0}".format(i))
      hist = hist[0:len(hist)-i-1]
      #print(hist)
    else:
      st_flag = True
      useflag = True
      for v in path[now[1]]:
        if is_passed[v[0]]:
          continue
        if v[1]==hist[len(hist)-2][1]:
          continue
        for w in hist[2:]:
          if v[1]==w[1]:
            break
        else:
          stack.append(v)
          useflag = False
        continue
      if useflag:
        #print("\tno route from path{0}".format(now))
        #print("\tstack is {0}".format(stack))
        if not stack:
          break
        next = stack[len(stack)-1]
        #print("\tnext is {0}".format(next))
        target_p = AB[abs(next[0])-1]
        if target_p[0] == next[1]:
          target = target_p[1]
        else:
          target = target_p[0]
        #print("\ttarget is {0}".format(target))
        for i,v in enumerate(hist[::-1]):
          if v[1] == target:
            break
          is_passed[v[0]] = False
        hist = hist[0:len(hist)-i]
    if not stack:
      #print("\tno stack: {0}".format(now))
      break
    now = stack.pop()

dfs('1','1')
for P in allpath:
  if len(P) == N+2:
    print("yes")
    Q = []
    for p in P:
      if p[0] == 0:
        continue
      tmp = AB[abs(p[0])-1][0]
      if tmp == p[1]:
      	tmp = AB[abs(p[0])-1][1]
      Q.append([tmp, p[1]])
    Q.sort(key=lambda x:x[0])
    #print(Q)
    for q in Q[1:]:
      print(q[1])
    break

Submission status: Wrong Answer

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_edges_from(s)

for x in sorted(nx.bfs_predecessors(g,1)):
    print(x[1])

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
par = [0] * (n+1)

for _ in range(m):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
print(G)
visited = [0] + [1] + [0] * (n-1)
q = deque()
q.append(1)
while q:
    now = q.popleft()
    #print("now:", now)
    visited[now] = 1
    for next in G[now]:
        #print("next:", next)
        #print("visited:", visited)
        if visited[next]:
            continue
        q.append(next)
        par[next] = now
        visited[next] = 1
print("Yes")
print("\n".join(map(str, par[2:])))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = []
B = []
pt = [[] for i in range(N)]
for i in range(M):
	a, b =  map(int, input().split())
	a -=1
	b -=1
	pt[a].append(b)
	pt[b].append(a)
n=N
res_list = [-1] * N
def bfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
                    res_list[j]=i
        q=q1
        c+=1
    return d
res = bfs(0)

no = 'No'
yes ='Yes'
print(res)
if -1 in res:
	print(no)
else:
	print(yes)
	
for i,x in enumerate(res_list):
	if i==0:
		continue
	print(x+1)

Submission status: Wrong Answer

Solution code:
import queue
import sys

readline = sys.stdin.readline


def main():
    n_rooms, n_passages = map(int, input().split())
    passages = (map(int, readline().strip().split()) for _ in range(n_passages))

    connections = [set() for _ in range(n_rooms+1)]  # type: list
    for a, b in passages:
        connections[a].add(b)
        connections[b].add(a)

    que = queue.Queue()
    que.put((0, 1))  # parent, current

    signs = [-1] * (n_rooms + 1)

    while not que.empty():
        parent, current = que.get()
        signs[current] = parent

        for room in connections[current]:
            if signs[room] == -1:
                que.put((current, room))

    print('Yes')
    for sign in signs[2:]:
        print(sign)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

from collections import deque
q = deque()

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

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now 
    
print("Yes")
for i in range(1, n):
    print(dist[i] + 1)

Submission status: Wrong Answer

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

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

from collections import deque
q = deque([0])
dist = [-1] * n
ans = [0] * n
while q:
    now = q.popleft()
    print(adj[now], dist, ans, q)
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [float("Inf")] * (n + 1)

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

for j in range(1, len(l)):
  if j == 1:
    print("Yes")
    continue
  print(l[j])

Submission status: Wrong Answer

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

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

for A, B in AB:
    graph[A-1] += [B]
    graph[B-1] += [A]

print(graph)

D = deque([0])
visited = [0] * N
visited[0] = 1

ret = [0 for i in range(N)]

while D:
    v = D.popleft()
    for i in graph[v]:
        i -= 1
        if visited[i]: continue
        visited[i] = 1
        ret[i] = v + 1
        D.append(i)

if any(ret[1:]):
    print("Yes")
    for i in ret[1:]:
        print(i)
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def m():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    dp = [10 ** 9] * (N + 1)
    visited = [False] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)


    def bfs(root):
        visited[root] = True
        dp[root] = 0
        queue = []
        for q in g[root]:
            dp[q] = root
            queue.append(q)
            visited[q] = True
        while queue:
            q = queue.pop()
            for k in g[q]:
                if not visited[k]:
                    queue.append(k)
                    dp[k] = q
                    visited[k] = True
    bfs(1)

    if not all(visited[2:]):
        print('No')
        return

    print('Yes')
    for j in dp[2:]:
        print(j)
    return

m()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

q = deque([1])
prev=[1]
siru = [0] * (n-1)
while q:

    now = q.popleft()
    
    next = graph[now-1]

    
    for n in next:
        if not siru[n-2]: 
            q.append(n)
            siru[n-2] = now


print("Yes")
print("\n".join(map(str, siru)))

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n,m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for i in range(1,m+1):
        a,b = map(int, input().split())
        graph[a-1].append(b)
        graph[b-1].append(a)
    
    q = deque([1])
    prev=[1]
    siru = [0] * (n-1)
    while q:
    
        now = q.popleft()
        
        next = graph[now-1]
    
        
        for n in next:
            if not siru[n-2]: 
                q.append(n)
                siru[n-2] = now
    
    
    print("Yes")
    print("\n".join(map(str, siru)))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

q = deque([1])
prev=[1]
siru = [0] * (n-1)
while q:

    now = q.popleft()
    
    next = graph[now-1]

    
    for n in next:
        if not siru[n-2]: 
            q.append(n)
            siru[n-2] = now
    if not 0 in siru:
        break



print("Yes")
print("\n".join(map(str, siru)))

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n,m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for i in range(1,m+1):
        a,b = map(int, input().split())
        graph[a-1].append(b)
        graph[b-1].append(a)
    
    q = deque([1])
    prev=[1]
    siru = [0] * (n-1)
    while q:
    
        now = q.popleft()
        
        next = graph[now-1]
    
        
        for n in next:
            if not siru[n-2]: 
                q.append(n)
                siru[n-2] = now
        if not 0 in siru:
            break
    
    
    
    print("Yes")
    print("\n".join(map(str, siru)))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

ans = [0] * (n+1)
alr = [0] * (n+1)
que = deque([1])
while len(que) > 0:
    idx = que.popleft()
    for i in path[idx]:
        if alr[i] == 0:
            que.append(i)
            ans[i] = idx
            alr[i] = 1
        else:
            pass

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

from collections import deque

N,M = map(int,input().split())
AB = deque()
for i in range(0,M):
    AB.append(list(map(int,input().split())))
#[list(map(int,input().split())) for x in range(0,M)]

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

start = 1
d = deque([start])
layer = {layer_idx:start}

while len(AB)>0:
    layer_idx += 1

    itnum_d = len(d)

    for ii in range(0,itnum_d):
        itnum = len(AB)
        start = d.popleft()

        for i in range(0,itnum):

            check = AB.popleft()

            if ans[check[0]] != 0 and ans[check[1]] != 0:
                break

            if check[0] == start:
                ans[check[1]] = start
                d.append(check[1])
            elif check[1] == start:
                ans[check[0]] = start
                d.append(check[0])
            else:
                AB.append(check)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# queue
q = deque()
q.append(0)
# 最初の部屋までの距離
dist = [INF] * n
# 直前の部屋
prev = [-1] * n
# 調べたかどうか
isReached = [False] * n

#### BFS ####
while len(q) != 0:
    # queueから値を取り出す
    v = q.pop()

    # vに隣接する部屋について調べる
    for u in to[v]:
        if dist[u] == INF and not isReached[u]:
            dist[u] = dist[v] + 1
            prev[u] = v
            isReached[u] = True
            q.append(u)

# print(prev)
print("Yes")
for i in range(1, len(prev)):
    print(prev[i] + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

q = deque([1])
prev=[1]
siru = [0] * (n-1)
while q:

    now = q.popleft()
    
    next = graph[now-1]

    
    for n in next:
        if not n in prev: 
            q.append(n)
            prev.append(n)
            siru[n-2] = now

if 0 in siru:
    print("No")
else:
    print(siru)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import queue

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)
        
    ### bfs ###
    q = queue.Queue()
    D = [-1]*N # 最短距離
    s = 1 # 始点
    step = 0
    D[s-1] = step
    while True:
        # print('s',str(s))
        step = D[s-1] + 1
        for v in vum[s]:
            # print('v',str(v))
            if D[v-1] < 0:
                # print('append v',str(v),str(step))
                q.put(v)
                D[v-1] = step
        if q.empty():
            break
        # print(list(q.queue),V)
        s = q.get()

    if -1 in D[1:]:
        print('No')
        return
    else:
        print('Yes')
    for d in D[1:]:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import queue

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)
        
    ### bfs ###
    q = queue.Queue()
    D = [-1]*N # 最短距離
    s = 1 # 始点
    step = 0
    D[s-1] = step
    while True:
        # print('s',str(s))
        step = D[s-1] + 1
        for v in vum[s]:
            # print('v',str(v))
            if D[v-1] < 0:
                # print('append v',str(v),str(step))
                q.put(v)
                D[v-1] = step
        if q.empty():
            break
        # print(list(q.queue),V)
        s = q.get()

    if -1 in D:
        print('No')
        return
    else:
        print('Yes')
    for d in D[1:]:
        print(d)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
s=sum(A)

if s>N:
  print(-1)
  exit()
  
print(N-s)

Submission status: Wrong Answer

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

if sum>N:
  print(-1)
  exit()
  
print(N-sum)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

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

i = [] #頂点(始点)
j = [] #頂点(終点)
d = [] #頂点間の距離
for _ in range(M):
    A,B = map(int,input().split())
    i.append(A-1)
    j.append(B-1)
    d.append(1)

graph = csr_matrix((d, (i, j)), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=False)

pred = pred + 1
print("Yes")
print(*pred[1:],sep="\n")

Submission status: Wrong Answer

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

cavelist = [
    {
        "caveId": i,
        "connected": set()
    }
    for i in range(1, n + 1)
]

for i in range(m):
    temp = input().split(" ")

    cavelist[int(temp[0]) - 1]["connected"].add(int(temp[1]))
    cavelist[int(temp[1]) - 1]["connected"].add(int(temp[0]))

goalpath = [0 for i in range(n - 1)]

out = {1}

tempNext = {1}

while True:
    next = tempNext
    tempNext = set()

    for id in next:
        cave = cavelist[id - 1]
        conn = cave['connected']

        for c in conn:
            if goalpath[c - 2] == 0:
                goalpath[c - 2] = cave['caveId']

        tempNext = tempNext | (conn - out)
        out = out | tempNext

    if tempNext == set():
        break

    if not (0 in goalpath):
        break

if 0 in goalpath:
    print('No')
else:
    print('Yes')
    for p in goalpath:
        print(p)

Submission status: Wrong Answer

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

cavelist = [
    {
        "caveId": i,
        "connected": set()
    }
    for i in range(1, n + 1)
]

for i in range(m):
    temp = input().split(" ")

    cavelist[int(temp[0]) - 1]["connected"].add(int(temp[1]))
    cavelist[int(temp[1]) - 1]["connected"].add(int(temp[0]))

goalpath = [0 for i in range(n - 1)]

out = {1}

tempNext = {1}

while True:
    next = tempNext
    tempNext = set()

    for id in next:
        cave = cavelist[id - 1]
        conn = cave['connected']

        for c in conn:
            if goalpath[c - 2] == 0:
                goalpath[c - 2] = cave['caveId']

        tempNext = tempNext | (conn - out)
        out = out | tempNext

    if tempNext == set():
        break

if 0 in goalpath:
    print('No')
else:
    print('Yes')
    for p in goalpath:
        print(p)

Submission status: Wrong Answer

Solution code:
import sys
import os
from collections import deque

def file_input():
    f = open('ABC168/input.txt', 'r')
    sys.stdin = f

def main():
    if os.getenv("ENV")=='LOCAL':
        file_input()

    N,M=map(int, input().split())
    r={}
    for i in range(M):
        A,B=map(int, input().split())
        # print("A:"+str(A[i])+" B:"+str(B[i]))
        if A not in r:
            r[A]=[B]
        else:
            r[A].append(B)
        if B not in r:
            r[B]=[A]
        else:
            r[B].append(A)
        # print(tmp[A[i]-1])
    # print(r)

    q=deque()
    q.append(1)
    visited=set()
    out=[0]*(N-1)
    while len(q)>0:
        # print("q="+str(q))
        position=q.popleft()
        # print("p="+str(position))
        for des in r[position]: #今いる場所から行ける場所を探索
            if des not in visited:  #訪問済みでないなら
                q.append(des)   #行ける場所だった場合キューに追加
                visited.add(des)   #訪問済みにする
                out[des-2]=position
                # print("destination="+str(des)+" p="+str(position)+" q="+str(q))
    # print(visited)



    print('Yes')
    [print(x) for x in out]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

isOk = True

def bfs(s):
    queue = [[s]]
    isSearch = [False]*(n+1)
    isSearch[s] = True
    while(len(queue)>0):
        now = queue.pop(0)
        last = now[-1]
        if last==1:
            return now
        for x in mp[last]:
            if isSearch[x]:
                continue
            queue.append(now+[x])

searched = [False]*(n+1)
ans = [0]*(n+1)
for i in range(2,n+1):
    if searched[i]:
        continue
    l = bfs(i)
    print(l)
    pre = 0
    for j in l:
        searched[j] = True
        if pre==0:
            pre = j
            continue
        if ans[pre]==0:
            ans[pre]=j
            pre = j
            continue
        if ans[pre]!=j:
            isOk=False
            break
            
        
if(isOk):
    print('Yes')
    for i in range(2,n+1):
        print(ans[i])
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict

n,m = map(int, input().split())
g = defaultdict(lambda: 0)
reached = list(range(1,n+1))
misi = [0 for _ in range(n+1)]

q = []

def bfs(x):
	q.append(x)
	while(len(q) != 0):
		now = q.pop(0)
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				reached.remove(k)
				q.append(k)

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

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(len(reached)==0):
	print("yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")

Submission status: Wrong Answer

Solution code:
import sys
import os
from collections import deque

def file_input():
    f = open('ABC168/input.txt', 'r')
    sys.stdin = f

def main():
    if os.getenv("ENV")=='LOCAL':
        file_input()

    N,M=map(int, input().split())
    r={}
    for i in range(M):
        A,B=map(int, input().split())
        # print("A:"+str(A[i])+" B:"+str(B[i]))
        if A not in r:
            r[A]=[B]
        else:
            r[A].append(B)
        if B not in r:
            r[B]=[A]
        else:
            r[B].append(A)
        # print(tmp[A[i]-1])
    # print(r)

    q=deque()
    q.append(1)
    visited=set()
    out=[0]*(N-1)
    while len(q)>0:
        # print("q="+str(q))
        position=q.popleft()
        # print("p="+str(position))
        visited.add(position)
        for des in r[position]: #今いる場所から行ける場所を探索
            if des in visited:  #すでに訪問済み
                continue
            # if des in q:    #ループよけ 2→2みたいな
            #     continue
            q.append(des)   #行ける場所だった場合キューに追加
            # print("destination="+str(des)+" p="+str(position)+" q="+str(q))
            out[des-2]=position
    # print(visited)



    print('Yes')
    [print(x) for x in out]

if __name__ == '__main__':
    main()