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 sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
L = [N+1] * (N)
for i in range(M):
  A, B = map(int, input().split())
  if L[A-1] == N + 1 and A != 1:
    L[A-1] = B
  elif L[B-1] == N + 1 and B != 1:
    L[B-1] = A
L = L[1:]
#print(L)
if N + 1 in L or 1 not in L:
  print('No')
else:
  print('Yes')
  [print(i) for i in L]

Submission status: Wrong Answer

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

siru=[-1]*(N-1)#2~~N
que=[[0]]

while len(que)>0:
    nowlist=que.pop(0)
    now=nowlist[-1]
    nexlist=G[now]
    for nex in nexlist:
        if siru[nex-1]==-1:
            siru[nex-1]=now
            que.append(nowlist+[nex])
X=siru.count(-1)
if X>=1:
    print("No")
else:
    print("Yes")
    for num in siru:
        print(num+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
d = defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)
ans = [-1] * N
cnt = 0
stack = [1]
while stack:
    val = stack.pop()
    next_vals = d[val]
    for nxt in next_vals:
        if ans[nxt - 1] == -1:
            ans[nxt - 1] = val
            stack.append(nxt)
            cnt += 1
if cnt >= N - 1:
    print("Yes")
    for i in range(1, N):
        print(ans[i])
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
import heapq

n, m = list(map(int, input().split()))
a = [0] * m
b = [0] * m
path = [[] for i in range(n+1)]

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

# 部屋1から出発して、
ans = [0]*(n+1)
visited = [1]
que = deque([[1, 1]])  # 今の場所、前の場所
now = 1
prev = 1
# BFS
while len(visited) != n:
    for can_go in path[now]:
        que.append([can_go, now])
    now, prev = que.popleft()
    if (now in visited):
        continue
    ans[now] = prev
    visited.append(now)
for _ans in ans[2:]:
    print(_ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
n,m = map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

dist = [float("inf")]*n
seen = [False]*n
ans = [0]*n
def f(s):
    PQ = [(0,s)]
    dist[s] = 0
    seen[s] = True
    while PQ:
        u,md = heappop(PQ)
        seen[u] = True
        if dist[u] < md: continue
        for v in G[u]:
            if seen[v]: continue
            if dist[v] > dist[u] + md:
                dist[v] = dist[u] + md
                heappush(PQ,(v,dist[v]))
                ans[v] = u+1
f(0)
print("Yes")
for i in range(1,n): print(ans[i])

Submission status: Wrong Answer

Solution code:
# # -*- coding: utf-8 -*-

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

#
import collections
buf = collections.deque()
parents = [-1 for _ in range(N)]

parents[0] = 0
buf.append(1)

while buf:
    src = buf.popleft()
    for dst in graph[src]:
        if parents[dst] == -1:
            parents[dst] = src
            buf.append(dst)

if all([p != -1 for p in parents]):
    print('Yes')
    for p in parents[1:]:
        print(p)
else:
    print('No')

Submission status: Wrong Answer

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

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

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

ans = []
for i in range(1,n):
    if i in route_li[0]:
        print(i)
        ans.append(1)
        continue
    for j in range(1,n):
        if i==j:
            continue
        if 0 in route_li[j]:
            if j in route_li[i]:
                print(i,j)
                ans.append(j+1)
                break
if len(ans)==(n-1):
    print('Yes')
    print('\n'.join(map(str,ans)))
else:
    print('No')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
to = [[] for _ in range(N)]
ans = [-1] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

from collections import deque

Q = deque([0])
ans[0] = -2

while Q:
    v = Q.popleft()
    for s in to[v]:
        if ans[s] == -1:
            ans[s] = v
            Q.append(s)

print(*(a + 1 for a in ans[1:]), sep="\n")

Submission status: Wrong Answer

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
depth=[10**18]*(n+1)
depth[1]=0
ans=[0]*(n+1)
while len(q)!=0:
  v=q.pop()
  for u in g[v]:
    if depth[u]>depth[v]+1:
      depth[u]=depth[v]+1
      ans[u]=v
    if check[u]==0:
      check[u]=1
      q.append(u)
print('Yes')
for i in range(2,n+1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
# int(input()) # 入力が1つ
from collections import deque
n, m = map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

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

def bfs(graph, n, start):
    visited = [False] * n
    visited[start] = True
    cost = [float('inf')] * n
    cost[0] = 0
    que = deque([start])
    count = 1
    while que:
        root = que.popleft()
        for node in graph[root]:
            if not visited[node]:
                visited[node] = True
                cost[node] = count
                que.append(node)
        count += 1
    result = all(visited)
    return result, cost

r, cost = bfs(graph, n, 0)
if r:
    print('Yes')
    for c in cost[1:]:
        print(c)
else:
    print('No')

Submission status: Wrong Answer

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,w = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
# print(dijkstra(0,n,w,cost))
ANS = dijkstra(0,n,w,cost)

if float("inf") in ANS:
    print("No")
else:
    print("Yes")
    for i in ANS[1:]:
        print(i)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
from collections import deque
d = deque([[0,0]]) # 左は今考えてる部屋、右は前の部屋
ans = [-1 for i in range(n)]
while d:
    u,v = d.popleft()
    if ans[u] == -1:
        ans[u] = v
    for j in g[u]:
        if ans[j] == -1:
            d.append([j,u])
        else:
            continue
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


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    pas = [-1 for _ in range(N)]
    pas[S] = 's'
    frag = set([S])
    que = deque([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:
            if i in frag:  # 処理済みか否か
                continue
            pas[i]=q
            que.append(i)
            frag.add(i)
    return pas


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

near = [[] for _ in range(n)]
for a, b in ab:
    near[a - 1].append(b - 1)
    near[b - 1].append(a - 1)
pas = bfs(near, 0, n)

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

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    N, M = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    dist = [-1 for _ in range(N)]

    def bfs(s):
        que = deque()
        dist[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)

    bfs(0)
    if all(dist[i] != -1 for i in range(1, N)):
        print("Yes")
        for i in range(1, N):
            print(dist[i])
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def a(graph,ans,ind):
    Q=graph[ind]
    for q in Q:
        if ans[q]!=-1:
            break
        ans[q]=ind
        a(graph,ans,q)

def main():
    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-1)
        graph[B-1].append(A-1)
    #print(graph)
    ans=[-1]*N
    Q=graph[0]
    for q in Q:
        ans[q]=0
        a(graph,ans,q)
    for w in ans:
        if w==-1:
            print("No")
            break
    print("Yes")
    for w in ans[1:]:
        print(w+1)
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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


n, m = [int(item) for item in input().split()]
parent = [-1] * 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 collections import deque
import sys
input = sys.stdin.readline


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    pas = [-1 for _ in range(N)]
    pas[S] = 's'
    frag = set([S])
    que = deque([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:
            if i in frag:  # 処理済みか否か
                continue
            pas[i]=q
            que.append(i)
            frag.add(i)
    return pas


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

near = [[] for _ in range(n)]
for a, b in ab:
    near[a - 1].append(b - 1)
    near[b - 1].append(a - 1)
print(near)

pas = bfs(near, 0, n)

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def dfs(v, p):
        for _, u in edge[v]:
            if u == p:
                continue
            elif visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u, v)

    visited = [False for _ in range(n)]
    visited[0] = True
    dfs(0, -1)
    for i in visited:
        if not i:
            print("No")
            exit()

    # ダイクストラ法：O(ElogV)
    def dijkstra_heap(s):
        # 始点sから各頂点への最短距離
        d = [f_inf] * n
        used = [True] * n  # True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist, e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            # まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])
        return d

    res = dijkstra_heap(0)
    print("Yes")
    for i in range(1, n):
        print(res[i])


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,M=acinput()


L=[[]for i in range(N+1)]
for i in range(M):
    tmp=acinput()
    L[tmp[0]].append(tmp[1])
    L[tmp[1]].append(tmp[0])
    
    
visited=[0]*(N+1)
queue=[1]

parent=[-1]*(N+1)
count=1
visited[1]=1
while True:
    
    q=queue.pop()

    
    for sq in L[q]:
        if not visited[sq]:
            visited[sq]=1
            parent[sq]=q
        
            queue.append(sq)
            count+=1
    
    if len(queue)==0:
        break

#if count!=N:
#    print("No")
#    sys.exit()

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



'''
5 4
1 2
2 3
4 5
5 4
'''

Submission status: Wrong Answer

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

d=[n+1 for i in range(n+1)]
d[1]=0
for i in range(1,n+1):
  for j in range(m):
    if l[j][0]==i:
      d[i]=min(d[i],d[l[j][1]]+1)
    if l[j][1]==i:
      d[i]=min(d[i],d[l[j][0]]+1)
      
for i in range(2,n+1):
  print(d[i])

Submission status: Wrong Answer

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

from collections import defaultdict
from collections import deque

def main():
    n, m = map(int, input().split())
    routes = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        routes[a].append(b)
        routes[b].append(a)

    rec = [0] * (n + 1)
    pos_queue = deque([1])
    while len(pos_queue) > 0:
        p = pos_queue.pop()
        for next_p in routes[p]:
            if not rec[next_p]:
                rec[next_p] = p
                pos_queue.append(next_p)

    print("Yes")
    print("\n".join(map(str, rec[2:])))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
def main():
    N, M = map(int, input().split())
    i = []
    j = []
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        i.append(a)
        j.append(b)
    d = [1] * M
    g = csr_matrix((d, (i, j)), shape=(N, N))
    d, p = dijkstra(g, directed = False, return_predecessors=True, indices=0)
    if min(p[1:]) < 0:
        print('No')
        return
    print('Yes')
    for i in range(1, N):
        print(p[i] + 1)
main()

Submission status: Wrong Answer

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

graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)
    
r = [-1 for i in range(N+1)] 
Q = deque([1])

while Q:
    x = Q.pop()
    for to in graph[x]:
        if r[to] == -1:
            r[to] = x 
            Q.append(to)

print("Yes")
for i in r[2:]:
    print(i)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque



import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    q = deque()
    q.append(1)
    d = {}
    d[1] = 0
    prev = {}
    while q:
        u = q.popleft()
        for v in g[u]:
            if v in d:
                continue
            d[v] = d[u] + 1
            prev[v] = u
            q.append(v)
    print('Yes')
    return [prev[i] for i in range(2, N+1)]


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

path = []

for _ in range(m):
    ai, bi = map(int, input().split())
    path.append([ai, bi])

# print(path)

linked = set()

for _ in range(m):
    for pi in path:
        if 1 in pi:
            linked.add(pi[0])
            linked.add(pi[1])
        if pi[0] in linked:
            linked.add(pi[1])
        elif pi[1] in linked:
            linked.add(pi[0])

if len(linked) == n:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque



import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    q = deque()
    q.append(1)
    d = {}
    d[1] = 0
    prev = {}
    while q:
        u = q.popleft()
        for v in g[u]:
            if v in d:
                continue
            d[v] = d[u] + 1
            prev[v] = u
            q.append(v)
    print('yes')
    return [prev[i] for i in range(2, N+1)]


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
  a+=[list(map(int,input().split()))]
a=sorted(a)
print('Yes')
b=[[i+1,0]for i in range(n)]
b[0][0]=0
for a in a:
  if b[a[0]-1][0]>b[a[1]-1][0]:
    b[a[0]-1][0]=b[a[1]-1][0]+1
    b[a[0]-1][1]=a[1]
  else:
    b[a[1]-1][0]=b[a[0]-1][0]+1
    b[a[1]-1][1]=a[0]
for i in range(1,n):
  print(b[i][1])

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
Gs = [[] for _ in range(N+1)]

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

ms = [0] * (N+1)
def bfs(c):
    queue = deque()
    ns = Gs[c]
    for n in ns:
        queue.append((n, c))
    while queue:
        c, p = queue.popleft()

        if ms[c] != 0:
            continue

        ms[c] = p

        ns = Gs[c]
        for n in ns:
            if n != p:
                queue.append((n, c))

bfs(1)

print(ms)
for m in ms[2:]:
    if m == 0:
        print('No')
        break
else:
    print('Yes')
    for m in ms[2:]:
        print(m)

Submission status: Wrong Answer

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n, m = map(int, input().split())
    edge = np.array([input().split() for _ in range(m)], dtype=np.int64).T
    a = csr_matrix(([1] * m, (edge - 1)), shape=(n, n))
    s, p = shortest_path(a, return_predecessors=True,
                         indices=0, directed=False)  # 最短経路p
    if min(s[1:]) < 1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
tree=[[] for _ in range(n+1)]
ans=[0]*n 
for _ in range(m):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
checked=[]
stack=[1]
while stack:
    p=stack.pop()
    for i in tree[p]:
        if i in checked:
            continue
        ans[i-1]=p
        checked.append(i)
        stack.append(i)

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

Submission status: Wrong Answer

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

Mark = [0 for _ in range(N+1)]
path = {k: [] for k in range(1, N+1)}
for i in range(M):
    A, B = [int(i) for i in input().split()]
    path[A].append(B)
    path[B].append(A)
next = [1]
while True:
    n = next.pop()
    for x in path[n]:
        # n -> x
        if Mark[x] == 0:
            Mark[x] = n
            next.append(x)

    if not next: break

print("\n".join([str(i) for i in Mark[2:]]))

Submission status: Wrong Answer

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=collections.deque()
q.append((1,0))
check=[0]*(n+1)
check[1]=1
depth=[10**18]*(n+1)
depth[1]=0
while len(q)!=0:
  v,d=q.pop()
  for u in g[v]:
    if depth[u]>d+1:
      depth[u]=d+1
    if check[u]==0:
      check[u]=1
      q.append((u,d+1))
ans=[10**18]*(n+1)
for v in range(2,n+1):
  tmp=10**18
  for u in g[v]:
    if tmp>depth[u]:
      ans[v]=u
      tmp=depth[u]
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())

path = [[] for i in range(N)]
indicator = [None] * N
indicator[0] = (0, 0)
for i in range(M):
    a, b = map(int, input().split())
    a-=1
    b-=1
    path[a].append(b)
    path[b].append(a)

def solve(N, path, indicator):
    visit = [False]*N
    visit[0] = True
    p = 0
    l = 0
    q = deque()
    q.append((0, 0))

    while q:
        (p, l) = q.pop()
        for room in path[p]:
            if visit[room]:
                continue
            if indicator[room] is None:
                indicator[room] = (p, l+1)
                q.append((room, l+1))
                visit[room] = True
            elif indicator[room][1] > l+1:
                return []

L = solve(N, path, indicator)
if L == []:
    print("No")
else:
    print("Yes")
    for p, l in indicator[1:]:
        print(p+1)

Submission status: Wrong Answer

Solution code:
import sys

n, m, *ab = map(int, sys.stdin.read().split())
ab = zip(*[iter(ab)] * 2)
graph = [[] for _ in range(n)]
for a, b in ab:
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)

def main():
    parent = [None] * n 
    parent[0] = 0
    stack = [0]
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if parent[y] is not None: continue 
            parent[y] = x
            stack.append(y)

    if None in parent:
        print('No')
    else:
        print('Yes')
        for i in range(1, n):
            print(parent[i] + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
X = defaultdict(list)
for i in range(M):
    Ai, Bi = map(lambda s: int(s) - 1, input().split())
    X[Ai].append(Bi)
    X[Bi].append(Ai)

V = [False] * N
P = [0] * N
A = [0] * N
Q = deque([0])
V[0] = True
while len(Q) > 0:
    r = Q.popleft()
    for nr in X[r]:
        if V[nr] == True:
            continue
        V[nr] = True
        P[nr] = P[r] + 1
        A[nr] = r + 1
        Q.append(nr)

for i in range(1, N):
    print(A[i])

Submission status: Wrong Answer

Solution code:
import collections
[n,m] = [int(i) for i in input().split()]
def BFS(s,G,num):
    ls = []
    check = [0] * num
    marker = [-1] * num
    check[0] = 1
    ls += G[s]
    for i in G[s]:
        marker[i] = s
    while(len(ls)):
        now = ls.pop(0)
        if check[now] == 1:
            continue
        else:
            #print(now)
            check[now] = 1
            ls += G[now]
            for i in G[now]:
                if marker[i] == -1:
                    marker[i] = now
    return marker
dic = collections.defaultdict(list)
for i in range(m):
    [a,b] = [int(i)-1 for i in input().split()]
    dic[a].append(b)
    dic[b].append(a)

ans = BFS(0,dic,n)

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

Submission status: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,M=acinput()


L=[[]for i in range(N+1)]
for i in range(M):
    tmp=acinput()
    L[tmp[0]].append(tmp[1])
    L[tmp[1]].append(tmp[0])
    
    
visited=[0]*(N+1)
queue=[1]

parent=[-1]*(N+1)
count=1
visited[1]=1
while True:
    
    try:
        q=queue.pop()
    except:
        break
    
    for sq in L[q]:
        if not visited[sq]:
            visited[sq]=1
            parent[sq]=q
        
            queue.append(sq)
            count+=1
    


if count!=N:
    print("No")
    sys.exit()

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