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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)
# hex_str = hex(i)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	wuf = UnionFind(N)

	oya = [[] for i in range(N)]

	for i in range(M):
		A,B = inputMap()
		A -= 1
		B -= 1
		wuf.union(A, B)

	for i in range(N):
		if wuf.is_same(0, i) == True:
			pass
		else:
			print("No")
			sys.exit()

	print("Yes")





class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		self.size = [1 for _ in range(n)]

	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			# メンバ数の更新
			sum = self.size[x] + self.size[y]
			self.size[x] = sum
			self.size[y] = sum
			# 短いリストを長いリストのルートに繋ぎ直す
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x

	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	# x が属するグループのメンバ数を返却
	def getSize(self, x):
		par_x = self.find(x)
		return self.size[par_x]


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
inf = 10 ** 7
N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]
a = [[] for i in range(N)]
for i in P:
    a[i[0]-1].append(i[1]-1)
    a[i[1]-1].append(i[0]-1)
path = [-1] * N
path[0] = 0
checked = [False] * N
stack = [(0,0)]
while (len(stack) != 0):
    kk = stack.pop()
    now = kk[0]
    pre = kk[1]
    nextP = a[now]
    checked[now] = True
    path[now] = pre
    for i in nextP:
        if not checked[i]:
            stack.append((i,now))
if False in checked:
    print("No")
else:
    print("Yes")
    for i in path[1:]:
        print(i + 1)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict


def main():
    N, M = map(int, input().split())
    A_B = [list(map(int, input().split())) for _ in range(M)]
    inf = float('inf')

    # distances = [[0 if i == j else inf for j in range(N + 1)] for i in range(N + 1)]
    signs = [-1 for _ in range(N + 1)]
    dists = [N for _ in range(N + 1)]

    path = [(a, b) if a <= b else (b, a) for a, b in A_B]

    for a, b in sorted(A_B):
        if a == 1:
            dists[b] = 1
            signs[b] = 1
        elif b == 1:
            dists[a] = 1
            signs[a] = 1
        else:
            if dists[a] - dists[b] > 1:
                dists[a] = dists[b] + 1
                signs[a] = b
            elif dists[b] - dists[a] > 1:
                dists[b] = dists[a] + 1
                signs[b] = a
            else:
                pass

    print(dists)
    print(signs)

    print('Yes')
    for s in signs[2:]:
        print(s)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 常備セット
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf


n,m = imap()
ab = np.array([iarr()+[1] for i in range(m)])
a,b,c = ab.T[0]-1, ab.T[1]-1, ab.T[2]

adja = [[] for i in range(n)]
for i in range(m):
    aa,bb = a[i],b[i]
    adja[aa].append(bb)
    adja[bb].append(aa)
    
graph = sps.csr_matrix((c,(a,b)), (n,n)) #a,b,cはvector
dk = sps.csgraph.dijkstra(graph,directed=0,indices=0).astype(int)

print("Yes")
for i in range(1,n):
    option = adja[i]
    min = np.inf
    ans = -1
    for num in option:
        if dk[num] < min: ans = num; min = dk[num]
    print(ans+1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque,defaultdict

N, M = [int(x) for x in stdin.readline().rstrip().split()]

par = [i for i in range(N+1)]
rank = [0] * (N+1)
size = [1] * (N+1)


def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
        size[y] += size[x]
        size[x] = 0

    else:
        par[y] = x
        size[x] += size[y]
        size[y] = 0
        if rank[x] == rank[y]:
            rank[x] += 1


def check_same(x, y):
    return find(x) == find(y)


def check_size(x):
    return size[find(x)]



from collections import defaultdict
adj = defaultdict(set)

for _ in range(M):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    union(A, B)
    adj[A].add(B)
    adj[B].add(A)
 
if len(set(par[1:])) == 1:
    print("Yes")
    ans = [0]*(N+1)
    visit_p = deque()
    visit_p.append((1,0))
    visited = [False]*(N+1)
    visited[1] = True
    dist = [10**18]*(N+1)
    
    while visit_p:
        now_v,distance = visit_p.popleft()
        for v in adj[now_v]:
            if visited[v]:
                continue
            
            if distance < dist[v]:
                ans[v] = now_v
            dist[v] = min(dist[v],distance)
            
            
            visited[v] = True
            visit_p.append((v,1+distance))

    for k in ans[2:]:
      print(k)
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

line = [[] for _ in range(N+1)]
flag = True
ans = [0] * (N+1)

for A,B in AB:
    line[A].append(B)
    line[B].append(A)

def bfs(now):
    que = deque()
    que.append(now)
    while que.__len__() != 0:
        now = que.popleft()
        for ne in line[now]:
            if ans[ne] != 0:
                continue
            ans[ne] = ans[now]+1
            que.append(ne)

bfs(1)
if 0 in ans[2:]:
    print('No')
else:
    print('Yes')
    print("\n".join(str(i) for i in ans[2:]))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
way = [[float('inf') for _ in range(N)] for _ in range(N)]
ans = [0]*N

for i in range(N):
    way[i][i] = 0

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

for i in range(N):
    for j in range(N):
        if way[i][0] > way[i][j]+way[j][0]:
            ans[i] = j
            way[i][0] = way[i][j]+way[j][0]

for i in range(1, N):
    print(ans[i]+1)

Submission status: Wrong Answer

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

    que.append(1)
    while(len(d) < n):
        if len(que) == 0:
            print("No")
            return

        label = que.pop(0)
        for i, p in enumerate(par):
            if label in p:
                que.append(i + 1)
                d[i + 1] = label

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

resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(n,dict):
    que = deque()
    distance = [-1 for _ in range(n)]
    que.append([1,0])
    while(len(que) > 0):
        tmp = que.popleft()
        now = tmp[0]
        step = tmp[1]
        if distance[now-1] == -1:
            distance[now-1] = step
            for x in dict[now-1]:
                que.append([x,step+1])
        else:
            continue
    return distance

def main():
    n,m = map(int,input().split())
    L = [list(map(int,input().split())) for _ in range(m)]
    dict = [[] for _ in range(n)]
    for l in L:
        dict[l[0]-1].append(l[1])
        dict[l[1]-1].append(l[0])
    result = bfs(n,dict)
    S = set(result)
    if -1 in S:
        print("No")
    else:
        print("Yes")
        for x in result[1:]:
            print(x)
main()

Submission status: Wrong Answer

Solution code:
# 常備セット
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf


n,m = imap()
ab = np.array([iarr()+[1] for i in range(m)])
a,b,c = ab.T[0]-1, ab.T[1]-1, ab.T[2]

adja = [[] for i in range(n)]
for i in range(m):
    aa,bb = a[i],b[i]
    adja[aa].append(bb)
    adja[bb].append(aa)
    
graph = sps.csr_matrix((c,(a,b)), (n,n)) #a,b,cはvector
dk = sps.csgraph.dijkstra(graph,directed=0,indices=0).astype(int)

for i in range(1,n):
    option = adja[i]
    min = np.inf
    ans = -1
    for num in option:
        if dk[num] < min: ans = num; min = dk[num]
    print(ans+1)

Submission status: Wrong Answer

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

import numpy as np
stack = [[] for j in range(n)]
value = np.ones(n) * 1000000
ans = np.zeros(n)
# print(stack)
for i in link:
    stack[i[0]-1].append(i[1]-1)
    stack[i[1]-1].append(i[0]-1)
# print(stack)
value[0] = 0
for i in range(n):
    for j in stack[i]:
        # print('ye',i,j)
        if value[j] > value[i]+1:
            ans[j] = i+1
        value[j] = min(value[j],value[i]+1)
        
for i in range(n):
    for j in stack[i]:
        # print('ye',i,j)
        if value[j] > value[i]+1:
            ans[j] = i+1
        value[j] = min(value[j],value[i]+1)

# print(value)
print('Yes')
for i in ans[1:]:
    print(int(i))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = {}
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in X:
        X[a].append(b)
    else:
        X[a] = [b]

    if b in X:
        X[b].append(a)
    else:
        X[b] = [a]

ans = [0 for _ in range(N)]
ans[0] = 1
que = [[1, X[0]]]
while len(que) > 0:
    dist, targets = que.pop(0)
    for t in targets:
        if ans[t] == 0:
            ans[t] = dist
            que.append([dist + 1, X[t]])

if 0 in ans:
    print("No")
else:
    print("Yes")
    for a in ans[1:]:
        print(a)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[0]*M
B=[0]*M
for i in range(M):
	A[i],B[i]=map(int,input().split())
list=[0]*N
mitisirube=[0]*N
dest=[0]*M
pren=0
def voiddelete(x):
	i=len(x)-1
	while(x[i]==0):
		del x[i]
		i-=1
	return(x)
def voidcount(x):
	for i in range(len(x)):
		if(x[i]==0):
			break
	return(i)
def move(pren,n):
	mitisirube[n-1]=pren
	list[voidcount(list)]=n
	dest=[0]*M
	for i in range(M):
		if(A[i]==n):
			if(not B[i] in dest):
				dest[voidcount(dest)]=B[i]
		if(B[i]==n):
			if(not A[i] in dest):
				dest[voidcount(dest)]=A[i]
	dest=voiddelete(dest)
	for i in range(len(dest)):
		if(not dest[i] in list):
			move(n,dest[i])
move(0,1)
list=voiddelete(list)
del mitisirube[0]
if(len(list)==N):
	print('Yes')
	print(*mitisirube,sep='\n')
else:
	print('No')

Submission status: Wrong Answer

Solution code:
import networkx as nx

N, M = map(int,input().split())
AB = []
G = nx.Graph()
[G.add_node(i + 1) for i in range(N)]

for _ in range(M):
    A, B = map(int,input().split())
    G.add_edge(A, B)

flag = 1
print_str = 'Yes\n'
for i in range(2, N + 1):
    haspath = nx.has_path(G, source = 1, target = i)
    
    if haspath == False:
        flag = 0
        break
    else:
        ans = len(nx.shortest_path(G, source = 1, target = i)) - 1
        print_str += str(ans)
        if i != N:
            print_str += '\n'
        
if flag == 1:
    print(print_str)
else:
    print('No')

Submission status: Wrong Answer

Solution code:

from collections import deque
def q4():
    class Room:
        def __init__(self, i):
            self.id = i
            self.d = -1
            self.next = []
            self.sign = -1

        def add_next(self, n):
            self.next.append(n)

        def print(self, tab=0, printed=[]):
            if self.id in printed:
                return
            printed.append(self.id)
            print("  " * tab + str(self.id) + f"({self.sign})")
            for n in self.next:
                n.print(tab + 1, list(printed))
    
        
    N, M = [int(i) for i in input().split(" ")]
    room_dict = {}

    def get_room(i):
        if i in room_dict:
            return room_dict[i]
        else:
            room = Room(i)
            room_dict[i] = room
            return room

    for i in range(M):
        A, B = [int(i) for i in input().split(" ")]
        get_room(A).add_next(get_room(B))
        get_room(B).add_next(get_room(A))


    d = 0
    sign = -1
    queue = deque([[get_room(1), d, sign]])
    while queue:
        room, d, sign = queue.popleft()
        if room.sign != -1:
            continue
        room.sign = sign
        room.d = d
        for n in room.next:
            queue.append([n, d + 1, room.id])

    for i in range(2, N + 1):
        print(get_room(i).sign)

q4()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
AB = []
d = defaultdict(set)
for _ in range(M):
    a, b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
    AB.append([a, b])

ans = [0] * N
ans[0] = -1
a = [1]
dis_to_goal = [0] * N
dis_to_goal[0] = 0
dis = 0
mem = set()
while True:
    b = []
    dis += 1
    for k in a:
        if k in mem:
            continue
        mem.add(k)
        print(k)
        for n in d[k]:
            if ans[n - 1] == 0:
                ans[n - 1] = k
                dis_to_goal[n - 1] = dis
                b.append(n)
    if len(mem) == N:
        break
    a = b.copy()

#print(ans)
#print(dis_to_goal)

for i, u in enumerate(ans[1:]):
    if dis_to_goal[i+1] - dis_to_goal[u-1] == 1:
        continue
    else:
        print('No')
        exit()
print('Yes')
for k in ans[1:]:
    print(k)

Submission status: Wrong Answer

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

egde = {}
distance = {}

for i in range(1,N+1):
    egde[i] = []
    distance[i] = -1

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


heres = [1]
distance[1] = 0
dist = 1
while(True):
    next_heres = set()
    for here in heres:
        for i in egde[here]:
            if distance[i] == -1:
                distance[i] = dist
            for j in egde[i]:
                if distance[j] == -1:
                    next_heres.add(j)
    if len(next_heres) == 0:
        break
    heres = next_heres
    dist += 1

if -1 not in set(distance.values()):
    print("Yes")
    for i in range(2,N+1):
        print(distance[i])
else:
    print("No")

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)]
for i in range(M):
  A[i] , B[i] = map(int , input().split())

direction = [N for i in range(N)]
point = [N for i in range(N)]
Atemp = [A[i] - 1 for i in range(M)]
Btemp = [B[i] - 1 for i in range(M)]
for i in range(M):
  if A[i] == 1:
    direction[Btemp[i]] = 1
    point[Btemp[i]] = 1
  if B[i] == 1:
    direction[Atemp[i]] = 1
    point[Atemp[i]] = 1
step = 1
k=1
unko = [i for i in range(M)]
while k != 0:
  k = 0

  for i in unko:
    a = point[Atemp[i]]
    b = point[Btemp[i]]
    m = min([a, b])
    if m == step and a != b:
      if a == m:
        direction[Btemp[i]] = A[i]
        point[Btemp[i]] = m+1
      if b == m:
        direction[Atemp[i]] = B[i]
        point[Atemp[i]] = m+1
      unko.remove(i)  
      k += 1

  step += 1
print('Yes')
for i in range(N - 1):
  print(str(direction[i + 1]))

Submission status: Wrong Answer

Solution code:



# print('input >>')
N, M = map(int,(input().split()))
ABs = [map(int,(input().split())) for _ in range(M)]

INF = 10 ** 10
ds = [INF] * (N+1)
marks = [0] * (N+1)

nodes = [None] * (N+1)

for AB in ABs:
    A, B = AB
    if nodes[A] is None:
        nodes[A] = []
    nodes[A].append(B)

    B, A = A, B
    if nodes[A] is None:
        nodes[A] = []
    nodes[A].append(B)

# print(nodes)

checked = [0] * (N+1) 

def dfs(cur, parent, children):
    # print(parent, children)
    if checked[parent] == 1:
        return
    checked[parent] = 1
    for child in children:
        # print(child)
        if marks[child] == 0:
            marks[child] = parent
            # print(marks)
    dfs(cur+1, child, nodes[child])

dfs(0, 1, nodes[1])

# print('-----output-----')
print('Yes')
for mark in marks[2:]:
    print(mark)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b)
    g[b-1].append(a)
d = [0]*(n-1)
check = [0]*n
check[0] = 1
def bfs():
    q = deque()
    q.append(1)
    
    while q:
        room = q.pop()
        for nroom in g[room-1]:
            if check[nroom-1]==0:
                d[nroom-2] = room
                check[nroom-1] = 1
                q.append(nroom)

bfs()
print('Yes')
for i in range(n-1):
    print(d[i])

Submission status: Wrong Answer

Solution code:
import queue 

def minEdgeBFS(edges, u, v, n): 
	
	# visited[n] for keeping track 
	# of visited node in BFS 
	visited = [0] * n 

	# Initialize distances as 0 
	distance = [0] * n 

	# queue to do BFS. 
	Q = queue.Queue() 
	distance[u] = 0

	Q.put(u) 
	visited[u] = True
	while (not Q.empty()): 
		x = Q.get() 
		
		for i in range(len(edges[x])): 
			if (visited[edges[x][i]]): 
				continue

			# update distance for i 
			distance[edges[x][i]] = distance[x] + 1
			Q.put(edges[x][i]) 
			visited[edges[x][i]] = 1
	return distance[v] 

def addEdge(edges, u, v): 
	edges[u].append(v) 
	edges[v].append(u) 

n,m=map(int,input().split())
edges = [[] for i in range(n)] 
for i in range(m):
   
	a,b=map(int,input().split())
	
	addEdge(edges, a-1, b-1) 
ans=[]
for i in range(1,n):
    ans.append(minEdgeBFS(edges,i, 0, n))
if 0 in ans:
    print('No')
else:
    print('Yes')
    for i in range(len(ans)):
        print(ans[i])

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
A = []
for m in range(M):
    A.append(list(map(int,list(input().split()))))
A = list(itertools.chain.from_iterable(A))

#
def whereto(x):
    if x%2 == 0:
        return x+1
    else:
        return x-1

Mark = [-1]*(N-1)
Past = []
Que = [1]

while len(Past) != N:
    next_road = ([i for i, x in enumerate(A) if x == Que[0]])

    for n in next_road:
        next = A[whereto(n)]
        #print(next)
        if Past.count(next) == 0:
            Past.append(next)
            Que.append(next)
            #print(next-2)
            Mark[next-2]=Que[0]
    Que.pop(0)

print("Yes")
for m in Mark:
    print(m)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(n,dict):
    que = deque()
    distance = [-1 for _ in range(n)]
    que.append([1,0])
    while(len(que) > 0):
        tmp = que.popleft()
        now = tmp[0]
        step = tmp[1]
        if distance[now-1] == -1:
            distance[now-1] = step
            for x in dict[now-1]:
                que.append([x,step+1])
        else:
            continue
    return distance

def main():
    n,m = map(int,input().split())
    L = [list(map(int,input().split())) for _ in range(m)]
    dict = [[] for _ in range(n)]
    for l in L:
        dict[l[0]-1].append(l[1])
        dict[l[1]-1].append(l[0])
    result = bfs(n,dict)
    S = set(result)
    if -1 in S:
        print("No")
    else:
        for x in result[1:]:
            print(x)
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m = map(int,input().split())
AB = [tuple(map(int, input().split())) for _ in range(m)]

def dfs(start):
    stack = []
    visited = [False] * n
    visited[start-1] = True
    stack.append(start)
    while stack:
        target = stack.pop()
        for i in g[target]:
            if not visited[i-1]:
                ans[i-2] = target
                visited[i-1] = True
                stack.append(i)

ans = [0] * (n-1)
g = defaultdict(list)
for a, b in AB:
    g[a].append(b)
    g[b].append(a)
start = 1
dfs(start)
if len([i for i in ans if i == 0]) == 0:
    print("Yes")
    print(*ans, sep="\n")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = {i:0 for i in range(1,N+1)}
ans[1] = 10000000
route = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
x = [1]
for _ in range(N+1):
    for i in x:
        tmp = []
        count = 0
        for j in route[i]:
            #print(j)
            if ans[j] == 0:
                ans[j] = i
                count += 1
                tmp.append(j)
    x = tmp
    #print(ans,x)
    if count == 0:
        break
print('Yes')
for i in ans.keys():
    if i != 1:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
L=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    L[a-1].append(b)
    L[b-1].append(a)
rou=L[0]
nrou=[]
sign=[0]*n
pas=[]
for i in rou:
    sign[i-1]=1
count=len(rou)
for i in range(n):
    for x in rou:
        pas.append(x)
    for x in rou:
        for y in L[x-1]:
            if y not in pas:
                nrou.append(y)
                sign[y-1]=x
                count += 1
    rou.clear()
    rou=nrou
    print(rou,pas)
    if count>=n-1:
        break

print('Yes')
for i in range(1,n):
    print(sign[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

''' Breadth First Search (BFS) '''
def bfs(x):
    q = deque([x])
    visited[x] = True
    while q:
        x = q.popleft()
        for y in adj[x]:
            if not visited[y]:
                q.append(y)
                visited[y] = True
                parent[y] = x

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
parent = [i for i in range(n + 1)]
visited = [False] * (n + 1)

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

bfs(1)
check = True
if i in range(2, n + 1):
  if parent[i] == i:
    check = False
if check:
  for i in range(2, n + 1):
    print(parent[i])
else:
  print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
l = [[] for _ in range(n+1)]
for a,b in ab:
  l[a].append(b)
  l[b].append(a)

cnt = 0
ans = [0] * (n+1)
ans[0],ans[1] = "", ""
for i in l[1]:
  if ans[i]==0: 
    ans[i]=1
    cnt += 1

now = deque(l[1])
for i in range(1, n+1):
  while now:
    x = now.pop()
    for j in l[x]:
      if ans[j] == 0: 
        ans[j] = x
        cnt += 1
if cnt != n-1: print("No")
else:
  print("Yes")
  for v in ans[2:]: print(v)

Submission status: Wrong Answer

Solution code:
inf = 10 ** 7
N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]
a = [[] for i in range(N)]
for i in P:
    a[i[0]-1].append(i[1]-1)
    a[i[1]-1].append(i[0]-1)
path = [-1] * N
path[0] = 0
checked = [False] * N
stack = [0]
while (len(stack) != 0):
    now = stack.pop()
    nextP = a[now]
    for i in nextP:
        if not checked[i]:
            path[i] = now
            stack.append(i)
            checked[i] = True
if False in checked:
    print("No")
else:
    print("Yes")
    for i in path[1:]:
        print(i + 1)

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

n , w = map(int,input().split())
bool = True
cost = [[float("inf") for i in range(n+1)] for i in range(n+1)] 
ans = [0]*(n-1)
for i in range(w):
    x, y = map(int,input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
ans = dijkstra(0,n,w,cost)

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