Problem:


Score: 400 points

Problem Statement

There is a cave.

The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.

It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.

Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.

If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.

Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 2 \times 10^5

1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)

A_i \neq B_i\ (1 \leq i \leq M)

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

If there is no way to place signposts satisfying the objective, print No.

Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

If we place the signposts as described in the sample output, the following happens:

Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.

Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.

Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.

Thus, the objective is satisfied.

Sample Input 2

6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6

Sample Output 2

Yes
6
5
5
1
1

If there are multiple solutions, any of them will be accepted.



Sample input:
4 4
1 2
2 3
3 4
4 2


Sample output:
Yes
1
2
2

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = 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]] == 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[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

path = []

class Node:
 """ノード
 """
 def __init__(self, name):
   self.name = name
   self.visited = False
   self.adjacent = []

def bfs(root):
 if root is None:
   return 

 q = deque()
 visit(root)
 q.append(root)
 while q:
   r = q.pop()
   for n in r.adjacent:
     if not n.visited:
       visit(n)
       q.append(n)

def visit(node):
 path.append(node.name)
 node.visited = True

if __name__ == "__main__":
    n, m = map(int, input().split())
    nodes = [Node(i) for i in range(1, n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        nodes[a-1].adjacent.append(nodes[b-1])
        nodes[b-1].adjacent.append(nodes[a-1])
        
    bfs(nodes[0])
    #print(path)
    
    if len(path) == n:
        print("Yes")
        dic = {}
        for i in range(1, len(path)):
            dic[path[i]] = path[i-1]
        for i in range(2, n+1):
            print(dic[i])
    else:
        print("No")

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)
if float('inf') in l:
    print('No')
    exit()
else:
    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())
A = [0 for i in range(M)]
B = [0 for i in range(M)]
KOTAE = [0 for i in range(N)]
HOZON = [1]
HOZON2 = []
HOZON3 = []
for i in range(M):
    A[i],B[i] = map(int,input().split())
S = 0
for j in range(M):
    for i in range(M):
        if A[i] in HOZON and not(A[i] in HOZON2  or A[i] in HOZON3 or B[i] in HOZON or B[i] in HOZON2 or B[i] in HOZON3):
            HOZON2.append(B[i])
            KOTAE[B[i]-1] = A[i]
        elif B[i] in HOZON and not(A[i] in HOZON or A[i] in HOZON2  or A[i] in HOZON3 or B[i] in HOZON2 or B[i] in HOZON3):
            HOZON2.append(A[i])
            KOTAE[A[i]-1] = B[i]
    HOZON3.extend(HOZON)
    HOZON = HOZON2
    HOZON2 = []
    if len(HOZON3) == N:
        break
for i in range(N):
    print(KOTAE[i])

Submission status: Wrong Answer

Solution code:
#d
n,m=map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
maze = []
inf = 9999999
dist = [inf]* n
dist[0] = 0
queue = []
answer = [0]*n

goto = [[] * 1 for i in range(n)]
for i in range(len(ab)):
    goto[ab[i][0]-1].append(ab[i][1]-1)
    goto[ab[i][1]-1].append(ab[i][0]-1)

queue.extend([0])

while queue != []:
    go = queue.pop()
    for h in goto[go]:
        if dist[h] == inf:
            queue.append(h)
            dist[h] = dist[go]+1
            answer[h] =go+1
            
print("Yes")
for i in answer[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
import networkx as nx
n,m=map(int,input().split())
g = nx.Graph()
l = sys.stdin.readlines()
for x in l:
    g.add_edge(int(x.split(' ')[0]), int(x.split(' ')[1].strip()))

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
# -*- coding:utf-8 -*-
from collections import deque

def get_route(pathways, routes, visited, start):
    queue = deque([start])
    while queue:
        now = queue.popleft()
        visited[now-1] = True
        for src, dest in filter(lambda x:x[0] == now and routes[x[1]-1] == 0, pathways):
            routes[dest-1] = now
            visited[dest-1] = True
            queue.append(dest)
        if all(visited): return routes
    return routes

def main():
    N, M = map(int, input().split())
    pathways = []
    for _ in range(M):
        A, B = map(int, input().split())
        pathways.append([A, B])
        pathways.append([B, A])
    ans_route = get_route(pathways, [0] * N, [False] * N, 1)
    if 0 in ans_route: print("No")
    else:
        print("Yes")
        for x in ans_route[1:]: print(x)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# = int(input())
N, M = map(int, input().split())
# = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
AB = [list(map(int, input().split())) for i in range(M)]
sign = [0]*(N-1)
ilist=[]

for i in range(M):
    if AB[i][0] == 1:
         sign[AB[i][1]-2] = 1
         ilist.append(i)
    elif AB[i][1] == 1:
         sign[AB[i][0]-2] = 1
         ilist.append(i)
for i in range(len(ilist)):
    del AB[ilist[i]-i]
ilist = []
length = len(AB)
#print(AB)

for i in range(length):
    if sign[AB[i][0]-2] == 1 and sign[AB[i][1]-2] != 1:
        sign[AB[i][1]-2] = AB[i][0]
        ilist.append(i)
    elif sign[AB[i][1]-2] == 1 and sign[AB[i][0]-2] != 1:
        sign[AB[i][0]-2] = AB[i][1]
        ilist.append(i)
for i in range(len(ilist)):
    del AB[ilist[i]-i]
ilist = []
length = len(AB)

for i in range(1000):
    for i in range(length):
        if sign[AB[i][0]-2] != 0 and sign[AB[i][1]-2] == 0:
            sign[AB[i][1]-2] = AB[i][0]
            ilist.append(i)
        elif sign[AB[i][1]-2] != 0 and sign[AB[i][0]-2] == 0:
            sign[AB[i][0]-2] = AB[i][1]
            ilist.append(i)
    for i in range(len(ilist)):
#        print(ilist)
        del AB[ilist[i]-i]
#        print(AB)
    ilist = []
    if len(AB) == length:
        break
    else:
        length = len(AB)
#        print(length)

if sign.count(0) > 0:
    print("No")
else:
    print("Yes")
    for number in sign:
        print(number)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

graph = defaultdict(set)

for _ in range(m):
    a, b = list(map(int, input().split()))
    graph[a].add(b)
    graph[b].add(a)

# 幅優先探索
# https://qiita.com/drken/items/4a7869c5e304883f539b
seen = [False for _ in range(n + 1)]  # 既に道しるべを設置したか? # idx 0 は使わない
todo = set()  # 検知したけどまだ探索してない
ans = defaultdict(int)
seen[1] = True
todo.update(graph[1])
for d in graph[1]:
    ans[d] = 1  # 1と繋がってる部屋の道しるべは1
    seen[d] = True
# 出発ノード
while len(todo) > 0:
    for v in todo:
        todo_next = set()
        for d in graph[v]:
            if seen[d]:
                continue
            seen[d] = True
            todo_next.add(d)
            ans[d] = v
        todo = todo_next

if not all(seen[1:]):
    print("No")
    exit()

print("Yes")
for i in range(2, n + 1):
    print(ans[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) + list(ABs.T[1]-1)
col = list(ABs.T[1]-1) + list(ABs.T[0]-1)
data = [1] * (2 * M)

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

Submission status: Wrong Answer

Solution code:
import collections

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

# 隣の部屋の辞書
# node2nb_dict = {i + 1: [] for i in range(N)}  # 2 * 10** 5
node2nb_dict = collections.defaultdict(lambda: [])

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

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


def f(next_targets, node_a):
    w_next_targets = {}
    for node in next_targets:
        # 巡回済みノードの更新
        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:
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())
a_b = [[] for _ in range(M)]
A = [0]*M
B = [0]*M
for i in range(M):
    a_b[i] = list(map(int, input().split()))
    A[i] = a_b[i][0]
    B[i] = a_b[i][1]


ans = [-1] * N
check = []
check.append(1)
memo = []

while True:
    memo = []
    for num in check:
        if num in A:
            list_a = [i for i, x in enumerate(A) if x == num]
            for index_a in list_a:
                if ans[B[index_a]-1] == -1:
                    ans[B[index_a]-1] = num
                    memo.append(B[index_a])
            list_b = [i for i, x in enumerate(B) if x == num]
            for index_b in list_b:
                if ans[A[index_b]-1] == -1:
                    ans[A[index_b]-1] = num
                    memo.append(A[index_b])
    if len(memo) == 0:
        break
    check = memo

if -1 in ans:
    print("No")
else:
    print("Yes")
    for j in ans[1:]:
        print(j)

Submission status: Wrong Answer

Solution code:
def main():
  from collections import deque
  n,m=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  
  if not ab[1]:
    print('No')
    exit()
  
  l=deque([1])
  ans=[-1]*n
  for _ in range(n+2):
    if l:
      x=l.popleft()
      for i in ab[x]:
        if i in l:
          continue
        l.append(i)
        ans[i-1]=x if ans[i-1]<0 else ans[i-1]
    else:
      break
  ans.sort()
  if ans[1]>=0:
    print('Yes')
    for i in ans[1:]:
      print(i) 
  else:
    print('No')
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

N = int(N)
M = int(M)

neighbor_dict = {}
wait = {}
done = {}
michisirube_dict = {}

for i in range(N):
	neighbor_dict[i+1] = []
	wait[i+1] = False
	done[i+1] = False
	michisirube_dict[i+1] = None

for i in range(M):

	A, B = input().split(" ")
	A = int(A)
	B = int(B)
	neighbor_dict[A].append(B)
	neighbor_dict[B].append(A)


def set_michisirube(room, neighbors):
	for neighbor in neighbors:
		if michisirube_dict[neighbor] is None:
			michisirube_dict[neighbor] = room
		else:
			pass
	return neighbors



neighbors = set_michisirube(1, neighbor_dict[1])
for neighbor in neighbors:
	set_michisirube(neighbor, neighbor_dict[neighbor])

if None in list(michisirube_dict.values()):
	print("No")
else:
	print("Yes")

	for i in range(N-1):
		print(michisirube_dict[i+2])

Submission status: Wrong Answer

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

ans = [-1] * (N+1)
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

for i in range(N+1):
    graph[i].sort()
    
from collections import deque
todo = deque([(1,0)])
while todo:
    x,parent = todo.pop()
    ans[x] = parent
    for y in graph[x]:
        if y == parent:
            continue
        if ans[y] != -1:
            continue
        todo.append((y,x))
            
if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in range(2,N+1):
        print(ans[i])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

import networkx as nx

YES = "Yes"  # type: str
NO = "No"


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()
    G.add_nodes_from([1+n for n in range(N)])

    G.add_edges_from([(a,b) for a,b in zip(A,B)])

    paths = nx.predecessor(G, 1, cutoff=N//2)

    print(YES)

    ans_list = []
    for key, val in sorted(paths.items()):
        if key != 1:
            print(val[0])
            # ans_list.append((key,val[0]))

    # ans_list.sort(key=lambda x: x[0])
    # for key, val in ans_list:
    #     print(val)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 標準入力の取得
N, M = list(map(int, input().split()))
A, B = [], []
for m in range(M):
    A_m, B_m = list(map(int, input().split()))
    A.append(A_m)
    B.append(B_m)

# 求解処理
paths = [list() for n in range(N)]
for A_m, B_m in zip(A, B):
    paths[A_m-1].append(B_m)
    paths[B_m-1].append(A_m)


rooms = [1 if n == 0 else 0 for n in range(N)]
was_written = [True if n == 0 else False for n in range(N)]
for n in range(N):
    path = paths[n]
    for room in path:
        if not was_written[room-1]:
            rooms[room-1] = n + 1
            was_written[room-1] = True


if False in was_written:
    print("No")
else:
    print("Yes")
    rooms = rooms[1:]
    for room in rooms:
        print(room)

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
  return 0

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)]

for i in combinations:
  l = 0
  t = len(i)
  for j in range(2, t+1):
    l = l+cango(i,j)
  if l == t-1:
    print("Yes")
    for j in range(1,t):
      print(i[j+1])
    sys.exit()
      
print("No")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
G = [[] for _ in range(N+1)] # 探索するためのグラフ行列
for i in range(M):
    #A[i] , B[i] = map(int,input().split())
    a,b = map(int,input().split())
    # こうすることでインデックスが各部屋に，その要素が繋がっている部屋になる！
    G[a].append(b)
    G[b].append(a)

# あとは探索するだけ，時間内にできるかなぁ
#print(G) #[[], [2], [1, 3, 4], [2, 4], [3, 2]]

flag = True
dir = [0]*(N-1) # 道標の値
for i in range(1,N+1):
    #print(G[i])
    # if i == 1:#1と直接繋がっている部屋は１回いでいける
    #     dir[i-2] = 1
    if 1 in G[i]:#G内に1があったら，部屋１への道ある
        dir[i-2] = 1

        for j in range(len(G[i])):
            dir[G[i][j]-2] = 2
    

for k in dir: #dirのなかに０あったら道しるべおけない
    #print(dir)
    if k == 0:
        flag = False
        print(dir)
    

        

if flag:
    print("Yes")
    for i in range(len(dir)):
        print(dir[i])
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d[-1]

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

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

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

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


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

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

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

temp = set(ans)
print("No")

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

flag = True
while flag:
    flag = False
    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
            elif room_move_count_list[i] == 999999:
                flag = True
            
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:
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(G)
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:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import itertools

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

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

for v in itertools.combinations(p, n-1): #n-1本の道で、全ての場所から辿り着けるか
    l = [[0]*n for i in range(n)]
    #重み1の隣接行列
    for pi in v:
        l[pi[0]-1][pi[1]-1] = 1
        l[pi[1]-1][pi[0]-1] = 1
    l = np.array(l)
    
    d, p = shortest_path(l, return_predecessors=True)
    
    #経路取得
    x = []
    for i in range(1,n):
        x.append(get_path(0, i, p))

    if x.count([]) == 0:
        print("Yes")
        ans = d[0][1:]
        for i in ans:
            print(int(i))
        exit()

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]] == 0:
      ans[AB[0]] = AB[1]
    elif ans[AB[1]] == 0:
      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]] == 0:
    ans[AB[0]] = AB[1]
  elif ans[AB[1]] == 0:
    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:
N,M = map(int,input().split())

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

if len(r[0])  == 0:
    print("No")
    exit()

print("Yes")

for i in range(N):
    r[i].sort()

#print(r)
from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None]*N
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in r[v]:
            if d[i] is None:
                d[i] = d[v]+1
                queue.append(i)
    
    return d

d = bfs(0)

for i in range(1,len(d)):
    print(d[i])

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
#A = []
#B = []
tree = [[]] * N

for i in range(M):
    tempA,tempB = map(int, input().split())
    #A.append(tempA)
    #B.append(tempB)
    tree[tempA - 1] = tree[tempA - 1]+[tempB]
    tree[tempB - 1] = tree[tempB - 1]+[tempA]

answer = ["Yes"]

try:
    for i in range(N):
        for i2,v in enumerate(tree):
            if i + 1 in v:
                answer.append(i2 + 1)
                break
    for i in answer:
        print(i)
except:
    print("No")

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 = set()
        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 = 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:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
g = [[] for _ in range(n)] 

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0 
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d
d = bfs(0)
if None in d:
    print("No")
else:
    print("Yes")
    d.remove(0)
    [print(i) for i in d] #要素を縦に出力

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
a=[]
b=[]
for i in range(M):
	A,B=map(int, input().split())
	a+=[A]
	b+=[B]

kishutsu=[]
current=[1]
ans=[0]*N

while len(set(kishutsu))!=N:
	newnodes=[]
	for i in current:
		destination=[]
		a_dest=[j for j, x in enumerate(a) if x==i]
		for val in a_dest:
			destination+=[b[val]]
		
		b_dest=[j for j, x in enumerate(b) if x==i]
		for val in b_dest:
			destination+=[a[val]]
		
		for node in destination:
			if node not in kishutsu:
				ans[node-1]=i
				newnodes+=[node]
	
	kishutsu+=current
	current=newnodes

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

Submission status: Wrong Answer

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

print('No')

Submission status: Wrong Answer

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

ar = [0]*(N+1)

for _ in range(M):
  a,b = map(int,input().split())
  if ar[a] != 0:
    ar[a] = min(ar[a],b)
  else:
    ar[a] = b
  if ar[b] != 0:
    ar[b] = min(ar[b],a)
  else:
    ar[b] = a

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

Submission status: Wrong Answer

Solution code:

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
R = [0] * N
P = 0
S = [1]
Stmp = []
while True:
    for i in range(M):
        for s in S:
            if AB[i][0] == s:
                R[AB[i][1] - 1] = s
                Stmp.append(AB[i][1])
                AB[i] = [0, 0]
                P += 1
            elif AB[i][1] == s:
                R[AB[i][0] - 1] = s
                Stmp.append(AB[i][0])
                AB[i] = [0, 0]
                P += 1
    S = Stmp
    Stmp = []
    print(R, P)
    if P > N - 1:
        break
print('Yes')
for i in range(1, N):
    print(R[i])

Submission status: Wrong Answer

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

room = {}
startRoom = {1:1}

for i in range(M):
  A, B = map(int,input().split())
  room.setdefault(A, []).append(B)
  room.setdefault(B, []).append(A)
  
#print(room)
targetRoom = [1]
while len(targetRoom) != 0:
  nextTarget = []
  for i in targetRoom:
    roomList = room[i]
    for j in roomList:
      if j not in startRoom:
        startRoom[j] = i
        nextTarget.append(j)
  targetRoom = nextTarget
  
#print(startRoom)
if len(startRoom) != N:
  print("no")
else:
  print("yes")
  for i in range(2, N+1):
    print(startRoom[i])

Submission status: Wrong Answer

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

paths = [tuple(map(int, input().split())) for _i in range(m)]
paths.extend([(e[1], e[0]) for e in paths])
paths = sorted(paths, key=lambda x: x[0])

shirube = [0] * n

for f, t in paths:
    temp_path = shirube[f - 1] + 1

    if shirube[t - 1] == 0 or temp_path < shirube[t - 1]:
        shirube[t - 1] = temp_path

if all([e != 0 for e in shirube[1:]]):
    print("Yes")
else:
    print("No")

for e in shirube[1:]:
    print(e)