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:
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
res=[0]*(n+1)
abr =[[0,0] for i in range(m)]

for i in range(m):
    if ab[i][0] <ab[i][1]:
        abr[i][0]=ab[i][0]
        abr[i][1]=ab[i][1]
    else:
        abr[i][0]=ab[i][1]
        abr[i][1]=ab[i][0]

abrs = sorted(abr)
ab = abrs

for i in range(m):
    if ab[i][0]==1:
        res[ab[i][1]]=1
    elif ab[i][1] ==1:
        res[ab[i][0]]=1
while min(res[1:]) ==0:
    for j in range(m):
        if res[ab[j][0]] !=0:
            if res[ab[j][1]] ==0:
                res[ab[j][1]] =ab[j][0]
                print(j,res)
        elif res[ab[j][1]] != 0:
            if res[ab[j][0]] ==0:
                res[ab[j][0]] =ab[j][1]
                print(j,res)
print("Yes")
for k in range(2,n+1):
    print(res[k])

Submission status: Wrong Answer

Solution code:
import queue

def main():
  N, M = map(int, input().split())
  routes = []
  for m in range(M):
    n1, n2 = map(int, input().split())
    routes.append([n1, n2])

  dic = {}
  for route in routes:
    n1 = route[0]
    n2 = route[1]

    dic.setdefault("{}".format(n1), []).append("{}".format(n2))
    dic.setdefault("{}".format(n2), []).append("{}".format(n1))

  q = queue.Queue()
  for i in dic["1"]:
        q.put(i)
        q.put("1")

  michishirube = {}

  while not q.empty():
      
    dist = q.get()
    parent = q.get()
    if dist in michishirube:
      continue
    if dist == "1":
      continue
    
    michishirube[dist] = parent

    for i in dic[dist]:
      q.put(i)
      q.put(dist)

  if not len(michishirube) == N-1:
    print("No")
    return
  
  michishirube_sorted = dict(sorted(michishirube.items(), key=lambda x:x[0]))
  print("Yes")
  for v in michishirube_sorted.values():
    print(v)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
r = [-1]*(n+1)
michi = [-1]*(n+1)
r[1] = 0
ab = []
for i in range(m):
    a,b = map(int,input().split())
    if a > b:
        a,b = b,a
    ab.append([a,b])
ab.sort()
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]

    if r[a] >= 0:
        if r[b] == -1:
            r[b] = r[a] + 1
            michi[b] = a
        else:
            if r[b] >= r[a]+1:
                r[b] = r[a] + 1
                michi[b] = a
    elif r[b] >= 0:
        r[a] = r[b] + 1
        michi[a] = b
for i in range(1,n+1):
    if r[i] == -1:
        print('No')
        exit()
else:
    print('Yes')
    for i in range(2,n+1):
        print(michi[i])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
d = [[] for i in range(n)]
l = [float('inf')] * n
for i1, i2 in L:
    d[i1 - 1].append(i2)
    d[i2 - 1].append(i1)
l[0] = 0
for i in range(len(d)):
    for j in range(len(d[i])):
        l[d[i][j] - 1] = min(l[d[i][j] - 1], l[i] + 1)
print('Yes')
for i in range(1, len(l)):
    if l[i] == 1:
        print(1)
    else:
       print(l.index(l[i] - 1) + 1)

Submission status: Wrong Answer

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

road = {k:[] for k in range(1,n+1)}
for _ in range(m):
  a,b = map(int,input().split())
  road[a].append(b)
  road[b].append(a)


next_visited = [1]
visited = {1:None}
temp_next = []

visit_num = {}
count = 0

while True:
  print(next_visited)
  temp_next = []
  for room in next_visited:
    ava_room = road[room]
    for r in ava_room:
      try:
        visited[r]
      except:
        visit_num[r] = room
        temp_next.append(r)
        visited[r] = None
        
  if temp_next == []:
    break
  next_visited = temp_next

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

else:
  print('Yes')
  for v in sorted(visit_num.items()):
    print(v[1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
chizu = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    chizu[a-1].append(b-1)
    chizu[b-1].append(a-1)
inf = 10**10
dep = [inf]*n
dep[0] = 0
prev = [-1]*n
former = []

for i in range(n):
    for j in chizu[i]:
        if dep[i]+1 < dep[j]:
            prev[j] = i+1
            dep[j] = dep[i]+1
        
    
print('Yes')
for i in range(1,n):
    print(prev[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

grid = {}
for i in range(M):
    a, b = map(int, input().split())
    if a not in grid or b not in grid:
        if a not in grid:
            grid[a] = set()
            grid[a].add(b)
        if b not in grid:
            grid[b] = set()
            grid[b].add(a)
    else:
        if b in grid:
            grid[b].add(a)
        if a in grid:
            grid[a].add(b)

def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(list(graph[vertex]) - visited)
    return visited

def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

def shortest_path(graph, start, goal):
    try:
        return next(bfs_paths(graph, start, goal))
    except StopIteration:
        return None

ans = []
flag = True
for i in range(2, N+1):
    path = shortest_path(grid, i, 1)
    if path:
        ans.append(path[1])
    else:
        flag = False

if flag:
    print("Yes")
    for i in ans:
        print(i)
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
ans = [0]*(N+1)
AB_ = []

def update():
  for AB in AB_:
    if AB[0] == 1:
      ans[AB[1]] = 1
    elif ans[AB[0]] == 1 and ans[AB[1]]==1:
      continue
    elif ans[AB[0]] == 1:
      ans[AB[1]] = AB[0]
    elif ans[AB[1]] == 1:
      ans[AB[0]] = AB[1]
    elif ans[AB[0]] != 1 and ans[AB[1]] != 1:
      ans[AB[0]] = AB[1]
      ans[AB[1]] = AB[0]

for _ in range(M):
  AB = sorted(list(map(int, input().split())))
  AB_.append(AB)
  if AB[0] == 1:
    ans[AB[1]] = 1
  elif ans[AB[0]] == 1 and ans[AB[1]]==1:
    continue
  elif ans[AB[0]] == 1:
    ans[AB[1]] = AB[0]
  elif ans[AB[1]] == 1:
    ans[AB[0]] = AB[1]
  elif ans[AB[0]] != 1 and ans[AB[1]] != 1:
    ans[AB[0]] = AB[1]
    ans[AB[1]] = AB[0]

for _ in range(10*3):
  update()
  
if 0 in ans[2:]:
  print("No")
else:
  print("Yes")
for i in ans[2:]:
  print(i)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G =[[]for i in range(N)]
for _ in range(M):
    A,B = map(int,input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
print(G)
if len(G[0])==0:
    print('No')
else:
    print('Yes')
    for i in range(1,N):
        print(min(G[i])+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
path_dict = {}
memo_list = [0] * (n + 1)
for i in range(m):
    A[i], B[i] = map(int, input().split())
    if not A[i] in path_dict.keys():
        path_dict[A[i]] = [B[i]]
    else:
        path_dict[A[i]].append(B[i])
    if not B[i] in path_dict.keys():
        path_dict[B[i]] = [A[i]]
    else:
        path_dict[B[i]].append(A[i])

for i in range(1, n + 1):
    for j in path_dict[i]:
        if memo_list[j] == 1:
            continue
        memo_list[j] = i

print("Yes")
for ans in memo_list[2:]:
    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,m = map(int,input().split())
ab = []
for _ in range(m):
    a,b = map(int,stdin.readline().split())
    ab.append([a,b])
whole = [1]
ans = [0 for i in range(n)]
while len(whole) < n:
    part = []
    for i in whole:
        for j in ab:
            if j[0] == i:
                if (j[1] not in whole) and (j[1] not in part):
                    part.append(j[1])
                    ans[j[1]-1] = i
            if j[1] == i:
                if (j[0] not in whole) and (j[0] not in part):
                    part.append(j[0])
                    ans[j[0]-1] = i
    for i in part:
        whole.append(i)
print("yes")
for i in range(1,n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
g={}
for _ in range(M):
    A, B = map(int, input().split())
    A-=1
    B-=1
    if A not in g:
        g[A]=set()
    if B not in g:
        g[B]=set()
    g[A].add(B)
    g[B].add(A)

distance=[None for i in range(N)]
visited = [False for i in range(N)]
predecessor = [ None for i in range(N)]

distance[0]=0
num = 0

while (num < N):
    mind=10**6
    cur = None
    for i in range(N):
        if distance[i]!=None and distance[i]<mind and not visited[i]:
            cur = i
            mind=distance[i]
    if cur == None:
        print("NO")
        exit()
    visited[cur]=True
    if cur in g:
        for item in g[cur]:
            if not visited[item]:
                if distance[item] is None or distance[item] > distance[cur]+1:
                    distance[item]=distance[cur]+1
                    predecessor[item]=cur
    num+=1

#print(predecessor)
print("YES")
for i in range(1, N):
    print(predecessor[i]+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
ans=[1]*(n+1)
w=[m]*(n+1)
w[1]=0
for i in range(m):
  a=l[i][0]
  b=l[i][1]
  if w[a]>w[b]+1:
    w[a]=w[b]+1
    ans[a]=b
  elif w[b]>w[a]+1:
    w[b]=w[a]+1
    ans[b]=a
for i in range(m):
  a=l[i][0]
  b=l[i][1]
  if w[a]>w[b]+1:
    w[a]=w[b]+1
    ans[a]=b
  elif w[b]>w[a]+1:
    w[b]=w[a]+1
    ans[b]=a
for i in range(m):
  a=l[i][0]
  b=l[i][1]
  if w[a]>w[b]+1:
    w[a]=w[b]+1
    ans[a]=b
  elif w[b]>w[a]+1:
    w[b]=w[a]+1
    ans[b]=a
print('Yes')
for i in range(2,n+1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)

INF = 10**10


def search(table, visit):
    d = deque()
    visit[1] = 0
    for x in table[1]:
        visit[x] = 1
        d.append(x)
    while(len(d) > 0):
        next = d.popleft()
        for x in table[next]:
            if visit[x] != INF:
                continue
            visit[x] = visit[next]+1
            d.append(x)


def main(input, print):
    n, m = map(int, input().split())
    table = [[] for _ in range(n+1)]
    visit = [INF]*(n+1)
    for i in range(m):
        a, b = map(int, input().split())
        table[a].append(b)
        table[b].append(a)
    search(table, visit)
    is_ok = True
    for i in range(2, n+1):
        if visit[i] == INF:
            is_ok = False
            break
    if is_ok:
        print('Yes')
        for i in range(2, n+1):
            print(visit[i])
    else:
        print('No')


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
import sys
import networkx as nx
n,m=map(int,input().split())
g = nx.Graph()
sys.stdin.readlines()

Submission status: Wrong Answer

Solution code:
import math
import queue
def dijkstra(n, w):
    ans=[math.inf]*n
    done=[]
    done.append(1)
    q=queue.Queue()
    for i in range(n+1):
        if w[1][i]==1:
            q.put(i)
            ans[i-1]=1
            done.append(i)
    while not q.empty():
        now=q.get()
        
        for i in range(n+1):
            if w[now][i]==1 and (i not in done):
                print(now,i,w[now][i])
                q.put(i)
                done.append(i)
                ans[i-1]=now
    return ans


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

for i in range(m):
    s = list(map(int, input().split()))
    mapping[s[0]][s[1]]=1
    mapping[s[1]][s[0]] = 1

ans=dijkstra(n,mapping)
if not math.inf in ans[1:]:
    print('Yes')
    for i in ans[1:]:
        print(i)
else:
    print('No')

Submission status: Wrong Answer

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

a, b = [], []
result = [-1] * n
way = dict()
result[0] = 0

for i in range(m):
    aa, bb = map(int, input().split())
    # aa, bb = 1, 2
    a.append(aa)
    b.append(bb)
    way[aa - 1] = way.get(aa - 1, []) + [bb - 1]
    way[bb - 1] = way.get(bb - 1, []) + [aa - 1]

visited = False
waits = [0]

while len(waits) > 0:
    current = waits.pop()
    for w in way.get(current, []):
        if result[w] == -1:
            result[w] = current + 1
            waits.append(w)

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
arr = [list(map(int,input().split())) for i in range(m)]
costheya = {i:[9999999,0] for i in range(2,n+1)}
arr.sort()

for turo in arr:
    left = turo[0]
    right = turo[1]
    if left == 1:
        costheya[right] = [1,1]
    elif right == 1:
        costheya[left] = [1,1]
    else:
        if costheya[left][0] > costheya[right][0]+1:
            costheya[left] = [costheya[right][0]+1,right]
        if costheya[right][0] > costheya[left][0]+1:
            costheya[right] = [costheya[left][0]+1,left]
print('Yes')
for i in costheya.values():
    print(i[1])

Submission status: Wrong Answer

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

#print(room_list)

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

    #print(room_list)

#回数管理
room_move_count_list = [999999] * N
room_move_count_list[0] = 0
#移動先管理
rome_move_to_list = [999999] * N
rome_move_to_list[0] = 0

for i, room in enumerate(room_list):
    for miti in room: 
        #print(miti)
        if room_move_count_list[miti - 1] > room_move_count_list[i] + 1:
            #print(room_move_count_list[miti - 1])
            room_move_count_list[miti - 1] = room_move_count_list[i] + 1
            rome_move_to_list[miti - 1] = i + 1

if max(room_move_count_list) == 999999:
    print('No')

else:
    print('Yes')
    for room in rome_move_to_list[1:]:
        print(room)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, M = iim()
    it = map(int, sys.stdin.read().split())

    d1 = defaultdict(list)

    for i, j in zip(it, it):
        d1[i].append(j)
        d1[j].append(i)

    ans = [0] * (N+1)
    dq = [1]
    visited = set([1])

    updated = True
    while updated:
        updated = False
        for i in dq:
            dq2 = []
            for j in d1[i]:
                if j in visited:
                    continue
                dq2.append(j)
                ans[j] = i
                updated = True
            visited.update(dq2)
        dq = dq2

    if len(visited) == N:
        print("Yes", *ans[2:], sep="\n")
    else:
        print("No")






if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

tree=[[0] for _ in range(N)]

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

dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
print("Yes")
for j in range(1,N):
    print(dist[j])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G =[[]for i in range(N)]
for _ in range(M):
    A,B = map(int,input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
print(G)
if len(G[0])==0:
    print('No')
else:
    print('Yee')
    for i in range(1,N):
        print(min(G[i])+1)

Submission status: Wrong Answer

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

dct = {}
for _ in range(M):
    a, b = map(int,input().split())
    if not a in dct:
        dct[a] = set()
    if not b in dct:
        dct[b] = set()
    dct[a].add(b)
    dct[b].add(a)

#print(dct)
answers = [0]*(N+1)

stack = [1]
lst = []
while len(stack):
    s = stack.pop()
    lst.append(s)
    #print(dct[s])
    for i in dct[s]:
        if i in lst:
            continue
        if i in stack:
            continue
        stack.append(i)
        answers[i] = s

if answers.count(0) != 2:
    print("No")
else:
    print("Yes")
    for ans in answers[2:]:
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10000000)
N, M = map(int, input().split())
class tree():
    def __init__(self):
        self.num = 0
        self.flag = 0
        self.step = -1
        self.leaf = []

li = [tree() for i in range(N)]
def saiki(que, step):
    pop = que.pop()
    li[pop].flag = 2


    for i in range(len(li[pop].leaf)):
        if li[li[pop].leaf[i]].flag == 0:
            que.append(li[pop].leaf[i])
            li[li[pop].leaf[i]].flag = 1
            if li[li[pop].leaf[i]].step != -1:
                if li[li[pop].leaf[i]].step > li[pop].step + 1:
                    li[li[pop].leaf[i]].step = li[pop].step + 1
                    li[li[pop].leaf[i]].num = pop
            else:
                li[li[pop].leaf[i]].step = li[pop].step + 1
                li[li[pop].leaf[i]].num = pop


    #print(que)
    if len(que) != 0:
        saiki(que, li[pop].step)
for i in range(M):
    A, B = map(int, input().split())
    li[A-1].leaf.append(B-1)
    li[B-1].leaf.append(A-1)

que = deque()
que.append(0)
li[0].step = 0
saiki(que, 0)
flag = 1
for i in range(len(li)):
    if li[i].flag == 0:
        flag = 0
        break
if flag == 0:
    print("No")
else:
    print("Yes")
for i in range(1, len(li)):
    print(li[i].num+1)

Submission status: Wrong Answer

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

C = []

ans = [0]*(N-1)
flag = [False]*N
flag[0] = True

check = [False]*N

for i in range(M):
    c = list(map(int, input().split()))
    check[c[0]-1] = True
    check[c[1]-1] = True
    if c[0] == 1:
        ans[c[1]-2] = 1
        flag[c[1]-1] = True
    if c[1] == 1:
        ans[c[0]-2] = 1
        flag[c[0]-1] = True
    C.append(c)

if all(check):

    while True:
        
        if all(flag):
            break
        for i in range(N):
            if flag[i]:
                continue
            now = i + 1
            for path in C:
                if path[0] == now:
                    if flag[path[1]-1] == True:
                        ans[now-2] = path[1]
                        flag[path[0]-1] = True
                        break
                    else:
                        pass
                if path[1] == now:
                    if flag[path[0]-1] == True:
                        ans[now-2] = path[0]
                        flag[path[1]-1] = True
                        break
                    else:
                        pass

    print('Yes')
    for i in ans:
        print(i)

else:
    print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
ans=[1]*(n+1)
w=[m]*(n+1)
w[1]=0
for i in range(m):
  a=l[i][0]
  b=l[i][1]
  if w[a]>w[b]+1:
    w[a]=w[b]+1
    ans[a]=b
  elif w[b]>w[a]+1:
    w[b]=w[a]+1
    ans[b]=a
for i in range(m):
  a=l[i][0]
  b=l[i][1]
  if w[a]>w[b]+1:
    w[a]=w[b]+1
    ans[a]=b
  elif w[b]>w[a]+1:
    w[b]=w[a]+1
    ans[b]=a
print('Yes')
for i in range(2,n+1):
  print(ans[i])

Submission status: Wrong Answer

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

# adj_table = [[0] * N for _ in range(N)]
start_nodes = []

# 隣の部屋の辞書
node2nb_dict = {i + 1: [] for i in range(N)}

for _ in range(M):  # 2 * 10** 5
    a, b = list(map(int, input().split()))
    # adj_table[a][b] = 1
    # adj_table[b][a] = 1
    node2nb_dict[a].append(b)
    node2nb_dict[b].append(a)

    if a == 1 or b == 1:
        # 1の部屋と隣接する部屋のリスト
        start_nodes.append(max(a, b))

# 幅優先でいく
route_dict = {}
done_set = {1}


def f(next_targets, node_a):
    w_next_targets = {}
    for node in next_targets:
        # 1の部屋の隣
        global done_set
        done_set = done_set | {node}
        my_next_targets = list(set(node2nb_dict[node]) - done_set - set(next_targets))
        w_next_targets[node] = my_next_targets
        route_dict[node] = node_a

        for next_node in my_next_targets:
            # 次の探索対象も確定させる
            route_dict[next_node] = node
            done_set = done_set | {next_node}  # 巡回済みノードの更新
    return w_next_targets


node_a = 1
next_targets = {node_a: node2nb_dict[1]}

while next_targets:
    for node_a, next_list in next_targets.items():
        next_targets = f(next_list, node_a)

if len(route_dict.keys()) == N - 1:
    ans = "Yes\n"
    for i in range(2, N + 1):
        ans += str(route_dict[i]) + "\n"
else:
    ans = "No"

# print(route_dict)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[[float("inf")]*n for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    ab[a-1][b-1]=1
    ab[b-1][a-1]=1
flag=[False]*n
flag[0]=True

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
    
l = dijkstra(0,n,m,ab)
print("yes")
for i in range(1,n):
    print(l[i])

Submission status: Wrong Answer

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
n,m=n1()
ab=n3(m)

ans={}
d=[0]*(n+1)
p=[1]
p2=[]
while len(ans)<n-1:
    for c in p:
        d[c]=1
        for a,b in ab:
            if a==c and d[b]==0:
                p2.append(b)
                d[b]=1
                ans[b]=a
                del ab[ab.index([a,b])]
            if b==c and d[a]==0:
                p2.append(a)
                d[a]=1
                ans[a]=b
                del ab[ab.index([a,b])]
    p=p2.copy()
    p2=[]

A=list(ans.items())
A.sort(key=lambda x:x[0])
print("Yes")
for line in A:
    print(line[1])

Submission status: Wrong Answer

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

miti = [0] * (N - 1)
path = { i:set() for i in range(1, N+1)}
routes = []
for i in range(M):
    Ai, Bi = [ int(i) for i in input().strip().split(' ')]
    path[Ai].add(Bi)
    path[Bi].add(Ai)

#print(path)
targets = set([1])
check_list = set([1])

while True:
#    print(targets)
    for target in targets:
        targets = []
        for t in set(path[target])-check_list:
            if miti[t-2] == 0:
                miti[t-2] = target
        targets += path[target]
        check_list.add(target)
#    print(check_list)
    targets = set(targets) - check_list
    if len(check_list) == N:
        print('Yes')
        for mt in miti:
            print(mt)
        break
    if len(targets) == 0:
        print('No')
        break

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
cnt = [100] * (n + 1) #何回
res = [0] * (n + 1) #結果
res[0] = -1
res[1] = -1

for i in range(m):
    a[i], b[i] = map(int, input().split())
    
    if a[i] == 1:
        cnt[b[i]] = 1
        res[b[i]] = 1
    if b[i] == 1:
        cnt[a[i]] = 1
        res[a[i]] = 1
        
for i in range(1,n):
    for j in range(m):
        if cnt[a[j]] == i:
            if(res[b[j]] == 0):
                cnt[b[j]] = i + 1
                res[b[j]] = a[j]
        if cnt[b[j]] == i:
            if(res[a[j]] == 0):
                cnt[a[j]] = i + 1
                res[a[j]] = b[j]

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())

road = [[] for _ in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    road[A].append(B)
    road[B].append(A)
# print(road)


ans = [-1] * (N + 1)
ans[1] = 0
ans[0] = 0
already = set()

stack = deque([])
for r in road[1]:
    stack.append(r)
    already.add(r)

# print(already)
# print(stack)
# print()
def dfs(s):
    now = s
    cnt = 1
    while len(stack) > 0:
        next_root = stack.popleft()
        # print("now ", now)
        # print("next ", next_root)

        for r in road[now]:
            if (ans[r] == -1):
                if r not in already:
                    already.add(r)
                    stack.append(r)
                ans[r] = now

        now = next_root
        # print(ans)
        # print("stack", stack)
        # print()
dfs(1)

temp = set(ans)
if ((-1) in temp):
    print("No")
else:
    print("Yes")
    for a in ans[2:]:
        print(a)

Submission status: Wrong Answer

Solution code:
import networkx as nx

n,m = map(int,input().split())
G = nx.Graph()
flag = True
for _ in range(m):
    a,b = map(int,input().split())
    G.add_edge(a,b)
    if min(a,b) == 1:
        flag = False

if flag:
    print("No")
else:
    l = nx.shortest_path(G, target=1)
    print(l)
    print("Yes")
    [print(l[i][1]) for i in range(2,len(l)+1)]

Submission status: Wrong Answer

Solution code:
tmp=input().split(" ")
room=int(tmp[0])
road=int(tmp[1])
room_list=[room for i in range(room+1)]
room_list[1]=0

yet_list=[]
tmp1=0
tmp2=0
for i in range(road):
    tmp=input().split()
    tmp1=int(tmp[0])
    tmp2=int(tmp[1])
    if room_list[tmp1]==room and room_list[tmp2]==room:
        yet_list.append([tmp1,tmp2])
    elif room_list[tmp1]<room_list[tmp2]:
        room_list[tmp2]=tmp1
    elif room_list[tmp2]<room_list[tmp1]:
        room_list[tmp1]=tmp2
    
while(yet_list!=[]):
    tmp1=yet_list[0][0]
    tmp2=yet_list[0][1]
    yet_list.remove([tmp1,tmp2])
    if room_list[tmp1]==room and room_list[tmp2]==room:
        yet_list.append([tmp1,tmp2])
    elif room_list[tmp1]<room_list[tmp2]:
        room_list[tmp2]=tmp1
    elif room_list[tmp2]<room_list[tmp1]:
        room_list[tmp1]=tmp2

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

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[1:]

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

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