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
from collections import deque
N,M = [int(i) for i in input().split()]
roads = []
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    roads.append([A,B])
    roads.append([B,A])
roads = np.array(roads)
places = [0]*(N+1)
places[1] = 1
q = deque([1])
n = 1
while n < N:
    i = q.pop()
    L = roads[roads[:,0] == i][:,1]
    for j in L:
        if places[j] == 0:
            places[j] = i
            q.appendleft(j)
            n += 1
    q = set(q)
    q = list(q)
    q = deque(q)
print("Yes")
for i in range(2,N+1):
    print(places[i])

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7
n, m = map(int, input().split())
# 幅優先？
ans = [-1 for i in range(n)]  # i+1番目の部屋にある道しるべ
visited = [False for i in range(n)]
visited[0] = True
dicab = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in dicab.keys():
        dicab[a].append(b)
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]
    else:
        dicab[a] = [b]
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]


def bfs():
    q = deque([0])
    while q:
        now = q.pop()
        nlist = dicab[now]
        for nextnode in nlist:
            if visited[nextnode] == True:
                continue
            if ans[nextnode] == -1:
                ans[nextnode] = now
                q.append(nextnode)
                visited[nextnode] = True


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

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split())
    list = [[0 for i in range(0)] for j in range(n+1)]
    key = [1]
    ans = [0] * (n+1)
    flag = [0] * (n+1)
    keyflag = [0] * (n+1)
    cnt = 0
    cnt2 = 0
    t = 0

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

    for i in range(2,n+1):
        if 1 in list[i]:
            ans[i] = 1
            flag[i] = 1
            key.append(i)
            keyflag[i] = 1
            cnt += 1

    while 0 in ans[2:]:
        t = 0
        for j in key[cnt2:]:
            cnt2 = cnt
            for i in range(2,n+1):
                if(flag[i] == 0):
                    if j in list[i]:
                        ans[i] = j
                        flag[i] = 1
                        key.append(i)
                        cnt += 1
                        t = 1
        if t == 0:
            break

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



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy
N,M=list(map(int,input().split()))
a = []
for i in range(M):
    a.append(list(map(int,input().split())))
b=[[0]*(N+1) for i in range(N+1)]
d=list()
k=1
ans=[0]*(N+1)
for i in range(M):
    if a[i][0]==1:
        b[a[i][1]][1]=1
        ans[a[i][1]]=1
        d.append(a[i][1])
    else:
        b[a[i][1]][a[i][0]]=-1     
    if a[i][1]==1:
        b[a[i][0]][1]=1
        ans[a[i][0]]=1
        d.append(a[i][0])
    else:
        b[a[i][0]][a[i][1]]=-1  
frag=1
while frag==1:
    check=len(d)
    frag=0
    for i in range(check):
        for j in range(2,N+1):
            if b[j][d[i]]==-1:
                if ans[j]==0:
                    ans[j]=d[i]
                frag=1
                if b[j] in d == False:
                    d.append(b[j])
    for i in range(check):
        del d[0]
c=1
for i in range(2,N+1):
    if ans[i]==0:
        c=0
if c==0:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys 
from collections import defaultdict 
 
class Graph: 
 
    def __init__(self): 
        global n
        self.graph = defaultdict(list) 
        self.parent = [None for i in range(0,n+1)]
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
    def BFS(self, s): 
        visited = [False] * (len(self.graph)+1) 
        queue = [] 
        queue.append(s)   
        while queue: 
            s = queue.pop(0) 
            
            # print (s, end = " ") 
            for i in self.graph[s]: 
                
                if visited[i] == False: 
                    self.parent[i]=s
                    queue.append(i) 
                    visited[i]=True
            

[n,m]=[int(i) for i in input().split(' ')]
g = Graph() 
for i in range(0,m):
    [a,b]=[int(i) for i in input().split(' ')]
    g.addEdge(a,b)
    g.addEdge(b,a)
# print(g.graph)
g.BFS(1)
flag=0
for i in range(2,n+1):
    if g.parent[i]==None:
        print('NO')
        flag=1
        break

if flag==0:
    print('YES')
    for i in range(2,n+1):
        print(g.parent[i])
        9

Submission status: Wrong Answer

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


def main():
    n, m = map(int, input().split())
    lst = [[] for _ in range(n + 1)]
    ans = [0] * (n + 1)
    for _ in range(m):
        ab = list(map(int, input().split()))
        a, b = tuple(sorted(ab))
        lst[a].append(b)
        lst[b].append(a)

    limit = 10 ** 5
    d = {i: limit + 1 for i in range(1, n + 1)}
    d[1] = 0

    def dfs(n, length):
        # 道しるべ分次へ向かう
        # 洞窟＝n、length=最短距離、i=次の洞窟
        for i in lst[n]:
            if length >= d[i] or i == 1:
                continue
            else:
                d[i] = length
                ans[i] = n

        while lst[n]:
            p = lst[n].pop()
            if d[p] == length:
                dfs(i, length + 1)

    dfs(1, 1)

    if all(i for i in ans[2:] if i != 0):
        print('Yes')
        print(*ans[2:], sep='\n')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
b = []
#r = ['']*n
for i in range(m):
  t1, t2 = map(int, input().split())
  a.append(t1)
  b.append(t2)
#  r[t2-1]+=' '+str(t1-1)
#  r[t1-1]+=' '+str(t2-1)
#for i in range(len(r)):
#  r[i] = list(map(int, r[i].split()))
#print(r)
d = [-1]*n
d[0] = 0
ans = [-1]*(n-1)
#for i in range(len(a)):
i = 0  
while i < len(a):
  if d[a[i]-1] == -1 and d[b[i]-1] == -1:
    a.append(a[i])
    b.append(b[i])
  elif d[a[i]-1] == -1:
    d[a[i]-1] = d[b[i]-1]+1
    ans[a[i]-2] = b[i]
  elif d[b[i]-1] == -1:
    d[b[i]-1] = d[a[i]-1]+1
    ans[b[i]-2] = a[i]
  elif d[a[i]-1] > d[b[i]-1]:
    d[a[i]-1] = d[b[i]-1]+1
    ans[a[i]-2] = b[i]
  elif d[a[i]-1] < d[b[i]-1]:
    d[b[i]-1] = d[a[i]-1]+1
    ans[b[i]-2] = a[i]
  i += 1
if ans.count(-1) > 0:
  print('No')
else:
  print('Yes')
  for i in reversed(ans):
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np
from collections import Counter
import math

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

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
print(ans)
if 0 in ans[1:]:
    print('No')
    exit()
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Submission status: Wrong Answer

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

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

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

q = [0]

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


while q:
    l = q.pop(0)
    for i in edges[l]:
        if ans[i] == -1:
            ans[i] = l
            count += 1
            q.append(i)
    if count == n:
        break

if count == n:
    for i in ans[1:]:
        print(i+1)
else:
    print('No')

Submission status: Wrong Answer

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

l = [[False for _ in range(n)] for __ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    l[a-1][b-1] = l[b-1][a-1] = True

p = [0 for _ in range(n)]
s = [1]
j = 0
while j < n-1:
    r = s[j]
    j += 1
    for i, b in enumerate(l[r-1]):
        if b and i+1 not in s:
            p[i] = r
            if 0 not in p[1:]:
                break
            s.append(i+1)

if 0 in p[1:]:
    print('No')
else:
    print('Yes')
    for pp in p[1:]:
        print(pp)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

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

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

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

parent += 1

print('Yes')
for node in parent[1:]:
    print(node)

Submission status: Wrong Answer

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

def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

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

import sys
sys.setrecursionlimit(2000000)

N,M = input_multiple_number()

ans = [0]*(N)
ans[0] = 1
michi = [[] for i in range(N+1)]
isVisit = [False]*N
isVisit[0] = True

for i in range(M):
	a,b = input_multiple_number()
	michi[a].append(b)
	michi[b].append(a)

def DFS(K):
	for heya in michi[K]:
		if ans[heya-1] == 0:
			ans[heya-1] = K

	for heya in michi[K]:
		if not isVisit[heya-1]:
			isVisit[heya-1] = True
			DFS(heya)

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

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np
from collections import Counter
import math

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

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
print(G)
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
if 0 in ans[2:]:
    print('No')
    exit()
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int, input().split()))
root = [[] for _ in range(n)]
answer=[0]*n
answer[0]=1
for i in range(m):
    c=list(map(int, input().split()))
    root[c[1]-1].append(c[0]-1)
    root[c[0]-1].append(c[1]-1)
count=1#最初から1の部屋はOKにしとく
queue=[0]
#print(root)
newqueue=[]
while(count<n and len(queue)!=0):
    for j in queue:
        for rootnum in root[j]:
            if(answer[rootnum]==0):
                answer[rootnum]=j
                newqueue.append(rootnum)
                count+=1
    queue=newqueue
    #print(newqueue)
    newqueue=[]
if(count<n):
    print('No')
else:
    print('Yes')
    for l in range(n-1):
        print(answer[l+1]+1)

Submission status: Wrong Answer

Solution code:
import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}
results[0] = (0, 0)
used = set()

while queue:
    cost, cur = queue.pop()
    if cur in used:
        continue
    used.add(cur)
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.append((next_cost, next_cur))

is_no = False
for k, result in results.items():
    if k == 0:
        continue
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for k, result in results.items():
        if k == 0:
            continue
        print(result[1] + 1)

Submission status: Wrong Answer

Solution code:
import numpy as np
room, route_count = map(int,input().split())
route = np.array([list(map(int,input().split())) for _ in range(route_count)])

ans = np.array([0]*(room-1))

def mem_ans(ans, object_num, next_num):
  for n in next_num:
    if ans[n-2] == 0:
      ans[n-2] = object_num
  return ans

object_nums = [1]
next_num = [1]

for object_num in object_nums:
    is_object_route = np.any(route==object_num, axis=1)
    object_rows = route[is_object_route]
    route[is_object_route] = 0
    next_num = object_rows[object_rows!=object_num]
    ans = mem_ans(ans, object_num, next_num)
    object_nums.extend(next_num)
    print(next_num)
if 0 in set(ans):
  print('No')
else:
  print('Yes')
  for i in ans:
    print(i)

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]
check = whole
ans = [0 for i in range(n)]
while len(whole) < n:
    part = []
    for i in check:
        dellist = []
        for j in range(len(ab)):
            c = 0
            k = ab[j]
            if k[0] == i:
                if (k[1] not in whole) and (k[1] not in part):
                    part.append(k[1])
                    ans[k[1]-1] = i
                    c += 1
            if k[1] == i:
                if (k[0] not in whole) and (k[0] not in part):
                    part.append(k[0])
                    ans[k[0]-1] = i
                    c += 1
            if c > 0:
                dellist.append(k)
        for i in dellist:
            del i
        
    check = part[:]
    for i in part:
        whole.append(i)
print("yes")
for i in range(1,n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np
from collections import Counter
import math

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

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
print(G)
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
if 0 in ans[1:]:
    print('No')
    exit()
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Submission status: Wrong Answer

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

ans = [-1]*n
ans[0] = 0
from collections import deque
q = deque([0])
while q:
    u = q.popleft()
    for v in d[u]:
        if ans[v]==-1:
            ans[v] = u
            q.append(v)
print('Yes')
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np
from collections import Counter
import math

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

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
print(G)
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
if 0 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np
from collections import Counter
import math

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

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
print(G)
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
                print(ans)
    s = ne
if 0 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Submission status: Wrong Answer

Solution code:
import math

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

hist= []
visited_pos = [-1] * n

#初期情報
#print(ab)
ts = {}
for el in ab:
  wk = ts.get(el[0]) 
  if wk is None:
    sss  = set()
    ts[el[0]] = sss
  ts[el[0]].add(el[1])
  wk = ts.get(el[1]) 
  if wk is None:
    sss  = set()
    ts[el[1]] = sss
  ts[el[1]].add(el[0])
#print(ts)


#幅優先探索
def tsk(pos):
  wk = ts.get(pos)
  if ts.get(pos) is None:
    return
  else:
    #print(pos,wk)
    for e in wk:
      if visited_pos[e-1] < 0:
        visited_pos[e-1] = pos
        hist.append(e-1)

idx = 0
hist.append(1)
while True:
  if idx >= len(hist):
    break
  else:
    tsk(hist[idx])
    idx += 1
#print(hist)
#print(visited_pos)
ans = 'Yes'
for i in range(n):
  if visited_pos[i] == -1:
    ans = 'No'
    break

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
path = [[] for _ in range(n+1)]

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


# print('path', path)
to = [0] * (n+1)
# print(to)
for i in range(1, n+1):
    # print('path(i)', path[i])
    for j in path[i]:
        if to[j] == 0:
            to[j] = i
            # print('to', to)

# print('to', to)
if 0 in to[2:]:
    print('No')
else:
    print('Yes')
    [print(x) for x in to[2:]]

Submission status: Wrong Answer

Solution code:

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

if N > M+1:
    print('No')
else:
    L = []

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

    key = 1
    D = [-1]*N
    def rec(L,D,key):
        # print()
        # print('key=',key)
        # print('D',D)
        # keyが含まれる部分を抽出する
        LL = [ item for item in L if key in item]

        if len(LL) == 0:
            return

        # Lから削除
        for index, item in enumerate(L):
            if item in LL:
                del L[index]

        # keyから接続されたノードリストを得る
        LLL = list(itertools.chain.from_iterable(LL))
        connectedNodes = [i for i in LLL if i!=key]
        # print('connectedNodes:',connectedNodes)

        ## keyから接続されたノードについてkeyの方を指すようにする
        for item in connectedNodes:
            if D[item-1] == -1:
                D[item-1] = key

        for item in connectedNodes:
            rec(L,D,item)

    rec(L,D,key)

    # print(D)
    DD = D[1:]

    # print('DD:',DD)

    if -1 in DD:
        print('No')
    else:
        print('Yes')
        for item in DD:
            print(item)

Submission status: Wrong Answer

Solution code:
import sys
N , M = (map(int , input().split()))
root_list = []
for i in range(M):
    A = list(map(int , input().split()))
    A.sort()
    root_list.append(A)
nn_dict = {}
for i in root_list:
    if 1 in i:
        try:
            i.remove(1)
            nn_dict.update({i[0]:1})
        except:
            pass
if nn_dict == {}:
    print('No')
    sys.exit()
nnn_dict = nn_dict.copy()
for i in nnn_dict.keys():
    for j in root_list:
        if i in j:
            try:
                j.remove(i)
                if j[0] not in nn_dict:
                    nn_dict.update({j[0]:i})
            except:
                pass
k_list = list(nn_dict.keys())
v_list = list(set(nn_dict.values()))
new_list = list(set(k_list)-set(v_list))
kk_list = []
while True:
    for i in new_list:
        for j in root_list:
            if i in j:
                try:
                    j.remove(i)
                    if j[0] not in nn_dict:
                        nn_dict.update({j[0]:i})
                except:
                    pass
    k_list = sorted(list(nn_dict.keys()))
    if kk_list == k_list:
        break
    else:
        kk_list = k_list
score_sorted = sorted(nn_dict.items(), key=lambda x:x[0] ,reverse=False)
print('Yes')
for i in score_sorted:
    if i[0] != 1:
        print(i[1])

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
d = deque()
d2 = deque()
As = [0] * m
Bs = [0] * m
Cs = [0] * max((m + 1), (n + 1))  # 標

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


def solver(i, c):
    aindexs = [j for j, x in enumerate(As) if x == i]
    bindexs = [j for j, x in enumerate(Bs) if x == i]
    indexs = aindexs + bindexs
    for aindex in aindexs:
        d.append(Bs[aindex])
        d2.append(c + 1)
    for bindex in bindexs:
        d.append(As[bindex])
        d2.append(c + 1)
    for index in indexs:
        As[index] = -1
        Bs[index] = -1
        Cs[index] = c


solver(1, 1)
d.append(1)
d2.append(1)
while d:
    solver(d.popleft(), d2.popleft())

for i in range(2, n + 1):
    if (Cs[i] == 0):
        print('No')
        exit()
print('Yes')
for i in range(2, n + 1):
    print(Cs[i])

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import numpy as np
# D

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

row = []
col = []
for i in range(M):
    r, c = list(map(int, input().split()))
    row.append(r-1)
    col.append(c-1)

data = [1] * (M)

csr = csr_matrix((data, (row, col)), shape=(N, N))
from_starts, procs = dijkstra(csr, indices=[0], directed=False, return_predecessors=True)
proc = procs[0]+1
 
if -9999 in proc[1:]:
  print('No')
else:
  print('Yes')
  for i in range(N-1):
    print(proc[i+1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def kamban_okude(imano_room, i):
    imano_room = int(imano_room)
    global michi_to
    global kamban
    i += 1
    next_room = michi_to[imano_room]
    if next_room == []:
        return
    for element in next_room:
        next_doko(element, imano_room, i)
    return

def next_doko(element, imano_room, i):
    global kamban
    if kamban[element][0] == -1:
        kamban[element][0] = imano_room
        kamban[element][1] = i
        return(kamban_okude(element, i))
    else:
        return

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



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

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

tf = kamban_okude(1, i)

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

Submission status: Wrong Answer

Solution code:
import itertools

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

path = [[False] * n for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

anspath = [float('inf')] * (n-1)

ans = 0

# 頂点を並び替える順列を生成してループ
for i in itertools.permutations(range(n), n):
  # 頂点1が終点
  if i[-1] == 0:
    # 生成した順列の中をさらにループ
    temppath = [0]*(n-1)
    for j in range(n):
      # n - 1 まで続いたら条件を満たすパスが存在する
      if j == n - 1:
        ans += 1
        for p in range(n-1):
          if temppath[p] <= anspath[p]:
            anspath[p] = temppath[p]
        break
      # i[j] から i[j + 1] に行くパスがなければ終了
      if not path[i[j]][i[j + 1]]:
        break
      else:
        temppath[i[j]-1] = i[j+1]  

if ans >= 1:
  print("Yes")
  for i in range(n-1):
    print(anspath[i]+1)
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import numpy

inp=input().split(" ")

n=int(inp[0])
m=int(inp[1])
array=numpy.zeros(m*2,dtype=">i4")

for i in range(m):
  a=(input().split(" "))
  array[2*i]=(int(a[0]))
  array[2*i+1]=(int(a[1]))

ans=numpy.ones(n-1,dtype=">i4")
ans*=-1
nums=[]
next=[-1]
where=numpy.where(array==1)[0]
while True:
    remcount=0
    for i in where:
        i=i-remcount
        if (i%2)==1:
          if array[i-1] not in nums:
            next.append(array[i-1])
            nums.append(array[i-1])
            ans[array[i-1]-2]=array[i]
            array=numpy.delete(array,i-1)
            array=numpy.delete(array,i-1)
        else:
          if array[i+1] not in nums:
            next.append(array[i+1])
            nums.append(array[i+1])
            ans[array[i+1]-2]=array[i]
            array=numpy.delete(array,i)
            array=numpy.delete(array,i)
        remcount+=2
    if len(next) == 0:
      break
    if next[0]!=-1:
      where=numpy.where(array==next[0])[0]
    else:
      next.pop(0)
      where=numpy.where(array==next[0])[0]
    next.pop(0)

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq

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

g = [[] for _ 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)#番号を修正。0スタートに。
#print(g)

INF = float('inf')
reach = [INF for _ in range(N)] #0からの距離を記録。INF未到達。
reach[0] = 0
par = [-1 for _ in range(N)] #親の位置を記録

Q =[]
heapq.heappush(Q, (0,0)) #0からの距離と頂点を入れる。

while Q:
  d,v = heapq.heappop(Q)
  for i in range(len(g[v])): #点vから行ける点をすべて探索
    u = g[v][i] #今探索している点
    print(v,u)
    if u == 0: #始点の場合はスルー
      continue
    if reach[u] != INF: #到達済みならスキップ
      continue
    reach[u] = reach[v] + 1 #探索中の点の到達を記録。
    par[u] = v
    heapq.heappush(Q, (reach[u],u))

#print(reach,par)
if INF not in reach[1:]:
  print("Yes")
  for i in range(1,N):
    ans = par[i]+1
    print(ans)
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
l=[[]]*n
for a,b in ab:
  l[a-1].append(b)
  l[b-1].append(a)
ans=[[0]]*(n)
for j in range(n):
  for lll in l[j]:
    ans[lll-1]=j+1
for t in range(1,n):
  print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ANS = [-1]*(n+1)
P = []
L = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())

    if a == 1:
        ANS[b] = 1
        P.append(b)
    elif b == 1:
        ANS[a] = 1
        P.append(a)
    else:    
        L[a].append(b)
        L[b].append(a)

print(L, ANS, P)

i = 0
while len(P) < n-1:
    for j in range(1, n+1):
        if P[i] in L[j] and ANS[j] == -1:
            P.append(j)
            L[j].remove(P[i])
            ANS[j] = P[i]
            # print(i, P[i], j, L, ANS, P)
    i += 1

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

Submission status: Wrong Answer

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

TFl=[0 for _ in range(N)]
ml=[0 for _ in range(N)]

for i in range(N):
  l.append([])

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

for i  in range(len(l)):
  for j in range(len(l[i])):
    TFl[l[i][j]]=1
    if ml[l[i][j]]==0:
      ml[l[i][j]]=i
  if all([k==1 for k in TFl]):
    break

if all([i==1 for i in TFl]):
  print('Yes')
  for i in range(1, N):
    print(ml[i]+1)


else:
  print('No')

Submission status: Wrong Answer

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

ans = [-1]*n
ans[0] = 0
from collections import deque
q = deque([0])
while q:
    u = q.pop()
    for v in d[u]:
        if ans[v]==-1:
            ans[v] = ans[u]+1
            q.append(v)
print('Yes')
for i in ans[1:]:
    print(i)