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:
from copy import deepcopy
def main():
    global flags, edges
    n, m = map(int, input().split())

    flags = {e:[0, n+1] for e in range(1, n + 1)}
    flags[1][1] = 0
    edges = {e:set() for e in range(1, n + 1)}
    edge_list = []
    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].add(b)
        edges[b].add(a)
        edge_list.append((a, b))

    distance = 1
    node_next = list(edges[1])
    node_next_next = []
    while node_next:
        for next in node_next:
            if flags[next][1] > distance:
                flags[next][1] = distance
                node_next_next += edges[next]
        node_next = deepcopy(node_next_next)
        node_next_next = []
        distance += 1
    for edge in edge_list:
        e1 = edge[0]
        e2 = edge[1]
        if flags[e1][1] > flags[e2][1]:
            flags[e1][0] = e2
        else:
            flags[e2][0] = e1
    result = [flags[f][1] < (n + 1) for f in flags if f > 1]
    if not all(result):
        print('No')
    else:
        print('Yes')
        for i1 in range(2, n + 1):
            print(flags[i1][0])
            
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)
# hex_str = hex(i)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()

	ans = {}
	ans[0] = 0
	ki = [[] for i in range(N)]

	for i in range(M):
		A,B = inputMap()
		A -= 1
		B -= 1
		ki[A].append(B)
		ki[B].append(A)

	print("Yes")
	stc = Queue()
	for ii in ki[0]:
		ans[ii] = 0
		stc.enqueue(ii)

	while True:
		next = stc.dequeue()
		#print(next)
		if next == None:
			break
		for ii in ki[next]:
			if ii in ans:
				pass
			else:
				ans[ii] = next
				stc.enqueue(ii)

	#print(ans)
	#print(ki)
	aa = [0 for i in range(N)]
	for k, v in ans.items():
		if k == 0:
			continue
		aa[k] = v+1

	#print(aa)


class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import collections

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

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

queue = collections.deque([0])
visited = [-1]*N
visited[0] = 0
while queue:
    x = queue.popleft()
    for i in G[x]:
        if visited[i] == -1:
            visited[i] = visited[x] + 1
            queue.append(i)
print("Yes")
print(*visited[1:], sep="\n")

Submission status: Wrong Answer

Solution code:
import queue

q = queue.Queue()
N, M = map(int, input().split())

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

for i in range(M):
  A, B = map(int, input().split())
  path[A-1].append(B)
  path[B-1].append(A)
q.put(1)
COUNTER = 0
while not q.empty() :
  now = q.get()
  for p in path[now-1]:
    if ans[p-2]==-1:
      ans[p-2]=now
      q.put(p)
      #print(COUNTER, now,p)
      COUNTER+=1
  
print("Yes")
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(500000)

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

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

for i in range(m):
    ta,tb=map(int, input().split())
    if ta!=1:
        a[tb-1].append(ta-1)
    if tb!=1:
        a[ta-1].append(tb-1)

KITENAI=900000
mk=[KITENAI]*n
mk[0]=0
qu=[0]

def setnext(now):
    global mk
    global qu

    for i in a[now]:
        if mk[i]==KITENAI:
            qu.append(i)
            mk[i]=mk[now] + 1

while len(qu)>0:
    setnext(qu.pop(0))

print("Yes")
for i in range(n-1):
    print(mk[i+1])

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,(input().split())))
sign=[]
for k in range(M):
  A,B=list(map(int,(input().split())))
  sign.append(sorted([A,B]))
len_goal=[[-1,-1] for k in range(N+1)]
len_goal[1][0]=1
len_goal[1][1]=1

sign=sorted(sign)

for room in sign:
  # 両方に深さが設定されている場合、深いほうの深さを浅い方+1にして、行き先を浅い方にする
  if(len_goal[room[0]][0]>len_goal[room[1]][0] and len_goal[room[1]][0]>=0):
    len_goal[room[0]][0]=len_goal[room[1]][0]+1
    len_goal[room[0]][1]=room[1]
  # 上に同じ
  elif(len_goal[room[1]][0]>len_goal[room[0]][0] and len_goal[room[0]][0]>=0):
    len_goal[room[1]][0]=len_goal[room[0]][0]+1
    len_goal[room[1]][1]=room[0]

  # 片方にのみ深さが設定されている場合、もう片方の深さを片方+1にして、行き先を片方にする
  elif(len_goal[room[0]][0]<0 and len_goal[room[1]][0]>=0):
    len_goal[room[0]][0]=len_goal[room[1]][0]+1
    len_goal[room[0]][1]=room[1]

  # 上に同じ
  elif(len_goal[room[0]][0]>=0 and len_goal[room[1]][0]<0):
    len_goal[room[1]][0]=len_goal[room[0]][0]+1
    len_goal[room[1]][1]=room[0]


print("Yes")
for z in len_goal[2:]:
  print(z[1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]


route = {}

for i in range(M):
    A, B = [int(x) for x in input().split()]

    if A in route:
        route[A].append(B)
    else:
        route[A] = [B]    

    if B in route:
        route[B].append(A)
    else:
        route[B] = [A]  

step = {}
stepcount = 0
mark = {1: 0}
r = 1

def check(stepcount, r):
    global mark
    stepcount += 1
    if r in route:
        for nextr in route[r]:
            # print(nextr)
            # print(route[nextr])
            if nextr in step:
                # 既存のルートが有る
                if step[nextr] > stepcount:
                    # 今回のルートのほうが近い
                    step[nextr] = stepcount
                    mark[nextr] = r
 
            else:
                # ルートが無い
                step[nextr] = stepcount
                mark[nextr] = r
                #check(stepcount, nextr)

check(0, 1)

# print(route)
if len(mark) == N:
    print('Yes')
    for i in range(2, N + 1):
        print(mark[i])
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque


def bfs(s):
    queue = deque([s])
    cv = [0] * n
    cv[s] = 1
    dist[0] = 0
    while queue:
        u = queue.popleft()
        for nxt in adj[u]:
            if not cv[nxt]:
                queue.append(nxt)
                cv[nxt] = 1
                if dist[u] + 1 < dist[nxt]:
                    dist[nxt] = dist[u] + 1
                    parent[nxt] = u


def dfs(u):
    st = [u]
    cv = [0] * n
    dist[0] = 0
    while st:
        u = st.pop()
        if cv[u]:
            continue
        cv[u] = 1
        for nxt in adj[u]:
            if dist[u] + 1 < dist[nxt]:
                parent[nxt] = u
                dist[nxt] = dist[u] + 1
            st.append(nxt)


n, m = [int(item) for item in input().split()]
parent = [-1] * n
dist = [float('inf')] * n
parent[0] = 0
adj = defaultdict(list)
for i in range(m):
    u, v = [int(item) - 1 for item in input().split()]
    adj[u].append(v)
    adj[v].append(u)
dfs(0)
# print(parent, adj)
if -1 in parent:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(parent[i] + 1)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

visited={1}
stack=deque([[1,0]])
re=[-1 for i in range(N+1)]
re[0]=0
re[1]=0
while stack:
    #print(stack)
    a,m=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            re[p]=m+1
            stack.append([p,m+1])
#print(re)
if -1 in re:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(re[i])

Submission status: Wrong Answer

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

p=[0]*n
p[0]=1
now=1
while 0 in p:
    cnt=0
    for to in l[now-1]:
        if p[to]==0:
            p[to]=now
            cnt+=1
    if cnt==0:
        break
    now=to+1
if 0 in p:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(p[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
d=deque()

l=[[] for _ in range(n)]
R=[-1]*(n+1)
R[1]=0

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

def g(s):
    for i in range(len(l[s-1])):
        if R[l[s-1][i]]==-1:
            R[l[s-1][i]]=s
            d.append(l[s-1][i])
    if len(d)!=0:
        s=d.popleft()
        return g(s)
    else:
        return
g(1)
for h in range(2,len(R)):
    print(R[h])

Submission status: Wrong Answer

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

ans_li = [-1]*n
queue=deque([0])
visited = [False]*n

while queue:
    x = queue.pop()
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
# from math import factorial
import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)
n, m = list(map(int, input().split()))
room = [[] for i in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    room[a-1].append(b-1)
    room[b-1].append(a-1)

ans = [-1]*n


def bfs(i):
    q = deque()
    q.append(i)
    while q:
        x = q.popleft()
        print(x)
        for i in range(len(room[x])):
            if ans[room[x][i]] == -1:
                q.append(room[x][i])
                ans[room[x][i]] = x
    return


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

Submission status: Wrong Answer

Solution code:
from collections import deque

import sys
input = sys.stdin.readline 

N,M = map(int,input().split())
path = [[] for i in range(N)]
ans = [None for i in range(N)]
visited = [0 for i in range(N)]

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

print(path)

def bfs(path, root,visited):
  visited[root] = 1
  queue = deque([root])
  while queue:
    cur = queue.popleft()
    for chi in path[cur]:
      if visited[chi] == 1:
        continue
      else:
        ans[chi] = cur + 1
        visited[chi] = 1
        queue.append(chi)

  if all([i == 1 for i in visited]):
    return "Yes"
  else:
    return "No"
  
flag = bfs(path,0,visited)

print(flag)

if flag == "Yes":
  for i in range(1,N):
    print(ans[i])

Submission status: Wrong Answer

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

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

for i in range(M):
  A, B = map(int, input().split())
  path[A-1].append(B)
  path[B-1].append(A)
nows = [1]
COUNTER = 0
while len(nows)>0 :
  now = nows.pop(0)
  for p in path[now-1]:
    if ans[p-2]==-1:
      ans[p-2]=now
      nows.append(p)
      #print(COUNTER, now,p)
      COUNTER+=1
  
print("Yes")
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]


route = {}

for i in range(M):
    A, B = [int(x) for x in input().split()]

    if A in route:
        route[A].append(B)
    else:
        route[A] = [B]    

    if B in route:
        route[B].append(A)
    else:
        route[B] = [A]  

step = {}
stepcount = 0
mark = {1: 0}
r = 1

def check(stepcount, r):
    global mark
    stepcount += 1
    if r in route:
        for nextr in route[r]:
            # print(nextr)
            # print(route[nextr])
            if nextr in step:
                # 既存のルートが有る
                if step[nextr] > stepcount:
                    # 今回のルートのほうが近い
                    step[nextr] = stepcount
                    mark[nextr] = r
            else:
                # ルートが無い
                step[nextr] = stepcount
                mark[nextr] = r
                check(stepcount, nextr)

#check(0, 1)

# print(route)
if len(mark) == N:
    print('Yes')
    for i in range(2, N + 1):
        print(mark[i])
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import deque

# n: 部屋
# m: 通路
n, m = map(int, input().split())
eage = [[] for _ in range(n)]
for _ in range(m):
  room_1, room_2 = map(int, input().split())
  room_1 -= 1
  room_2 -= 1
  eage[room_1].append(room_2)
  eage[room_2].append(room_1)

# 隣接リスト
# [[1], [0, 2, 3], [1, 3], [2, 1]]


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

for start_point in range(n):
  # スタートが最初の部屋のとき
  if start_point == 0:
    print("Yes")
    continue

  print( bfs(start_point) )

Submission status: Wrong Answer

Solution code:
nm=list(map(int, input().split()))
n=nm[0]
m=nm[1]
ab=[]
ans=['Yes']+[0]*(n-1)
room=[i+2 for i in range(n-1)]

for i in range(m):
    ab.append(list(map(int, input().split())))

roomto=[1]
flg=True
while flg:
    roomto1=[]
    path=[]
    flg=False
    abc=ab.copy()
    for pair in ab:
        print(pair)
        if pair[0] in roomto and pair[1] in room:
            roomto1.append(pair[1])
            abc.remove(pair)
            path.append(pair)
            flg=True
        elif pair[1] in roomto and pair[0] in room:
            roomto1.append(pair[0])
            abc.remove(pair)
            path.append(pair)
            flg=True
    ab=abc
    roomto1=list(set(roomto1))
    roomto=roomto1
    for r in roomto1:
        room.remove(r)
        for pair in path:
            if r==pair[0]:
                ans[r-1]=pair[1]
            elif r==pair[1]:
                ans[r-1]=pair[0]


if 0 not in ans:
    for value in ans:
        print(value)
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
lis = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    lis[a].append(b)
    lis[b].append(a)
queue = deque([1])
dist_list = [-1]*(n+1)
dist_list[1] = 0
while len(queue) != 0:
    now = queue.popleft()
    for v in lis[now]:
        if dist_list[v] == -1:
            dist_list[v] = dist_list[now] + 1
            queue.append(v)
for i in range(2, n+1):
    for v in lis[i]:
        if dist_list[v] == dist_list[i]-1:
            print(v)
            break

Submission status: Wrong Answer

Solution code:
from collections import deque

# n: 部屋
# m: 通路
n, m = map(int, input().split())
eage = [[] for _ in range(n)]
for _ in range(m):
  room_1, room_2 = map(int, input().split())
  room_1 -= 1
  room_2 -= 1
  eage[room_1].append(room_2)
  eage[room_2].append(room_1)

# 隣接リスト
# [[1], [0, 2, 3], [1, 3], [2, 1]]


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

for start_point in range(n):
  # スタートが最初の部屋のとき
  if start_point == 0:
    print("Yes")
    continue

  print( bfs(start_point) )

Submission status: Wrong Answer

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

e = [[]]*n



for _ in range(m):
    a, b = [int(i) for i in input().split()]
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    
    
q = deque()
q.append(0)
ans = np.ones(n-1)
check = np.zeros(n)

while len(q) > 0:
    # キューの先頭（左端）からnodeを取り出す
    node = q.popleft()

    if node is not None:
        check[node] = 1
        con = e[node]
        for i in con:
            if check[i] ==0:
                ans[i-1] = int(node) + 1
                q.append(i)

        

print('Yes')

for i in ans:
    print(int(i))

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
ab = np.array([list(map(int, input().split())) for _ in range(M)])

dp = [[0, float("inf")] for _ in range(N + 1)]

tmp = {1}
while tmp:
    for i in list(tmp):
        abi = ab[np.any(ab == i, axis=1)]
        ab = np.delete(ab, np.where(ab == i)[0], axis=0)
        for a, b in abi:
            if a == 1:
                dp[b][0] = 1
                dp[b][1] = 1
                tmp.add(b)
            elif b == 1:
                dp[a][0] = 1
                dp[a][1] = 1
                tmp.add(a)
            else:
                if dp[a][1] > dp[b][1] + 1:
                    dp[a][0] = b
                    dp[a][1] = dp[b][1] + 1
                if dp[b][1] > dp[a][1] + 1:
                    dp[b][0] = a
                    dp[b][1] = dp[a][1] + 1
                tmp.add(a)
                tmp.add(b)
        tmp.remove(i)

for ans in dp[2 : N + 1]:
    print(ans[0])

Submission status: Wrong Answer

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

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

for i in range(M):
  A, B = map(int, input().split())
  path[A-1].append(B)
  path[B-1].append(A)
nows = [1]
COUNTER = 0
while len(nows)>0 :
  buf = []
  for now in nows:
    for p in path[now-1]:
      if ans[p-2]==-1:
        ans[p-2]=now
        buf.append(p)
        #print(COUNTER)
        COUNTER+=1
  nows = buf
  
print("Yes")
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import copy




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

INF = 1000000
kamban = [[-1, INF] for _ in range(n+1)]
kamban[1] = [1, 0]

for i in range(m):
    a, b = map(int, input().split())
    if kamban[a][1] <= kamban[b][1]:
        kamban[b] = [a, kamban[a][1]+1]
    else:
        kamban[a] = [b, kamban[b][1]+1]

if [-1, INF] in kamban[1:]:
    print("No")
else:
    print("Yes")
    for k in kamban[2:]:
        print(k[0])

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

n, m = list(map(int, input().split()))
a = np.zeros((m,), dtype=np.int)
b = np.zeros((m,), dtype=np.int)
for i in range(m):
    a[i], b[i] = list(map(int, input().split()))
a -= 1
b -= 1

is_visited = np.zeros((n,), dtype=np.bool)
parent = np.zeros((n,), dtype=np.int)

q = deque()
q.append(0)
is_visited[0] = True
while len(q) != 0:
    node = q.popleft()
    for i in np.where(a == node)[0]:
        child = b[i]
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)
    for i in np.where(b == node)[0]:
        child = a[i]
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)

parent += 1

print('Yes')
print('\n'.join(list(map(str, parent))))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)
# hex_str = hex(i)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()

	ans = [inf for i in range(N)]
	ki = [[] for i in range(N)]

	for i in range(M):
		A,B = inputMap()
		A -= 1
		B -= 1
		ki[A].append(B)
		ki[B].append(A)

	print("Yes")
	stc = Stack()
	for ii in ki[0]:
		ans[ii] = 0
		stc.push(ii)

	while True:
		next = stc.pop()
		if next == None:
			break
		for ii in ki[next]:
			if ans[ii] == inf:
				ans[ii] = next
				stc.push(ii)

	#print(ans)
	#print(ki)
	for i,val in enumerate(ans):
		if i == 0:
			continue
		print(val+1)



class Stack:
    def __init__(self, stack = None):
        if type(stack) is type([]):
            self.stack = stack
        else:
            self.stack = []

    def push(self, e):
        self.stack.append(e)
        return self.stack

    def pop(self):
        try:
            sEl = self.stack.pop()
            return sEl
        except IndexError:
            return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()