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 numpy as np

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

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

dist = [[] for i in range(10**5)]; counter = [1]
dist[0] = paths[1] #2
counter.extend(paths[1])
for j in dist[0]:
  for i in paths[j]: #134
    if not i in counter:
      dist[1].append(i) #34
      counter.append(i)

counter = sorted(counter)
for i in range(n):
  if not counter[i] == i+1:
    print('No')
    exit()
    
print("Yes")
for i in range(1,n):
  print(paths[i][0])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [[] for i in range(n + 1)]  #部屋毎にどの部屋とつながっているか

for i in range(m):  #m本の道をlの部屋に結び付け
    a, b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)

#print(l)  #
inf = float("inf")
dist = [inf] * (n + 1)#0番目は外界であって部屋ではないので使わない
dist[1] = 1  #１番目の部屋は外界との距離が１だと決まっている特別な部屋
#print(dist)  #

prev = [0] * (n + 1)#暫定の行先部屋番号

while any(i == inf for i in dist[1:]):#すべての部屋の距離が分かるまで続ける
    for i in range(len(l)):#部屋ごとに見ていく
        for j in l[i]:  #道の先の部屋番号
            if dist[i] > dist[j] : #道の先の部屋番号の外界までの距離が分かっていて、暫定の距離よりも近かったら
                dist[i] = dist[j] + 1  #その部屋の距離は道の先の部屋の距離＋１
                prev[i] = j
#        print(dist)#
#        print(prev)#

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = [[] for i 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)

ls = deque([0])
ans = [-1] * N
ans[0] = 0
while len(ls) > 0:
    v = ls.pop()

    for next_v in G[v]:
        if ans[next_v] != -1:
            continue
        ans[next_v] = v
        ls.append(next_v)

if -1 in ans:
    print("No")
else:
    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 = []
#print(l) #
ans = [0] * (n + 1)
def check(a, b):
#    print(a, b)#
#    print(ans[a], b)#
    if ans[a] == 0:
        return b
    elif ans[a] < b:
#        print(ans[a])#
        return ans[a]
    else:
#        print(b)#
        return b

for i in range(m):
    p1,p2 = list(map(int, input().split()))
#    print(i)#
    ans[p1] = check(p1,p2)
    ans[p2] = check(p2,p1)
#    print(ans)  #

if all(a > 0 for a in ans[2:]):
    print("Yes")
    for i in ans[2:]:
        print(i)
else:
    print("No")

Submission status: Wrong Answer

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

l = []
#print(l) #
ans = [0] * (n + 1)
def check(a, b):
#    print(a, b)#
#    print(ans[a], b)#
    if ans[a] == 0:
        return b
    elif ans[a] < b:
        print(ans[a])
        return ans[a]
    else:
        print(b)
        return b

for i in range(m):
    p1,p2 = list(map(int, input().split()))
#    print(i)#
    ans[p1] = check(p1,p2)
    ans[p2] = check(p2,p1)
#    print(ans)  #

if all(a > 0 for a in ans[2:]):
    print("Yes")
    for i in ans[2:]:
        print(i)
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
par = []
rank = []
def init(n):
    for i in range(n):
        par.append(i)
        rank.append(sys.maxsize)
    rank[0] = 0
 
def root(x):
    if par[x] == x:
        return x
    else:
        return root(par[x])
        
 
def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False
 
def unite(x,y):
    if par[x]==par[y] or rank[x] == rank[y]:
        return
    if(rank[x] < rank[y]):
        par[y] = x
        rank[y] = rank[x] + 1
    else:
        par[x] = y
        rank[x] = rank[y] + 1

 
n,m = map(int,input().split())
 
turo = [[] for i in range(n)]
q = deque()
his = []
 
for i in range(m):
    a,b = map(int,input().split())
    if b == 1:
        turo[b-1].append(a-1)
    else:
        turo[a-1].append(b-1)
 
init(n)
q.append(0)
his.append(0)
 
while len(q) > 0:
    #print(q)
    room = q.popleft()
    #print(room+1)
    for room2 in turo[room]:
        if room2 not in his:
            his.append(room2)
            q.append(room2)
        unite(room,room2)
#print(rank,his,turo)
if len(his) < n:
    print("No")
    exit()

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
par = []
rank = []
def init(n):
    for i in range(n):
        par.append(i)
        rank.append(sys.maxsize)
    rank[0] = 0
 
def root(x):
    if par[x] == x:
        return x
    else:
        return root(par[x])
        
 
def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False
 
def unite(x,y):
    if par[x]==par[y]:
        return
    if rank[x] != sys.maxsize and rank[x] == rank[y]:
        pass
    elif(rank[x] < rank[y]):
        par[y] = x
        rank[y] = rank[x] + 1
    else:
        par[x] = y
        rank[x] = rank[y] + 1

 
n,m = map(int,input().split())
 
turo = [[] for i in range(n)]
q = deque()
his = []
 
for i in range(m):
    a,b = map(int,input().split())
    if b == 1:
        turo[b-1].append(a-1)
    else:
        turo[a-1].append(b-1)
 
init(n)
q.append(0)
his.append(0)
 
while len(q) > 0:
    #print(q)
    room = q.popleft()
    #print(room+1)
    for room2 in turo[room]:
        if room2 not in his:
            his.append(room2)
            q.append(room2)
        unite(room,room2)
#print(rank,his,turo)
if len(his) < n:
    print("No")
    exit()

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

Submission status: Wrong Answer

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

d=deque()
d.append(1)
while d:
    v=d.popleft()
    for i in node[v]:
        if distance[i]!=-1:
            continue
        distance[i]=distance[v]+1
        d.append(i)
print('Yes')
for i in range(2,n+1):
    print(distance[i])

Submission status: Wrong Answer

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

d=deque()
d.append(0)
while d:
    v=d.popleft()
    for i in node[v]:
        if distance[i]!=-1:
            continue
        distance[i]=distance[v]+1
        d.append(i)
print('Yes')
for i in range(1,n):
    print(distance[i])

Submission status: Wrong Answer

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

d=deque()
d.append(0)
while d:
    v=d.popleft()
    for i in node[v]:
        if distance[i]!=-1:
            continue
        distance[i]=distance[v]+1
        d.append(i)
for i in range(1,n):
    print(distance[i])

Submission status: Wrong Answer

Solution code:
import sys
par = []
rank = []
def init(n):
    for i in range(n):
        par.append(i)
        rank.append(sys.maxsize)
    rank[0] = 0

def root(x):
    if par[x] == x:
        return x
    else:
        return root(par[x])
        

def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False

def unite(x,y):
    #print(par[x],par[y],rank[root(x)],rank[root(y)])
    if par[x]==par[y]:
        return
    if rank[x] != sys.maxsize and rank[x] == rank[y]:
        pass
    elif(rank[x] < rank[y]):
        par[y] = x
        rank[y] = rank[x] + 1
    else:
        par[x] = y
        rank[x] = rank[y] + 1
        #if rank[x]==rank[y]:
         #   rank[x] += 1
    #print(par,rank)

n,m = map(int,input().split())
ab = []
for i in range(m):
    a,b = map(int,input().split())
    if a > b:
        ab.append([b,a])
    else:
        ab.append([a,b])
ab.sort()
init(n)

for a,b in ab:
    unite(a-1,b-1)

for i in range(1,n):
    if (root(i) != 0):
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
import sys
par = []
rank = []
def init(n):
    for i in range(n):
        par.append(i)
        rank.append(sys.maxsize)
    rank[0] = 0

def root(x):
    if par[x] == x:
        return x
    else:
        return root(par[x])
        

def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False

def unite(x,y):
    #print(par[x],par[y],rank[root(x)],rank[root(y)])
    if par[x]==par[y]:
        return
    if (rank[x] < rank[y]):
        par[y] = x
        rank[y] = rank[x] + 1
    else:
        par[x] = y
        rank[x] = rank[y] + 1
        #if rank[x]==rank[y]:
         #   rank[x] += 1
    #print(par,rank)

n,m = map(int,input().split())
ab = []
for i in range(m):
    a,b = map(int,input().split())
    if a > b:
        ab.append([b,a])
    else:
        ab.append([a,b])
ab.sort()
init(n)

for a,b in ab:
    unite(a-1,b-1)

for i in range(1,n):
    if (root(i) != 0):
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
import sys
par = []
rank = []
def init(n):
    for i in range(n):
        par.append(i)
        rank.append(sys.maxsize)
    rank[0] = 0

def root(x):
    if par[x] == x:
        return x
    else:
        return root(par[x])
        

def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False

def unite(x,y):
    #print(par[x],par[y],rank[root(x)],rank[root(y)])
    if par[x]==par[y]:
        return
    if (rank[x] < rank[y]):
        par[y] = x
        rank[y] = rank[x] + 1
    else:
        par[x] = y
        rank[x] = rank[y] + 1
        #if rank[x]==rank[y]:
         #   rank[x] += 1
    #print(par,rank)

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
init(n)
#print(par,rank)
for a,b in ab:
    unite(a-1,b-1)

for i in range(1,n):
    if (root(i) != 0):
        print("No")
        exit()
print("Yes")
for i in range(1,n):
    print(par[i]+1)

Submission status: Wrong Answer

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

room=[[i+1,None] for i in range(n)] 
room[0][1]="Yes"

print(room)

check_list=[1]
next_list=[]
def check(x):
    for i in corridor:
        if i[0]==x:
            if not room[i[1]-1][1]:
                room[i[1]-1][1]=i[0]
                next_list.append(i[1])
        if i[1]==x:
            if not room[i[0]-1][1]:
                room[i[0]-1][1]=i[1]
                next_list.append(i[0])

while check_list:
    for i in check_list:
        check(i)
    check_list.clear()
    check_list=next_list[:]
    next_list.clear()

for i in room:
    print(i[1])

Submission status: Wrong Answer

Solution code:
# import sys
# input = sys.stdin.readline
import itertools


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n, m = input_list()
    rooms = []
    for _ in range(m):
        rooms.append(input_list())
    prev = [0]*n
    to_list = [[] for _ in range(n)]
    for a, b in rooms:
        to_list[a-1].append(b-1)
        to_list[b-1].append(a-1)
    marked = {0}
    que = [0]
    for i in que:
        print(to_list[i])
        for j in to_list[i]:
            if j in marked:
                continue
            que.append(j)
            marked.add(j)
            prev[j] = i+1

    print('Yes')
    print(*prev[1:], sep='\n')


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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = list(map(int,input().split()))
graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = list(map(int,input().split()))
    graph[a].append(b)
    graph[b].append(a)
# print(graph)
dist = [-1]*(n+1)
dist[0] = 0
dist[1] = 0
d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i]!=-1:
            continue
        dist[i] = dist[v] +1
        d.append(i)
    # print(dist)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
table = []
for i in range(N):
    table.append([])
for i in range(M):
    Ai, Bi = map(int, input().split())
    table[Ai - 1].append(Bi - 1)
    table[Bi - 1].append(Ai - 1)

cost = [1000000] * N
queue = [0]
counter = 0
cost[0] = 0
answer = [-1] * N
answer[0] = 0
while counter < len(queue):
    current = queue[counter]
    counter += 1

    for n in table[current]:
        if cost[current] + 1 < cost[n]:
            cost[n] = cost[current] + 1
            answer[n] = current
            queue.append(n)
for a in map(lambda x: x + 1, answer[1:]):
    print(a)

Submission status: Wrong Answer

Solution code:
print("No")

Submission status: Wrong Answer

Solution code:
#import time
from itertools import dropwhile, takewhile
def main():
    N, M = list(map(int, input().split()))
    lis = [list(map(int, input().split())) for _ in range(M)]
    #print(lis)
    edge = [[] for _ in range(N+1)]
    #print(edge)
    for a,b in lis:
        edge[a].append(b)
        edge[b].append(a)
        #print(edge)
    ans = [0] * (N+1)
    visited = {0}
    stack = [1]
    for i in stack:
        for j in edge[i]:
            if j in visited:
                continue
            stack.append(j)
            #print(stack)
            visited.add(j)
            #print(visited)
            ans[j]=i
    print("Yes")
    for k in ans[2:]:
        print(k)


if __name__ == '__main__':
    #start = time.time()
    print(main())
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Wrong Answer

Solution code:
import collections
import networkx as nx

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

L = [1]
Q = collections.deque(L)
G = nx.Graph()

for i in range (1, N+1):
    G.add_node(i)

for i in range (0, M):
    A, B = map(int, input().split())
    G.add_edge(A, B)

Lamps = [0]*N

s = Q.popleft()
V = list(G.adj[s])
for j in range (0, len(V)):
    Lamps[V[j]-1] = 1
    Q.append(V[j])

while Q:
    s = Q.popleft()
    V = list(G.adj[s])
    for j in range (0, len(V)):
        if Lamps[V[j]-1] == 0:
            Lamps[V[j]-1] = s

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

Submission status: Wrong Answer

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

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

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

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v]+1
        d.append(i)
ans = dist[1:]
if -1 not in ans:
    print("Yes")
    for i in range(1,len(ans)):
        print(ans[i])
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
nextroom = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  nextroom[A-1].append(B-1)
  nextroom[B-1].append(A-1)

sgn = [-1 for _ in range(N)]
sgn[0] = 0

depth = [float('inf') for _ in range(N)]
depth[0] = 0

now = [0]
nextvisit = []
for j in range(1, M):
  for n in now:
    for i in nextroom[n]: 
      if depth[i] > j:
        nextvisit.append(i)
        sgn[i] = n
        depth[i] = j
  now = [] + nextvisit
  nextvisit = []

if -1 in sgn:
  print('No')
else:
  print('Yes')
  for k in range(1, len(sgn)):
    print(sgn[k]+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
r=[0]*(n-1)
rr=[0]*(n-1)
ab=[]
lpath=1
for ii in range(m):
  abii=list(map(int,input().split()))
  abii.sort()
  if abii[0]==1:
    kk=abii[1]-1-1
    r[kk]=lpath
    rr[kk]=1
  else:
    ab.append(abii)
"""
print(r)
print(rr)
print(ab)
"""
for ll in range(n):
  lpath+=1
  lenab0=len(ab)
  if lenab0==0:
    break
  for jj in range(lenab0):
    jjj=(lenab0-1)-jj
    abj0=ab[jjj][0]
    abj02=abj0-2
    abj1=ab[jjj][1]
    abj12=abj1-2
    if r[abj02]==0 and r[abj12]==0:
      pass
    elif r[abj02]>0 and r[abj02]<lpath and r[abj12]>0 and r[abj12]<lpath:
      del ab[jjj]
    else:
      #print(ab[jjj])
      if r[abj02]==0 and r[abj12]<lpath:
        iii=abj1
        kk=abj02
      elif r[abj12]==0 and r[abj02]<lpath:
        iii=abj0
        kk=abj12
      r[kk]=lpath
      rr[kk]=iii
      del ab[jjj]
  """
  print(r)
  print(rr)
  print(ab)
  """
  if lenab0==len(ab):
    break
#import numpy as np
if min(r)>0 and min(rr)>0:
  print("Yes")
  for ii in range(len(rr)):
    print(rr[ii])
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
r=[0]*(n-1)
rr=[0]*(n-1)
ab=[]
lpath=1
for ii in range(m):
  abii=list(map(int,input().split()))
  abii.sort()
  if abii[0]==1:
    kk=abii[1]-1-1
    r[kk]=lpath
    rr[kk]=1
  else:
    ab.append(abii)
"""
print(r)
print(rr)
print(ab)
"""
for ll in range(n):
  lpath+=1
  lenab0=len(ab)
  if lenab0==0:
    break
  for jj in range(lenab0):
    jjj=(lenab0-1)-jj
    abj0=ab[jjj][0]
    abj02=abj0-2
    abj1=ab[jjj][1]
    abj12=abj1-2
    if r[abj02]==0 and r[abj12]==0:
      pass
    elif r[abj02]>0 and r[abj02]<lpath and r[abj12]>0 and r[abj12]<lpath:
      del ab[jjj]
    else:
      #print(ab[jjj])
      if r[abj02]==0 and r[abj12]<lpath:
        iii=abj1
        kk=abj02
      elif r[abj12]==0 and r[abj02]<lpath:
        iii=abj0
        kk=abj12
      r[kk]=lpath
      rr[kk]=iii
      del ab[jjj]
  """
  print(r)
  print(rr)
  print(ab)
  """
#import numpy as np
if min(r)>0 and min(rr)>0:
  print("Yes")
  for ii in range(len(rr)):
    print(rr[ii])
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
r=[0]*(n-1)
rr=[0]*(n-1)
ab=[]
lpath=1
for ii in range(m):
  abii=list(map(int,input().split()))
  abii.sort()
  #print(abii)
  if abii[0]==1:
    kk=abii[1]-1-1
    r[kk]=lpath
    rr[kk]=1
  else:
    ab.append(abii)
"""
print(r)
print(rr)
print(ab)
"""
for ll in range(n):
  lpath+=1
  lenab0=len(ab)
  if lenab0==0:
    break
  for jj in range(lenab0):
    jjj=(lenab0-1)-jj
    if r[ab[jjj][0]-1-1]==0 and r[ab[jjj][1]-1-1]==0:
      pass
    elif r[ab[jjj][0]-1-1]>0 and r[ab[jjj][0]-1-1]<lpath and\
    	r[ab[jjj][1]-1-1]>0 and r[ab[jjj][1]-1-1]<lpath:
      pass
      del ab[jjj]
    else:
      #print(ab[jjj])
      if r[ab[jjj][0]-1-1]==0 and r[ab[jjj][1]-1-1]<lpath:
        iii=ab[jjj][1]
        kk=ab[jjj][0]-1-1
      elif r[ab[jjj][1]-1-1]==0 and r[ab[jjj][0]-1-1]<lpath:
        iii=ab[jjj][0]
        kk=ab[jjj][1]-1-1
      r[kk]=lpath
      rr[kk]=iii
      del ab[jjj]
  """
  print(r)
  print(rr)
  print(ab)
  """
#import numpy as np
if min(r)>0 and min(rr)>0:
  print("Yes")
  for ii in range(len(rr)):
    print(rr[ii])
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
r=[0]*(n-1)
rr=[0]*(n-1)
ab=[]
lpath=1
for ii in range(m):
  abii=list(map(int,input().split()))
  abii.sort()
  #print(abii)
  if abii[0]==1:
    kk=abii[1]-1-1
    r[kk]=lpath
    rr[kk]=1
  else:
    ab.append(abii)
"""
print(r)
print(rr)
print(ab)
"""
for ll in range(n):
  lpath+=1
  lenab0=len(ab)
  if lenab0==0:
    break
  for jj in range(lenab0):
    jjj=(lenab0-1)-jj
    if r[ab[jjj][0]-1-1]==0 and r[ab[jjj][1]-1-1]==0:
      pass
    elif r[ab[jjj][0]-1-1]>0 and r[ab[jjj][1]-1-1]>0:
      pass
      del ab[jjj]
    else:
      #print(ab[jjj])
      if r[ab[jjj][0]-1-1]==0:
        iii=ab[jjj][1]
        kk=ab[jjj][0]-1-1
      elif r[ab[jjj][1]-1-1]==0:
        iii=ab[jjj][0]
        kk=ab[jjj][1]-1-1
      r[kk]=lpath
      rr[kk]=iii
      del ab[jjj]
  """
  print(r)
  print(rr)
  print(ab)
  """
#import numpy as np
if min(r)>0 and min(rr)>0:
  print("Yes")
  for ii in range(len(rr)):
    print(rr[ii])
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

n,m = I()
g = [[] for _ in range(n)]
for i in range(m):
    a,b = I()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = deque([0])
d = [-1]*n
d[0] = 0
while q:
    v = q.pop()
    for i in g[v]:
        if d[i] != -1:
            continue
        d[i] = v
        q.append(i)
if -1 in d:
    print("No")
else:
    print("Yes")
    for i in d[1:]:
        print(i+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(graph, visited, ss):
  queue = deque([ss])
  visited[ss] = 0
  ans = [0]*n
  while queue:
    s = queue.popleft()
    for new_s in graph[s] :
      if visited[new_s] == -1:
        #　移動回数の計算
        visited[new_s] = visited[s] + 1
        queue.append(new_s)
        ans[new_s] = s
  return ans

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

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

visited = [-1]*n
ans = bfs(graph, visited, 0)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(graph, visited, ss, g):
  queue = deque([ss])
  visited[ss] = 0
  while queue:
    s = queue.popleft()
    #　返り値に関する条件
    if visited[g] != -1 :
        return visited
    for new_s in range(n) :
      if graph[new_s][s] == 1 and visited[new_s] == -1:
        #　移動回数の計算
        visited[new_s] = visited[s] + 1
        queue.append(new_s)
  return visited

n,m = map(int,input().split())
graph = [[0 for i in range(n)] for j in range(n)]

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

for g in range(1,n) :
    visited = [-1]*n
    bfs(graph, visited, 0, g)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(graph, visited, ss, g):
  queue = deque([ss])
  visited[ss] = 0
  while queue:
    s = queue.popleft()
    #　返り値に関する条件
    if visited[g] != -1 :
        return visited
    for new_s in range(n) :
      if graph[new_s][s] == 1 and visited[new_s] == -1:
        #　移動回数の計算
        visited[new_s] = visited[s] + 1
        queue.append(new_s)
  return visited

n,m = map(int,input().split())
graph = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    a,b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
 
d = [0]*n
for g in range(1,n) :
    visited = [-1]*n
    d[g] = bfs(graph, visited, 0, g)[g]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
edges = defaultdict(list)
ans = [0]*(N+1)
num = 1
currentdepth = {1}
nextdepth = set()
for _ in range(M):
  a, b = map(int, input().split())
  edges[a].append(b)
  edges[b].append(a)
while num < N:
  for ver in currentdepth:
    for nextver in edges[ver]:
      if ans[nextver]==0:
        nextdepth.add(nextver)
        ans[nextver] = ver
  num = num + len(nextdepth)
  if num == N:
    break
  currentdepth = nextdepth
  nextdepth = set()
print('Yes')
print(*(ans[2:]),sep='\n')

Submission status: Wrong Answer

Solution code:
def main():
    n, m = (int(i) for i in input().split())
    graph = { i: [] for i in range(1, n+1) }

    for i in range(m):
        src, dst = (int(i) for i in input().split())
        graph[src].append(dst)
        graph[dst].append(src)

    def bfs():
        st = [1] 
        visited = set([1])
        pptr = { }

        while st:
            room = st.pop()
            for dest_room in graph[room]:
                if dest_room in visited:
                    continue
                st.append(dest_room)
                visited.add(dest_room)
                pptr[dest_room] = room

        return pptr

    pptr = bfs()
    if len(pptr) != n-1:
        print('No')

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

main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m = (int(i) for i in input().split())
    graph = { i: [] for i in range(1, n+1) }

    for i in range(m):
        src, dst = (int(i) for i in input().split())
        graph[src].append(dst)
        graph[dst].append(src)

    def bfs():
        st = [1] 
        visited = set([1])
        pptr = { }

        while st:
            room = st.pop()
            for dest_room in graph[room]:
                if dest_room in visited:
                    continue
                st.append(dest_room)
                visited.add(dest_room)
                pptr[dest_room] = room

        return pptr

    pptr = bfs()
    print(pptr)
    if len(pptr) != n-1:
        print('No')

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


main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
vi=[0 for _ in range(n+1)]
 
for i in range (m):
        a,b=map(int,input().split())
        l[a].append(b)
        l[b].append(a)
        
st = deque([1])
f = set([1])

while st:
    x = st.popleft()
    for k in l[x]:
        if k not in f:
            f.add(k)
            st.appendleft(k)
            vi[k] = x
            
print('Yes')
for i in range(2,n+1):
    print(vi[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
l = [[0] for _ in range(n+1)]
vi = [0]*(n+1)

for _ in range(m):
    a,b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)
d = deque([1])
s = set([1])

while d:
    x = d.popleft()
    for k in l[x]:
        if k not in s:
            s.add(k)
            d.appendleft(k)
            vi[k] = x
print('Yes')
for i in vi[2:]:
    print(i)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

INF = 1000000
N, M = map(int, input().split())
d = [INF]*(N+1)
d[1] = 0
prev = [0]*(N+1)
G = {}
for i in range(M):
  a, b = map(int, input().split())
  try:
    G[a].append(b)
  except:
    G[a] = [b]
  try:
    G[b].append(a)
  except:
    G[b] = [a]

que = []
heappush(que, (0, 1))
    
while True:
  if len(que) == 0:
    break
  p = heappop(que)
  v = p[1]
  
  for u in G[v]:
    if (d[u] > d[v] + 1):
      d[u] = d[v] + 1
      heappush(que, (d[u], u))
      prev[u] = v
      
if 0 in prev[2:]:print('No')
else:
  for i in range(2, N+1):
    print(prev[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
vi=[0 for _ in range(n+1)]
vi[1]=-1

for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=deque([1])
e=set()

def bfs(x):
  if x not in e:
    e.add(x)
    for k in l[x]:
      if k not in e:
        st.append(k)
        vi[k]=x              
  return
while st:
  
  bfs(st.popleft())
  
print("Yes")
for m in vi[2:]:
  print(m)

Submission status: Wrong Answer

Solution code:
# -*- codinf: utf-8 -*-
from collections import deque

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

for _ in range(M):
  a, b = map(int, input().split())
  route[a].append(b)
  route[b].append(a)
  
q = deque([1]) # 頂点を設定して初期化
pre = [None] * (N+1) # 頂点までの最短に進む時の次の頂点のリスト
pre[1] = 0 # 頂点は0
depth = [None] * (N+1) # 頂点からの深さ(最短距離)のリスト
depth[1] = 0 # 頂点の距離は0
while len(q) > 0:
  x = q.popleft()
  for r in route[x]:
    if pre[r] is None:
      depth[r] = depth[x] + 1
      pre[r] = x
      q.append(r)

print("YES")
for i in range(2, len(pre)):
  print(pre[i])

Submission status: Wrong Answer

Solution code:
# -*- codinf: utf-8 -*-
from collections import deque

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

for _ in range(M):
  a, b = map(int, input().split())
  route[a].append(b)
  route[b].append(a)
  
q = deque([1]) # 頂点を設定して初期化
depth = [None] * (N+1) # 頂点からの深さ(最短距離)のリスト
depth[1] = 0 # 頂点の距離は0
while len(q) > 0:
  x = q.popleft()
  for r in route[x]:
    if depth[r] is None:
      depth[r] = depth[x] + 1
      q.append(r)

print("YES")
for i in range(2, len(depth)):
  print(depth[i])

Submission status: Wrong Answer

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

(n, m), g, s = map(int, input().split()), defaultdict(list), []
for i in range(m): a, b = map(int, input().split()); g[a].append(b); g[b].append(a)
def solve(i):
    q = deque([int(i)])
    while q:
        x = q.popleft()
        for a in g[x]:
            if a == 1: return x
            q.append(a)
    print('No'); exit()

for i in range(2, n + 1): s.append(solve(i))
print('Yes')
for i in s: print(i)