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 math
import numpy as np
N, M = (int(i) for i in input().split())  

arr = np.array([[0] * N] * N)

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

lis = [-1] * (N-1)
def recur(bef, visit_list, num):
  all_visited = True
  #print(bef, visit_list)
  tmp_lis = []
  for i, x in enumerate(arr[bef-1]):
    if x and i+1 not in visit_list:
      tmp_lis.append(i+1)
      
  for x in tmp_lis:
    recur(x, visit_list + [bef] + tmp_lis, num+1)
    lis[x - 2] = bef
  all_visited = False
      
  if all_visited:
    return
  
recur(1, [], 0)
#print(lis)
if -1 in lis:
  print('No')
else:
  print('Yes')
  for x in lis:
    print(x)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra
n,m = map(int,input().split())
d = [[0]*n for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    d[a][b] = 1
    d[b][a] = 1
#print(d)
d = dijkstra(d)
#print(d)
li = []
for i in range(1,n):
    for j in range(1,n):
        for k in range(j+1,n):
            if d[i][j] > d[i][k]:
                if d[i][k] + d[0][k] == d[i][0] and k-1!=i:
                    li.append(k)
                    break
            break
       # print(i,j,k,li,d[i][k],d[0][k],d[i][j])
if len(li) == n-1:
    for i in range(len(li)):
        print(li[i])

Submission status: Wrong Answer

Solution code:
import queue

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

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

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

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

  michishirube = {}

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

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

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



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


for i in range(m):
    a[i],b[i] = map(int,input().split())
    route[a[i]-1].append(b[i]-1)
    route[b[i]-1].append(a[i]-1)
for j in range(n):
    if j in route[0]:
        michishirube[j] = 1
    else:
        for k in range(len(route[j])):
            if route[j][k] in route[0]:
                michishirube[j] = (route[j][k]+1)
print("Yes")
for i in range(1,n):
    print(michishirube[i])

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 len(next)!=0:
    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)
        if len(next)==0:
          break
        remcount+=2
    where=numpy.where(array==next[0])[0]
    next.pop(0)

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

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import queue

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

vac = []

room = [vac.copy() for i in range(N+1)]
track = [0] * (N + 1)
lamp = [0] * (N + 1)

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

def explore(address):

    track[address] = 1

    for i in room[address]:
        if track[i] == 0:
            lamp[i] = address
            track[i] = 1

q = queue.Queue()
q.put([1])
count = 0

while count < N:
    count += 1
    r = q.get()
    for i in r:
        explore(i)
        q.put(room[i])

print("Yes")

for i in range(2,N+1):
    print("{}".format(lamp[i]))

Submission status: Wrong Answer

Solution code:
import collections as cl

def bfs(cost, connection_nodes) :
    queue = cl.deque(list(connection_nodes[0]))
    current_cost = 1
    pending_nodes = set()
    visited = set()
    visited.add(0)
    
    while queue :
        a = queue.popleft()
        # print("poped : ", a)
        # if (visited in a) :
        #     continue
        visited.add(a)
        if (current_cost < cost[a]) :
            cost[a] = current_cost
        pending_nodes = pending_nodes | connection_nodes[a] - visited
        # print(pending_nodes)

        if (len(queue) == 0) :
            node = set()
            for pending in pending_nodes :
                # print(connection_nodes[pending])
                node = node | connection_nodes[pending] - visited
            # print("---")
            pending_nodes = set()
            current_cost += 1
            queue = cl.deque(node)

def main() :
    
    N,M = map(int,input().split())
    # N部屋ある各部屋にコストいくつで訪問できるのか(0-index)
    cost = [10**9] * N
    connection_nodes = [set() for i in range(N)]
    for i in range(M) :
        a,b = map(int,input().split())
        # 0-indexにしておく
        a = a-1
        b = b-1

        # つながるノードをまとめておく
        connection_nodes[a].add(b)
        connection_nodes[b].add(a)
    
    cost[0] = 0
    bfs(cost,connection_nodes)
    # print(connection_nodes)
    print("Yes")
    for k in range(1,N) :
        print(cost[k])



main()

Submission status: Wrong Answer

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

for turo in arr:
    left = turo[0]
    right = turo[1]
    if left == 1:
        costheya[right] = [1,1]
    elif right == 1:
        costheya[left] = [1,1]
    else:
        if costheya[left][0] > costheya[right][0]+1:
            costheya[left] = [costheya[right][0]+1,right]
        if costheya[right][0] > costheya[left][0]+1:
            costheya[right] = [costheya[left][0]+1,left]

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

print('Yes')
for i in costheya.values():
    print(i[1])

Submission status: Wrong Answer

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

memo = {1:[0,None]}
for room in arr[1]:
    memo[room] = [1,1]

possible = True 
if len(memo.keys())<2:
    possible = False

visit = arr[1]
while len(visit) > 0:
    index = visit.pop(0)
    for item in arr[index]:
        if item not in memo.keys():
            distance = memo[index][0]
            memo[item] = [distance+1,index]
            visit.append(item)

if possible and len(memo.keys())==n:
    print("Yes")
    memo.pop(1)
    for item in memo.values():
        print(item[1])

Submission status: Wrong Answer

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

n, m = [int(x) for x in 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 all([i != None for i in d]):
    print("Yes")
    for i in range(1,n):
        print(d[i])
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
 
for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

print(graph)

check = [-1]*(N)
check[0] = 0

q = deque([0])

while q:
	#print(q)
	p = q.popleft()
	#print(p, check)
	for x in graph[p]:
		#print(x)
		if check[x] == -1:
			check[x] = p+1
			q.append(x)


if -1 in check:
	print("No")
	exit()
else:
	print("Yes")

for i in range(1, N):
	print(check[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(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
from collections import deque
n,m = map(int,input().split())
G = [set() for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)
ans = [-1 for _ in range(n)]

ans[0]=0
q = deque([0])
q2 = deque()

seen = set()
seen.add(0)

for _ in range(2*n):
    while q:
        q2 = deque()
        #print(ans,q,q2,seen)
        i = q.pop()
        for j in G[i]:
            if j in seen:
                continue
            q2.append(j)
            ans[j] = i+1
            seen.add(j)
            '''if cost[i] ==-1:
                cost[i] = c
                ans[i] = j
            elif cost[i] > cost[j] + 1:
                cost[i] = cost[j] + 1
                ans[i] = j
            else:
                pass'''
    q = q2
    if len(seen) == n:
        print("Yes")
        print(*ans[1:], sep="\n")
        sys.exit()
        
print("No")

Submission status: Wrong Answer

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

ROOP=[[] for i in range(N+1)]
GOAL_start=[]
#部屋2からNまでで、部屋１までの最短経路を出す
#部屋i(2からN)にいるとき、行先は?
for i in range(2,N+1):
	for ab in AB:
		if i ==ab[0]:
			ROOP[i].append(ab[1])

		elif i==ab[1]:
			ROOP[i].append(ab[0])
	if 1 in ROOP[i]:
		GOAL_start.append(i)

#GOALから逆順にDPをしていこう
visited=[-1]*(N+1)

for i in GOAL_start:
	visited[i]=1#１に最も近い地点、GOALの距離

#初期設定
#GOALは,1に距離１でいける場所
#こんな感じの再起関数
print("START")
def bfs(GOAL,GOAL_NEXT):#スタート地点と、そこから行くところ
	print(GOAL,GOAL_NEXT)
	for i in ROOP[GOAL]:
		if i!= GOAL_NEXT and (visited[i]==-1 or visited[i]>1+visited[GOAL]):
			visited[i]=1+visited[GOAL]
			bfs(i,GOAL)
		else:#行先がないとき
			pass
	return 1
bfs(GOAL_start[0],1)

if -1 not in visited[2:]:
	print("Yes")
	for i in visited[2:]:
		print(i)
else:
	print("NO")

Submission status: Wrong Answer

Solution code:
n,m = list(map(int,input().split()))
a = []
res = [0 for i in range(n-1)]
f = False

for i in range(m):
    a1,b1 = list(map(int,input().split()))
    a.append([a1,b1])
    if a1 == 1 or b1 == 1:
        f = True

temp = [1]
temp2 = [1]

if f:
    for l in range(n):
        temp = temp2.copy()
        temp2 = []
        for j in temp:
            for p in [0,1]:
                for q in range(n-1):
                    if a[q][p] == j:
                        if p == 0:
                            temp2.append(a[q][1])
                        else:
                            temp2.append(a[q][0])
            for k in temp2:
                if res[k-2] == 0:
                    res[k-2] = j
        if res.count(0) == 0:
            break
    if res.count(0) == 0:    
        print("Yes")
        for i in res:
            print(i)
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
line1 = input().split()
n = int(line1[0])
m = int(line1[1])

road_map = [[] for i in range(n)]

for i in range(m):
  line = input().split()
  a = int(line[0]) - 1
  b = int(line[1]) - 1
  road_map[a].append(b)
  road_map[b].append(a)
  
current_goal = [0]
route = [-1] * n
none = True
while none:
  goal = current_goal
  current_goal = []
  for i in range(n):
    none = False
    road = road_map[i]
    if route[i] >= 0:
      continue
    dist = -1
    for r in road:
      if r in goal:
        dist = r
    if dist >= 0:
      current_goal.append(i)
      route[i] = dist
      none = True
if min(route) == -1:
  print("No")
else:
  print("Yes")
  for r in route:
    print(r + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

n, m = map(int,input().split())
g =Graph()
for _ in range(m):
    x, y = map(int,input().split())
    g.add_edge(x-1,y-1,1)
d = Dijkstra(g,0)

ans= [float("inf") for i in range(n)]
for i in range(n):
    x = d.shortest_distance(i)
    ans[i] = x
if float("inf") in ans:
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

path = [[] for _ in range(n+1)]
for i in range(m):
    aa, bb = a[i], b[i]
    path[bb].append(aa)
    path[aa].append(bb)
print(path)

ans = [0] * (n+1)
que = deque([[1, 1]])
while len(que) > 0:
    idx = que.popleft()
    if ans[idx[0]] == 0:
        ans[idx[0]] = idx[1]
    for i in path[idx[0]]:
        if ans[i] == 0:
            deque.append(que, [i, idx[0]])

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

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

print("Yes")

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

Submission status: Wrong Answer

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

chizu=[[] for i in range(n+1)]
ans=[0]*(n+1)
ans[1]=-1

for i in range(m):
    chizu[ab[i][0]].append(ab[i][1])
    chizu[ab[i][1]].append(ab[i][0])

kaisu=[chizu[1]]
for i in chizu[1]:
    ans[i]=1

error=0
j=-1
counter=len(chizu[1])
while True:
    j+=1
    if len(kaisu)<=j:
        error=1
        break
    for now in kaisu[j]:#スタートからj+1距離の点たちについて操作
        kari=[]
        for i in chizu[now]:#ある点から隣り合う点決めていく
           if ans[i]==0:#未到達であれば
                ans[i]=now
                kari.append(ans[i])
                counter+=1
        kaisu.append(kari)
    if counter==n-1:
        break

if error==0:
    print("Yes")
    for i in range(2,n+1):
        print(ans[i])
    

elif error==1:
    print("No")

Submission status: Wrong Answer

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

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

A = [x[0] for x in AB]
B = [x[1] for x in AB]


ans = [0] * (N-1)

room_set = set([1])

for _ in range(N):
    room_set_new = set([])
    for i, x in enumerate(A):
        if x in room_set:
            #print("B[i]",i, B[i], x)
            if ans[B[i] - 2] == 0:
                ans[B[i] - 2] = x
            room_set_new.add(B[i])
            del A[i]
            del B[i]
    if(min(ans) != 0):
        break

    for i, x in enumerate(B):
        if x in room_set:
            #print("A[i]",i, A[i], x)
            if ans[A[i] - 2] == 0:
                ans[A[i] - 2] = x
            room_set_new.add(A[i])
            del A[i]
            del B[i]
    if (min(ans) != 0):
        break
    room_set = room_set_new
    #rint("room", room_set)

if(min(ans) == 0):
    print("No")


print("{} ".format('Yes'))
for i in range(N-1):
    print("{} ".format(ans[i]))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
edge = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

#print(edge)

print('YES')

ans = [None]*N
#print(edge)
q = deque([0])

tmp = [-1]*N#部屋１からの距離
tmp[0] = 0

while q:
    now = q.popleft()
    #print(edge[now])
    for v in edge[now]:
        if ans[v] == None:
            ans[v] = now
        if tmp[v] != -1:
            if tmp[now] + 1 < tmp[v]:
                tmp[v] = tmp[now]+1
                ans[v] = now
            continue
        tmp[v] = tmp[now] + 1
        q.append(v)
    #print("ans",ans)
for c in ans[1:]:
    print(c+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd

N,M = map(int,input().split())
A2B = dd(list)
B2A = dd(list)
for a in range(M):
    A,B = input().split()
    A2B[A].append(B)
    B2A[B].append(A)
    
# 探索するノードの一覧
nodes_seek = set([str(x) for x in range(1,N+1)])

# 探索したノードの一覧
disc_nodes = set([])

# 各ノードの最短経路を保管する辞書
shortest_path = dd(list)
# 各ノードの暫定の最短ホップ数を保管する辞書
shops = dd(int)
# 各ノードの最短経路における、手前のノードを記憶する辞書
sprev = dd(str)

# ノード1から順に探索
## ノード1に入った⇒ 隣接する部屋のリスト一覧を取得
nxt_nodes = dd(list)
nxt_nodes["1"] = A2B["1"]
nxt_nodes["1"] += B2A["1"]

## ノード1への距離を0として記入
shops["1"] = 0
shortest_path["1"] = []
sprev["1"]=[]
disc_nodes.add("1")

#取得した隣接リストを使う（が、幅優先で考える）


count = 0

while len(disc_nodes) < N:
    # 現在の隣接リストをあたり、次の隣接ノードのリストを作成する
    nnxt_nodes = dd(list)
    for key in nxt_nodes.keys():
        ## 現在の隣接リストから、すでに見つかったノードを省く
        tnxt_nodes = set(nxt_nodes[key]) - disc_nodes
    
        for n in tnxt_nodes:
            # 現在の隣接リストで見つかったノードについて、
            ## 手前のノードとして、現在のKeyを記入
            shops[n] = shops[key]+1
            sprev[n] = str(key)            
            
            ## 探索済みノードとして追記
            disc_nodes.add(n)
            
            ## 次の隣接リストを取得、記載する
            nnxt_nodes[n] += A2B[n]
            nnxt_nodes[n] += B2A[n]
    nxt_nodes = nnxt_nodes

    count += 1
    if count >100:
        break

ans = 'Yes'
       
# print(" ----------------------- ")    

# for i in range(1,N+1):
#     print("i:",i)
#     print("-- shops --")
#     print(shops[str(i)])
    
#     print("-- sprev --")
#     print(sprev[str(i)])
    

# print("disc_nodes")
# print(disc_nodes)

for i in range(1,N+1):
    if i == 1:
        print(ans)
    else:
#         print(i,sprev[str(i)])
        print(sprev[str(i)])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
d = [[] for i in range(n)]
l = [10 ** 10] * 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 10 ** 10 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))

Submission status: Wrong Answer

Solution code:
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)
    
for i in range(1 , n):
    stack = [i]
    visited = [False]*(n-1)
    ans = 1
    visited[i-1] = True
    while stack:
        v = stack.pop()
        if 0 in G[v]:
            print(ans)
            continue
        for to in G[v]:
            if visited[to-1] is True:
                continue
            stack.append(to)
            visited[to-1] = True

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, m = i_map()
    num_list = []
    for _ in range(m):
        a, b = i_map()
        if a > b:
            a, b = b, a
        tmp = [a-1, b-1]
        num_list.append(tmp)

    print('No')
    exit()

    num_list.sort()
    print(num_list)  

    ans_list = [INF] * n

    for i in range(m):
        if num_list[i][0] == 0:
            ans_list[num_list[i][1]] = num_list[i][0]

    print(ans_list)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
R = [list(map(int, input().split())) for i in range(M)]

F = [1] * N
F[0] = 0
O = [0] * N

Us = [1]
for i in range(N):
    NUs = []
    for j in R:
        for U in Us:
            if j[0] == U and F[j[1] - 1] == 1:
                F[j[1] - 1] = 0
                O[j[1] - 1] = U
                NUs.append(j[1])
            if j[1] == U and F[j[0] - 1] == 1:
                F[j[0] - 1] = 0
                O[j[0] - 1] = U
                NUs.append(j[0])
    Us = NUs

if np.prod(F):
    print('no')
else:
    print('yes')
    for i in O:
        print(i)

Submission status: Wrong Answer

Solution code:
import copy
N, M = map(int,input().split())
roads = list()
for i in range(M):
    a ,b = map(int,input().split())
    roads.append([a,b])

marks = dict()
class Route:
    def __init__(self):
        self.w = ''

    def route(self,n, roads, w):
        for r in roads:
            if r[0] == n:
                num = r[1]
            elif r[1] == n:
                num = r[0]
            else:
                continue
            if num == 1:
                if len(w + '1') < len(self.w) or len(self.w) == 0:
                    self.w = w + '1'
            else:
                roads_ = copy.deepcopy(roads)
                roads_.remove(r)
                self.route(num,roads_, w + str(num))

route = Route()
dirs = dict()
ret = list()
ans = 'Yes'
for i in range(2, N + 1):
    if ans == 'No':
        break
    route.w = ''
    route.route(i,roads,str(i)) 
    for j in range(len(route.w)-1):
        if route.w[j] not in dirs.keys():
            dirs[route.w[j]] = set()
        dirs[route.w[j]].add(route.w[j+1])
        if len(dirs[route.w[j]]) > 1:
            ans = 'No'
            break
        if j == 0:
            ret.append(route.w[j+1])

ans = 'Yes'
if ans == 'No':
    print(ans)
else:
    print(ans)
    for i in ret:
        print(i)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
import sys
import math
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations, combinations_with_replacement
from itertools import accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil,floor
from copy import deepcopy
from heapq import heappop,heappush,heapify
import heapq


# def combinations(n, r):
# 	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# def gcd(a, b):
# 	if b == 0:
# 		return a
# 	else:
# 		return gcd(b, a%b)
 
# def lcm(a, b):
# 	return a // gcd(a, b) * b

# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))


N,M = MI()
A = []
B = []
for _ in range(M):
	a,b = MI()
	A.append(a)
	B.append(b)

d = defaultdict(int)
ref_list = [''] * N

for aa, bb in zip(A,B):
	ref_list[bb-1] += str(aa)
	ref_list[aa-1] += str(bb)

memo = []

def rec(i, done, num):
	memo.append(str(i)+':'+str(num))
	if d[str(i)]==0:
		d[str(i)] = num
	else:
		d[str(i)] = min(num, d[str(i)])
	candidate = list(set(ref_list[int(i)-1]))
	candidate = [c for c in candidate if not c in done]
	new_done = done+candidate
	for c in candidate:
		if not c in done and not str(c)+':'+str(num+1) in memo:
			rec(c, new_done, num+1)
	return


rec(1, ['1'], 10)

ans = []
for i in range(1,N):
	d_i = d[str(i+1)]
	for target in list(set(ref_list[i])):
		if d[str(target)] == d_i -1:
			ans.append(target)
			break

if len(ans)==N-1:
	print('Yes')
	for f in ans:
		print(f)
else:
	print('No')