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:
#!/usr/bin/python3

import numpy
#標準出力からの読み込み
input_1 = input()
n = int(input_1.split(" ")[0])
m = int(input_1.split(" ")[1])

road = []
for i in range(m):
    input_m = input()
    road.append(int(input_m.split(" ")[0]))
    road.append(int(input_m.split(" ")[1]))

#判定ロジック

list_a = [i for i, x in enumerate(road) if x == 4]
output = ['' for s in range(n)]
output[0] = 'Yes'

def mark_maker(road, room_list, output):
    next_room_list = []
    for room in room_list:
        tmp_rooms_index = [i for i, x in enumerate(road) if x == room]
        next_rooms_index = list(map(lambda x: x+1 if x%2==0 else x-1, tmp_rooms_index))
        next_rooms = [road[j] for j in next_rooms_index]
        for k in next_rooms:
            if k == 1:
                continue
            if output[k-1] == '':
                output[k-1] = room
                next_room_list.append(k)
    return output, next_room_list

room_list = [1]
for i in range(100000):
    output, room_list = mark_maker(road, room_list, output)

if '' in output:
    output = 'No'

print(output)

Submission status: Wrong Answer

Solution code:
def dijkstra(startNode, nodeNum, edgeNum, cost):
    '''
    startNodeから各頂点への最短距離をダイクストラ法で計算
    startNode:始点
    nodeNum:ノードの数
    edgeNum:エッジの数
    cost[a][b]:ab間の距離
    '''
    d = [float('inf')]*nodeNum
    x = [0]*nodeNum
    usedNode = [False]*nodeNum
    d[startNode] = 0
    
    while True:
        v = -1
        y = 0
        for i in range(n):
            if (not usedNode[i]) and (v == -1):
                v=i
                y=i+1
            elif (not usedNode[i]) and d[i] < d[v]:
                v=i
                y=i+1
        if v == -1:
            break
        usedNode[v] = True

        for j in range(n):
            if d[j] > d[v]+cost[v][j]:
                d[j] = d[v]+cost[v][j]
                x[j] = y
    return d,x


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

c = [[float('inf') for i in range(n)] for j in range(n)]
for i in range(m):
    c[a[i-1]-1][b[i-1]-1] = 1
    c[b[i-1]-1][a[i-1]-1] = 1

d,x = dijkstra(0, n, m, c)

print('yes')
for i in range(n-1):
    print(x[i+1])

Submission status: Wrong Answer

Solution code:
import math
import sys
sys.setrecursionlimit(10000000)
N,M=map(int,input().split())
road=[[]for i in range(M)]
graph=[[]for j in range(N)]
for i in range(M):
    road[i]=list(map(int,input().split()))
    graph[road[i][0]-1].append(road[i][1])
    graph[road[i][1]-1].append(road[i][0])

# print(graph)
# print(road)
ans=[-1 for i in range(N)]

def dfs(K):
    for i in graph[K]:
        if ans[i-1] != -1:
            return
        else:
            j=i-1
            ans[j] = K+1
            dfs(j)
dfs(0)
if -1 in ans:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(ans[i])

Submission status: Wrong Answer

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

matrix = [[0]*N for i in range(N)]
for i in range(M):
    matrix[l[i][0]-1][l[i][1]-1] = 1
    matrix[l[i][1]-1][l[i][0]-1] = 1
que = [0]
check = [0]*N

temp_l = [list(range(N)), [0]*N, [0]*N]

count = 0
while len(que) != 0:
    count += 1
    search = que.pop(0)
    for i in range(N):
        if matrix[search][i] == 1 and check[i] == 0:
            que.append(i)
            temp_l[1][i] = search
            temp_l[2][i] = count
            check[i] = 1

print(temp_l[1])
if 0 in temp_l:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(temp_l[1][i]+1)

Submission status: Wrong Answer

Solution code:
def cango(l,room):
  for i in range(len(l)+1):
    room = l[room]
    if room == 1:
      return 1,i
  return 0,10000

import sys

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

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

import itertools

options = AB

keys = options.keys()
values = (options[key] for key in keys)
combinations = [dict(zip(keys, combination)) for combination in itertools.product(*values)]
can_list = []
for i in combinations:
  l = 0
  can = []
  t = len(i)
  for j in range(2, t+1):
    tmp1,tmp2 = cango(i,j)
    l = l+tmp1
    can.append(tmp2)
  if l == t-1:
    if len(can_list)==0:
      can_list=can
    else:
      fff = 0
      for x in can:
        for y in can_list:
          if x<=y:
            pass
          else:
            fff = 1
            break
      if fff == 0:
        can_list = can
            
      
      
if len(can_list)>0:
  print("Yes")
  for i in can_list:
    print(i)
else:
  print("No")

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 = 1
hist.append(1)
while True:
  if idx > len(hist):
    break
  else:
    tsk(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:
int1 = lambda n:int(n)-1

def main():
    N, M = map(int, input().split())
    edges = [set() for _ in range(N)]
    ans = [-1] * (N)
    for _ in range(M):
        A, B = map(int1, input().split())
        edges[A].add(B)
        edges[B].add(A)

    queue = [0]
    seen = set()
    while queue:
        s = queue.pop()
        for ss in edges[s]:
            if ss not in seen:
                ans[ss] = s
                queue.append(ss)
                seen.add(ss)
    if -1 in ans[1:]:
        print('No')
    else:
        print('Yes')
        for a in ans[1:]:
            print(a+1)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def breath_first_search(start :int, am :list):
    backs = [-1 for _ in range(n)]
    q = deque([start])
    visited = set([start])

    while True:
        if not q: break
        now = q.popleft()
        for node, is_adj in enumerate(am[now]):
            if not is_adj: continue
            if node in visited: continue
            print(now, node)
            backs[node] = now
            q.append(node)
            visited.add(node)

    return backs

n, m = map(int, input().split())
paths = [list(map(int, input().split())) for _ in range(m)]
am = [[0]*n for _ in range(n)]
for a, b in paths:
    am[a-1][b-1] = 1
    am[b-1][a-1] = 1

backs = breath_first_search(0, am)

if -1 in backs:
    print("Yes")

for back in backs[1:]:
    print(back+1)

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()))
ABs = np.array([list(map(int, input().split())) for i in range(M)])

row = list(ABs.T[0]-1)
col = list(ABs.T[1]-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:
# list(map(int, input().split()))
# int(input())

def main(AB, N, M):

    def serch(st = {1}, already = {1}, dict = {1:1}):
        next_dict = dict.copy()
        # for l in st:
        #     for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]:
        #         next_dict.setdefault(i, l)

        # next_dict.update({i:l for l in st for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]})

        # [next_dict.setdefault(i, l) for l in st for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]]
        # next_st = {k for k in next_dict if k not in already}

        next_dict.update({i:l for l in st for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab] if i not in already})
        next_st = set(next_dict.keys())
        # [already.add(k) for k in next_st]
        next_already = already.union(next_st)
        print(next_dict, next_st, next_already)
        if len(next_already) == N:
            return next_dict
        elif len(next_st) == 0:
            print('No')
            exit()
        else:
            return serch(next_st, next_already, next_dict)

    ans = serch()
    print('Yes')
    [print(ans[i + 1]) for i in range(1, N)]



if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    AB = []
    for _ in range(M):
        AB.append(list(map(int, input().split())))
    main(AB, N, M)

Submission status: Wrong Answer

Solution code:
import numpy as np

def search_and_mark(recent_rooms, rooms, AB, count, count_max):
  if None not in rooms:
    return rooms

  if count >= count_max:
    return []
  tmp_rooms = []
  for r in recent_rooms:
    tmp = AB[np.any(AB == r, axis=1)]
    target = tmp[tmp != r]
    tmp_rooms.extend(target)
    
    for t in target:
      if rooms[t] == None:
        rooms[t] = r

  recent_rooms = tmp_rooms
  return search_and_mark(recent_rooms, rooms, AB, count+1, count_max)

def resolve():
  N, M = map(int, input().split(" "))
  rooms = [None] * N

  AB = []
  for m in range(M):
    AB.append([int(x) - 1 for x in input().split(" ")])

  # AB.sort()
  # setAB = set(AB)
  AB = np.array(AB)
  result = search_and_mark([0], rooms, AB, 1, N)

  # print(AB)

  if(len(result) > 0):
    print("Yes")
    for r in result[1:]:
      print(r + 1)
  else:
    print("No")

  return True

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

dist = [1000000] * n
ans = [None]*n
not_visited = set(range(n))
not_visited.remove(0)
vs = deque([0])
dist[0] = 0
while vs:
    v = vs.popleft()
    print(v, e[v])
    for other_side in e[v]:
        if other_side in not_visited:
            vs.append(other_side)
            not_visited.remove(other_side)
            if dist[other_side] > dist[v] + 1:
                dist[other_side] = dist[v] + 1
                ans[other_side] = v

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

Submission status: Wrong Answer

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

from collections import deque

N,M=map(int,input().split())
AL=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    AL[A-1].append(B-1)
    AL[B-1].append(A-1)
Q=deque([[0,-1]]) # [今いるindex,前のindex]
ANS=[-1 for _ in range(N)] # 答え
ANS[0]=1
TF=[0 for _ in range(N)]
while Q:
    print(Q)
    i,c=Q.popleft()
    if TF[i]:
        continue
    TF[i]=1
    ANS[i]=c
    for j in AL[i]:
        if not TF[j]:
            Q.append([j,i])

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

Submission status: Wrong Answer

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

from collections import deque

N,M=map(int,input().split())
AL=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    AL[A-1].append(B-1)
    AL[B-1].append(A-1)
Q=deque([[0,-1]]) # [今いるindex,前のindex]
ANS=[-1 for _ in range(N)] # 答え
ANS[0]=1
TF=[0 for _ in range(N)]
while Q:
    print(Q)
    i,c=Q.popleft()
    if TF[i]:
        continue
    TF[i]=1
    ANS[i]=c
    for j in AL[i]:
        if not TF[j]:
            Q.append([j,i])

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = list(map(int, input().split()))
tsuro = [list(map(int, input().split())) for _ in range(M)]
tsuro = np.array(tsuro)
arr = list(range(2, N + 1))
tsuro = np.sort(tsuro, axis=1)
order = np.argsort(tsuro[:, 0])
tsuro = tsuro[order]

goal_list = [1]
ans_list = np.zeros(N)
start_list = list(range(M))
counts = 0
success_flag = False
while True:
    if counts > 2 * N:
        print('No')
        break
    room_a, room_b = tsuro[start_list[0]]
    if room_a in goal_list and room_b in goal_list:
        start_list.pop(0)
    elif room_a in goal_list:
        goal_list.append(room_b)
        ans_list[room_b - 1] = room_a
        start_list.pop(0)
    elif room_b in goal_list:
        goal_list.append(room_a)
        ans_list[room_a - 1] = room_b
        start_list.pop(0)
    else:
        tmp = start_list.pop(0)
        start_list.append(tmp)
    if len(start_list) == 0:
        success_flag = True
        break
    counts += 1
if success_flag:
    print('Yes')
    for ans in ans_list[1:]:
        print(int(ans))

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 = 1
hist.append(1)
while True:
  if idx > len(hist):
    break
  else:
    tsk(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:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import numpy as np
# D

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

row = list(ABs.T[0]-1)
col = list(ABs.T[1]-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')
  print('\n'.join(proc[1:].astype('str')))

Submission status: Wrong Answer

Solution code:
# D
from collections import deque

N,M=map(int,input().split())
AL=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    AL[A-1].append(B-1)
    AL[B-1].append(A-1)
Q=deque([[0,-1]]) # [今いるindex,前のindex]
ANS=[-1 for _ in range(N)] # 答え
ANS[0]=1
TF=[0 for _ in range(N)]
while Q:
    print(Q)
    i,c=Q.popleft()
    if TF[i]:
        continue
    TF[i]=1
    ANS[i]=c
    for j in AL[i]:
        if not TF[j]:
            Q.append([j,i])

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

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(M)]
A.sort(key=lambda x: x[0],reverse = True)

floor = [10**6] * (N+1)
connect = [[] for _ in range(N+1)]
floor[1] = 0

for a,b in A:
    if floor[a] < floor[b]:
        floor[b] = floor[a]+1
    elif floor[a] > floor[b]:
        floor[a] = floor[b]+1
    connect[a].append(b)
    connect[b].append(a)

def f(l):
    tmp = list(map(lambda x:floor[x], l))
    return tmp

print("Yes")
for i,l in enumerate(connect[2:]):
    print(l[f(l).index(min(f(l)))])

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
import math
import sys
sys.setrecursionlimit(10**7)
def dfs(queue, visited_list, count, ans):
    visit = queue.pop()
    visited[visit] = 0
    if count == 1:
        ans = visit
    if visit == 1:
        print(ans)
        return 
    
    
    for i in G[visit]:
        if visited_list[i] != -1:
            continue
        queue.append(i)
        dfs(queue,visited_list, count+1, ans)


# k = int(input())
# s =input()
# a = list(map(int, input().split()))
n,m= map(int, input().split())
G = defaultdict(set) 
for i in range(m):
    x,y= map(int,input().split())
    G[x].add(y)
    G[y].add(x)

print("Yes")
for i in range(2,n+1):
    visited = [-1]*(n+1)
    queue = deque()
    visited[i]=0
    queue.appendleft(i)
    dfs(queue, visited,0,[])

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(-1)
    for i in edges[l]:
        if ans[i] == -1:
            ans[i] = l
            count += 1
            q.append(i)
    if count == n:
        break

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

Submission status: Wrong Answer

Solution code:
import itertools
import sys
import numpy as np
import collections


n,m = map(int, input().split())
l = sorted([sorted(input().split()) for _ in range(m)])
tansaku = '1'
noone_l = []
miti = [1] *(n+1)
for i,ab in enumerate(l):
    if ab[0] !=tansaku:
        noone_l = l[i:]
        break
    else:
        tansaku += ab[1]
        miti[int(ab[1])] = 1
next_l = noone_l
cnt=2
while len(next_l) !=0 and len(tansaku) < n:
    tmp = next_l[:]
    next_l.clear()
    for ab in tmp:
        if ab[0] and ab[1] in tansaku:
            continue
        elif ab[0] or ab[1] in tansaku:
            if ab[0] in tansaku:
                tansaku += ab[1]
                miti[int(ab[1])] = cnt
            else:
                tansaku += ab[0]
                miti[int(ab[0])] = cnt
        else:
            next_l.append(ab)
    if len(tmp) == len(next_l):
        print('No')
        break
    else:
        cnt+=1
else:
    print('Yes')
    for i in miti[2:]:
        print(i)

Submission status: Wrong Answer

Solution code:

import numpy as np

def search_and_mark(recent_rooms, rooms, AB, count, count_max):
  if None not in rooms:
    return rooms

  if count >= count_max:
    return []
  tmp_rooms = []
  for r in recent_rooms:
    tmp = AB[np.any(AB == r, axis=1)]
    target = tmp[tmp != r]
    tmp_rooms.extend(target)
    
    for t in target:
      rooms[t] = r

  recent_rooms = tmp_rooms
  return search_and_mark(recent_rooms, rooms, AB, count+1, count_max)

def resolve():
  N, M = map(int, input().split(" "))
  rooms = [None] * N

  AB = []
  for m in range(M):
    AB.append([int(x) - 1 for x in input().split(" ")])

  # AB.sort()
  # setAB = set(AB)
  AB = np.array(AB)
  result = search_and_mark([0], rooms, AB, 1, N)

  # print(AB)

  if(len(result) > 0):
    print("Yes")
    for r in result[1:]:
      print(r + 1)
  else:
    print("No")

  return True

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

path = []

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

# print(path)

linked = [[]]

ans = {}


for pi in path:
    for i, l in enumerate(linked):
        flg = False
        if pi[0] in l:
            flg = True
            l.add(pi[1])
            if pi[1] not in ans:
                ans[pi[1]] = pi[0]
        elif pi[1] in l:
            flg = True
            l.add(pi[0])
            if pi[0] not in ans:
                ans[pi[0]] = pi[1]

        if flg:
            break
        if i == len(linked) - 1:
            linked.append(set(pi))
            ans[pi[1]] = pi[0]
            ans[pi[0]] = pi[1]


linked.pop(0)
# print(linked)
# print(ans)

len_l = len(linked)

max_len = -1
ans_idx = -1


tmp_l = [set() for i in range(len_l)]
for i in range(len_l):
    for j in range(len_l):
        if not linked[i].isdisjoint(linked[j]):
            tmp_l[i] = tmp_l[i] | (linked[i] | linked[j])


for i in range(len(tmp_l)):
    if 1 in tmp_l[i]:
        max_len = max(len(tmp_l[i]), max_len)
        if max_len == len(tmp_l[i]):
            ans_idx = i

# print(tmp_l)
# print()
if len(tmp_l[ans_idx]) == n:
    print('Yes')
    for i in range(1, n):
        print(ans[i+1])
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[ans[AB[1]]] == 1:
      ans[AB[0]] = AB[1]
    elif ans[ans[AB[0]]] == 1:
      ans[AB[1]] = AB[0]
    elif ans[AB[0]] == 0 and ans[AB[1]] == 0:
      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[ans[AB[1]]] == 1:
    ans[AB[0]] = AB[1]
  elif ans[ans[AB[0]]] == 1:
    ans[AB[1]] = AB[0]
  elif ans[AB[0]] == 0 and ans[AB[1]] == 0:
    ans[AB[0]] = AB[1]
    ans[AB[1]] = AB[0]
    

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

q = deque([0])
dist = [-1]*N
dist[0] = 0

while q:
  v = q.popleft()
  for nv in G[v]:
    if dist[nv] == -1:
      dist[nv] = v+1
      q.append(nv)
 
print(*dist[1:])

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse import csr_matrix

from scipy.sparse.csgraph import dijkstra

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

edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T

graph = csr_matrix(([1]*M, (edge - 1)), (N, N))


distance_mat, processors = dijkstra(graph, directed = False, indices = [0, 1], return_predecessors = True)


if float("inf") in distance_mat[0]:
    print("No")
else:
    print("Yes")
    for i in range(1,len(processors[0])):
        print(processors[0][i]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
N, M = map(int, input().split())
D = [[float("inf")]*N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for i in range(M):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    D[s][t] = 1
    D[t][s] = 1

q = deque()
q.append(0)
d = defaultdict(lambda : int(-1))
d[0] = 0
while q:
    u = q.popleft()
    for v in range(N):
        if D[u][v] == float("inf"):
            continue
        if not d[v] == -1:
            continue
        d[v] = d[u] + 1
        q.append(v)
        break
if len(d) == N:
    print("Yes")
else:
    print("No")
    exit()
for i in range(1, N):
    print(d[i])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = []
f = [0] * n
f[0] = 1
for i in range(m):
    a, b = map(int, input().split())
    p = sorted([a, b])
    l.append(p)
    if p[0] == 1:
        f[p[1] - 1] = 1
l.sort()
for i in range(m):
    if f[l[i][0] - 1] == 0 and f[l[i][1] - 1] != 0:
        f[l[i][0] - 1] = l[i][1]
    elif f[l[i][0] - 1] != 0 and f[l[i][1] - 1] == 0:
        f[l[i][1] - 1] = l[i][0]
for i in range(m):
    if f[l[i][0] - 1] == 0 and f[l[i][1] - 1] != 0:
        f[l[i][0] - 1] = l[i][1]
    elif f[l[i][0] - 1] != 0 and f[l[i][1] - 1] == 0:
        f[l[i][1] - 1] = l[i][0]
for i in range(n):
    if f[i] == 0:
        print("No")
        exit()
print("Yes")
for i in range(1, n):
    print(f[i])

Submission status: Wrong Answer

Solution code:
import sys
import heapq


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]

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

    # print(adj)

    INF = 10 ** 18
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def dijkstra(s):
        color = [WHITE] * N
        d = [INF] * N
        p = [-1] * N
        d[s] = 0
        PQ = []
        heapq.heappush(PQ, (0, s))  # (距離, 頂点の番号)
        color[s] = GRAY

        while PQ:
            distance, u = heapq.heappop(PQ)
            color[u] = BLACK

            if d[u] < distance:
                continue
            # print(u)

            for j in range(len(adj[u])):
                v = adj[u][j]
                if color[v] == BLACK:
                    continue
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                    p[v] = u
                    heapq.heappush(PQ, (d[v], v))
                    color[v] = GRAY

        return d, p

    d, p = dijkstra(0)
    print(d, p)
    if INF in d[1:]:
        print("No")
        sys.exit()
    else:
        print("Yes")
        for i in range(1, N):
            print(d[i] + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
now = [0] * N
for i in range(M):
    A, B = map(int, input().split())
    a = now[A - 1]
    b = now[B - 1]
    if A == 1:
        now[B - 1] = 1
    elif B == 1:
        now[A - 1] = 1
    else:
        if a == 0:
            now[A - 1] = B
        elif a > B:
             now[A - 1] = B
        if b == 0:
            now[B - 1] = A
        elif b > A:
             now[B - 1] = A

if 0 in now[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(now[i],end = "\n")

Submission status: Wrong Answer

Solution code:
import queue


N,M = map(int, input().split())
A=[]
B=[]
for m in range(M):
  a,b = map(int, input().split())
  A.append(a)
  B.append(b)

dic = {}

for a,b in zip(A,B):
  if not a in dic:
    dic[a] = []
  if not b in dic:
    dic[b] = []

  dic[a].append(b)
  dic[b].append(a)

visited = [0] * N

q = queue.Queue()
visited[0] = 1
n_tot = 1
# print(dic)
q.put(1)
while n_tot < N:
  root = q.get()
  nodes = dic[root]
  for node in nodes:
    if visited[node-1] == 0:
      visited[node-1] = root
      n_tot += 1
#     print("q.queue,root,visited",q.queue,root,visited)
    else:
      q.put(node)

print('Yes')
for v in range(1,len(visited)):
  print(visited[v])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*n
f=0
flag=0
for i in range(m):
    a[i],b[i]=map(int,input().split())
    if a[i]==1:
        c[b[i]-1]=1
        f=f*10+b[i]
        flag+=1
    elif b[i]==1:
        c[a[i]-1]=1
        f=f*10+a[i]
        flag+=1
p=list(map((lambda x: int(x)), list(str(f))))
for j in range(len(p)):
    for i in range(m):
        if p[j]==a[i]:
            if c[b[i]-1]==0:
                c[b[i]-1]=a[i]
                flag+=1
                for k in range(len(p)):
                    if p[j]==b[i]:
                        break
                    if k==len(p)-1:
                        p.append(b[i])
        elif p[j]==b[i]:
            if c[a[i]-1]==0:
                c[a[i]-1]=b[i]
                flag+=1
                for k in range(len(p)):
                    if p[j]==a[i]:
                        break
                    if k==len(p)-1:
                        p.append(a[i])
if flag<n-1:
    print('No')
    exit()
print('Yes')
for i in range(1,len(c)):
    print(c[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)

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