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: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
from collections import deque
import itertools
from copy import deepcopy
import random
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_pow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def get_primes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
######################################################################################################
def main():
    N,M=map(int,input().split())
    G=[[] for a in range(N)]
    for a in range(M):
        x,y=map(int,input().split())
        x-=1
        y-=1
        G[x].append(y)
        G[y].append(x)
    mmin=[inf]*N
    mmin[0]=0
    to=[-1]*N
    Q=deque()
    Q.append(0)
    while len(Q)>0:
        now=Q.popleft()
        for a in range(len(G[now])):
            x=G[now][a]
            if mmin[x]>mmin[now]+1:
                mmin[x]=mmin[now]+1
                to[x]=now
                Q.append(x)
    to=to[1:]
    if to.count(-1)>0:
        print("No")
        return
    else:
        print("Yes")
        for a in range(N-1):
            print(to[a]+1)
main()

Submission status: Accepted

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

ans = [0] * (n - 1)

def bfs(i, queue, p):
    while len(queue) > 0:
        x = queue.popleft()
        pre = p.popleft()
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                queue.append(data[x[j]])
                p.append(x[j])

queue = deque()
pre = deque()
pre.append(0)
queue.append(data[0])
bfs(0, queue, pre)

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())

r=[[] for _ in range(n)]
d=deque()
b=[n+1]*n
for _ in range(m):
    a,z=map(int,input().split())
    r[a-1].append(z-1)
    r[z-1].append(a-1)

o=0
f=1
b[o]=0
for _ in range(n):
    for i in r[o]:
        if(b[i]==n+1):
            b[i]=o
            d.append(i)
    if(d):
        o=d.popleft()
        f+=1
    else:
        break

if (f==n):
    print("Yes")
    for i in b[1:]:
        print(i+1)
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
import heapq

N, M = map(int, sys.stdin.readline().strip().split())
G = [[] for _ in range(N)]
for m in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# print(G)
# みんな大好き　ダイクストラ
d = [] * N
c = [False] * N
heapq.heappush(d, (0, 0))
p = [N] * N  # 親を保存するリスト　親ノードとしてあり得ない N を初期値にした

mindist = [float('inf')] * N
mindist[0] = 0

while d:
    now = heapq.heappop(d)[1]
    c[now] = True

    for i in G[now]:
        if mindist[now] + 1 < mindist[i]:
            mindist[i] = mindist[now] + 1
            p[i] = now
            heapq.heappush(d, (mindist[i], i))

# print(p)
# 答える
if N in set(p[1:]):
    print('No')
else:
    print('Yes')
    for i in p[1:]:
        print(i + 1)

Submission status: Accepted

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]+=[b-1]
  G[b-1]+=[a-1]
que=deque([0])
visited=[-1 for i in range(N)]
visited[0]=0
dokokara=[0 for i in range(N)]
while len(que)>0:
  v=que.popleft()
  for i in G[v]:
    if visited[i]!=-1:
      continue
    else:
      visited[i]+=1
      dokokara[i]=v
      que.append(i)


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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
p = [[] for x in range(n)]
r = [-2] + [-1] * (n - 1)
for _ in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    p[a].append(b)
    p[b].append(a)

from collections import deque
dq = deque()
dq.append(0)

def bfs(room):
    l = []
    global r
    for iroom in p[room]:
        if r[iroom] == -1:
            r[iroom] = room
            l.append(iroom)
    return l

while len(dq) > 0:
    c = dq.popleft()
    ll = bfs(c)
    dq.extend(ll)

if -1 in r:
    print('No')
else:
    print('Yes')
    for i in r[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
import queue
n,m=map(int,input().split())
road_list=[set() for i in range(n)]
mitisirube=[0]*n
mitisirube[0]=1
for i in range(m):
    a,b=map(int,input().split())
    road_list[a-1].add(b)
    road_list[b-1].add(a)

q = queue.Queue()

counter_set=set()
counter_set.add(1)
for i in road_list[0]:
    q.put(i)
    mitisirube[i-1]=1
    counter_set.add(i)

while not q.empty():
    tmp=q.get()
    for i in road_list[tmp-1]:
        if i not in counter_set:
            q.put(i)
            counter_set.add(i)
            if mitisirube[i-1]==0:
                mitisirube[i-1]=tmp

if mitisirube.count(0)>0:
    print("No")
else:
    print("Yes")
    for i in range(1,len(mitisirube)):
        print(mitisirube[i])

Submission status: Accepted

Solution code:
from collections import deque
import collections
import math
import sys

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

def bfs(i, ans):
    d = deque()
    ans[i] = 0
    d.append(i)
    while len(d) > 0:
        v = d.popleft()
        for node in table[v]:
            if ans[node] == -1:
                ans[node] = v
                d.append(node)
    return ans


table = [[] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)
ans = [-1 for i in range(n)]

ans = bfs(0, ans)

if -1 in ans:
    print('No')
else:
    print('Yes')
    for a in ans[1:]:
        print(a+1)

Submission status: Accepted

Solution code:
import queue

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

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

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

# cost to isMin
result = [[999999999999999, None, False] for i in range(n)]

# from tom
q = queue.Queue()

result[0] = [0, None, True]
for i in road[0]:
    q.put([0,i])

while not q.empty():
    n = q.get()
    if(not result[n[1]][2]):
        result[n[1]]=[result[n[0]][0]+1, n[0], True]
        for i in road[n[1]]:
            q.put([n[1], i])

flag = True
for i in result:
    if(not i[2]):
        flag = False
        break

if(flag):
    print("Yes")
    for i in range(1,len(result)):
        print(result[i][1]+1)
else:
    print("No")

Submission status: Accepted

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

dic = {}
for i in range(m):
    a, b = map(int, input().split())
    if not a in dic:
        dic[a] = [b]
    else:
        dic[a].append(b)
    if not b in dic:
        dic[b] = [a]
    else:
        dic[b].append(a)

queue = [1]
res = [0] * (n+1)
while queue != []:
    p = queue[0]
    del queue[0]
    for i in dic[p]:
        if res[i] == 0:
            res[i] = p
            queue.append(i)
            
print('Yes')
for elem in res[2:]:
    print(elem)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict


def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(m)]

    R = defaultdict(set)
    for ab in AB:
        a, b = ab
        R[a].add(b)
        R[b].add(a)

    A = [0] * (n + 1)
    Q = deque(R[1])
    Qa = deque([1] * len(R[1]))
    while len(Q) > 0:
        qe = Q.pop()
        arrow = Qa.pop()
        if A[qe] == 0:
            A[qe] = arrow
            for r in R[qe]:
                Q.appendleft(r)
                Qa.appendleft(qe)

    if A[2:].count(0) > 0:
        print('No')
        exit()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

def bfs(loads):
    visit = [-1] * len(loads)
    d = deque([0])
    visit[0] = 0
    
    while d:
        num = d.popleft()
        
        for l in loads[num]:
            if visit[l] != -1:
                continue
            
            d.append(l)
            visit[l] = num
        
        
    return visit

n, m = map(int, input().split())
loads = [[] for _ in range(n)]

for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    loads[a].append(b)
    loads[b].append(a)
    
visit = bfs(loads)

if -1 in visit:
    print('No')
    sys.exit()
    
print('Yes')
for i in range(1, n):
    print(visit[i] + 1)

Submission status: Accepted

Solution code:
import numpy as np
import networkx as nx
g = nx.Graph()

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

for _ in range(m):
    a, b = map(int, input().split())
    g.add_edge(a, b)

res = np.array([0] * 2 + [-1] * (n-1))

from collections import deque
q = deque([1])

while q:
    vis = q.popleft() # visit
    #     print(vis)
    cands = list(nx.all_neighbors(g, vis)) # next visit

    if cands:
        for c in cands:
            if res[c] == -1:
                res[c] = vis # mark
                q.append(c) # should append

if (res == -1).sum():
    print('No')
else:
    print('Yes')
    for i in res[2:]:
        print(i)

Submission status: Accepted

Solution code:
import sys
import collections
import heapq


def main():

    input = sys.stdin.readline

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

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

    ans_list = [0] * (N + 1)

    syori_list = []

    adjacent_dict = collections.defaultdict(list)

    
    for frm, to in edges:
        adjacent_dict[frm].append(to)
        adjacent_dict[to].append(frm)

    tmp_list = []
    tmp_list = adjacent_dict[1]
    for i in tmp_list:
        syori_list.append(i)
        ans_list[i] = 1

    for i in syori_list:
        tmp_list = adjacent_dict[i]
        for j in tmp_list:
            if ans_list[j] == 0:
                syori_list.append(j)
                ans_list[j] = i
    
    check_list = ans_list[2:]

    if check_list.count(0) > 0:
        print("No")
        return
    else:
        print("Yes")
    
    for i in check_list:
        print(i)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

c = [set([]) for i in range(n)]

d = [n for i in range(n)]
d[0] = 0
dist = [set([]) for i in range(n+1)]
dist[0].add(1)
ans = [n for i in range(n)]
ans[0] = 0

for i in range(m):
    a,b = list(map(int, input().split(" ")))
    c[a-1].add(b)
    c[b-1].add(a)
    if a==1:
        d[b-1] = 1
        dist[1].add(b)
        ans[b-1] = 1
    if b==1:
        d[a-1] = 1
        dist[1].add(a)
        ans[a-1] = 1

for i in range(1, n):
    for one in dist[i]:
        #print("dist", i, one)
        #print(c[one-1])
        for one2 in c[one-1]:
            #print(i, d[one2-1])
            if i<d[one2-1]:
                dist[i+1].add(one2)
                d[one2-1] = i+1
                ans[one2-1] = one

if n in d:
    print("No")
else:
    print("Yes")
    for i, one in enumerate(ans):
        if i!=0:
            print(one)

Submission status: Accepted

Solution code:
def check_road(start, road_array, mark_array):
    search_target = []
    search_target.append(start)

    while len(search_target) > 0:
        target = search_target[0]
        if len(road_array[target]) != 0:
            for road in road_array[target]:
                if road is not None and mark_array[road] is None and road != 1:
                    # 逆側の要素を返す
                    # print('{}を探している、次は{}へ移動'.format(
                    #     target, road[abs(1-road.index(target))]))
                    mark_array[road] = target
                    search_target.append(road)
        del search_target[0]


# 部屋の数 通路の数
N, M = map(int, input().split())
road_array = [[None] for i in range(N+1)]
# for i in road_array:
#     print(i)
#     print(len(road_array))
for i in range(M):
    a, b = map(int, input().split())
    tmp_a = road_array[a]
    tmp_b = road_array[b]
    # print('チェック{}'.format(i))
    # print('チェック{}'.format(tmp_a))
    # print('チェック{}'.format(tmp_b))
    tmp_a.append(b)
    tmp_b.append(a)
    road_array[a] = tmp_a
    road_array[b] = tmp_b

mark_array = [None] * (N+1)
check_road(1, road_array, mark_array)
mark_array = mark_array[2:]

if None in mark_array:
    print('No')
else:
    print('Yes')
    for mark in mark_array:
        print(mark)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
path = list(list(map(int, input().split())) for _ in range(m))

d = deque()

dic = dict()
for i in range(m):
    p = path[i]
    if p[0] not in dic:
        dic[p[0]] = [p[1]]
    else:
        dic[p[0]].append(p[1])
    if p[1] not in dic:
        dic[p[1]] = [p[0]]
    else:
        dic[p[1]].append(p[0])
        
sign = [0]*n
done = [0]*n
done[0] = 1

for i in dic[1]:
    d.appendleft(i)
    sign[i-1] = 1
    done[i-1] = 1

while len(d) > 0:
    x = d.pop()
    for i in dic[x]:
        if done[i-1] == 0:
            d.appendleft(i)
            sign[i-1] = x
            done[i-1] = 1
        
print("Yes")
for i in range(n-1):
    print(sign[i+1])

Submission status: Accepted

Solution code:
from collections import deque

n,m=list(map(int,input().split()))
R=[[] for _ in range(n)]
sign=[0 for _ in range(n-1)]
dp=[0 for _ in range(n)]

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

start=deque()
start.append(0)
dp[0]=1

while start:
  s=start.popleft()
  for r in R[s]:
    if dp[r-1]:
      continue
    sign[r-2] = s + 1
    start.append(r-1)
    dp[r-1]=1

if 0 in sign:
  print("No")
else:
  print("Yes")
  for s in sign:
    print(s)

Submission status: Accepted

Solution code:
from collections import deque

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

g = [[] for _ in range(N+1)] # 隣接リスト

for _ in range(M):
    a, b = [int(x) for x in input().split()]
    #print(a,b,g)
    g[a].append(b)
    g[b].append(a)

#road_list=[]
#for i in range(M):
#  road_list.append(list(map(int,input().split())))

queue = deque([1])
d = [None] * (N+1) # uからの距離の初期化
d[1] = 0 # 自分との距離は0
while queue:
  v = queue.popleft()
  for i in g[v]:
    if d[i] is None:
      d[i] = v
      queue.append(i)

#print(d)


#ans_dict=dict([])
#before_room=[1]
#while True:
#  temp_room=[]
#  for j in range(len(before_room)):
#    for i in road_list:
#      if i[0]==before_room[j]:
#        if i[1] not in ans_dict:
#          ans_dict[i[1]]=before_room[j]
#          temp_room.append(i[1])
#      if i[1]==before_room[j]:
#        if i[0] not in ans_dict:
#          ans_dict[i[0]]=before_room[j]
#          temp_room.append(i[0])
#  before_room=temp_room
#  if len(ans_dict)==N:
#    break
    
d[0]=0
if None in d:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(d[i])

Submission status: Accepted

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: Accepted

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: Accepted

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

import queue
ans = [0]*1000001
done = [0]*100001
dict = {}
next = []
q = queue.Queue()

def nanka(before, now):
    #print(before,now)
    if ans[now-1] == 0:
        ans[now-1] = before
        done[now] = 1
        for tt in dict[now]:
            if done[tt] == 1:
                continue
            elif tt not in next:
                q.put([now,tt])

def main():
    N ,M  =  [int(i) for i in input().split()]

    road = []
    for i in range(M):
        a, b = [int(i) for i in input().split()]
        if a not in dict.keys():
            dict[a] = [b]
        else:
            dict[a].append(b)
        if b not in dict.keys():
            dict[b] = [a]
        else:
            dict[b].append(a)
    #road = sorted(road)

    mins = [1000000] * N

    for j in dict[1]:
        before = 1
        now = j
        nanka(1,j)
    while not q.empty():
        kk = q.get()
        nanka(kk[0],kk[1])
        
    if 0 in ans[1:N]:
        print("No")
    else:
        print("Yes")
        for i in ans[1:N]:
            print(i)
    #print(ans[1:N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
ans=[-1]*n
visited=[True]*n
stack=deque([0])
visited[0]=False
while stack:
    x=stack.popleft()
    for nx in edge[x]:
        if visited[nx]:
            visited[nx]=False
            stack.append(nx)
            ans[nx]=x
for i in range(1,n):
    if visited[i]:
        print("No")
        exit()
print("Yes")
for i in ans[1:]:
    print(i+1)

Submission status: Accepted

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: Accepted

Solution code:
from heapq import heappush, heappop, heapify

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
nodes = [[] for _ in range(n)]
costs = [n+1 for i in range(n)]
costs[0] = 0
oyas = [None for _ in range(n)]

for tmp in ab:
    nodes[tmp[0]-1].append(tmp[1]-1)
    nodes[tmp[1]-1].append(tmp[0]-1)
#print(nodes)
## (cost, node, oya)
op_l = [(costs[0]+1, no, 0) for no in nodes[0]]
heapify(op_l)

while True:
    if len(op_l) == 0:
        break
    cost, node, oya = heappop(op_l)
    if oyas[node] is not None:
        continue
    else:
        costs[node] = cost
        oyas[node] = oya
        for ko in nodes[node]:
            if ko == 0 or oyas[ko] is not None:
                continue
            else:
                tmp = (costs[node]+1, ko, node)
                heappush(op_l, tmp)
#print(oyas)
for i in range(n):
    if i == 0:
        print("Yes")
    else:
        print(oyas[i]+1)

Submission status: Accepted

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

to = [[] for _ in range(110000)]
ans = [0] * 110000
queue = []
passed = [0] * 110000
passed[1] = 1

def search(i):
  global queue
  global passed
  global ans
  for j in to[i]:
    if passed[j] == 0:
      queue.append(j)
      passed[j] = 1
      ans[j] = i
  


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

search(1)
queue.append(1)

while queue:
  que = queue.pop(0)
  search(que)


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

Submission status: Accepted

Solution code:
from collections import OrderedDict, defaultdict, deque
from enum import Enum
from typing import Dict, Optional


class State(Enum):
    UNVISITED = 0
    VISITED = 1


class Node(object):
    def __init__(self, key: int) -> None:
        self.adj_nodes: Dict[int, Node] = {}  # node key: node
        self.key: int = key
        self.state = State.UNVISITED

    def __repr__(self):
        return "<Node {}>".format(self.key)

    def add_adj_node(self, key) -> None:
        if key not in self.adj_nodes.keys():
            self.adj_nodes[key] = Node(key)


class Graph:
    def __init__(self) -> None:
        self.nodes: Dict[int, Node] = {}

    def add_node(self, key) -> None:
        if key not in self.nodes.keys():
            self.nodes[key] = Node(key)

    def add_edge(self, source: int, dest) -> None:
        if not self.get_node(source):
            self.add_node(source)
        if not self.get_node(dest):
            self.add_node(dest)

        self.get_node(source).add_adj_node(dest)

    def get_node(self, key) -> Optional[Node]:
        try:
            return self.nodes[key]
        except KeyError:
            return None


class BFS:
    def __init__(self, g: Graph, start_key: int):
        self.graph = g
        self.start_key = start_key
        self.history: Dict[int, int] = {}

    def solve(self):
        n = self.graph.get_node(self.start_key)
        n.state = State.VISITED
        queue = deque()
        queue.append(n.key)
        while queue:
            n_key = queue.popleft()
            n = self.graph.get_node(n_key)

            for adj_node_key in n.adj_nodes:
                adj_node = self.graph.get_node(adj_node_key)
                if adj_node.state == State.UNVISITED:
                    self.history[adj_node_key] = n.key
                    adj_node.state = State.VISITED
                    self.visit_func(adj_node_key)
                    queue.append(adj_node_key)

    def visit_func(self, node_key):
        raise NotImplementedError


class Ans(BFS):
    def __init__(self, g, n, start_key=1):
        super().__init__(g, start_key)
        self.n = n
        self.dist = {x: -1 for x in range(1, n + 1)}
        self.dist[self.start_key] = 0

    def visit_func(self, node_key):
        if node_key != self.start_key:
            prev_dist = self.dist[self.history[node_key]]
            self.dist[node_key] = prev_dist + 1

    def show_results(self, n):
        if -1 in set(self.dist.values()):
            print("No")
            return
        print("Yes")
        for i in range(2, n + 1):
            print(self.history[i])


if __name__ == "__main__":
    n, m = map(int, input().split(" "))
    G = Graph()
    for i in range(n):
        G.add_node(i + 1)

    for _ in range(m):
        a, b, = map(int, input().split(" "))
        # print(a, b)
        G.add_edge(a, b)
        G.add_edge(b, a)

    a = Ans(G, n)
    a.solve()
    # a.show_results()
    a.show_results(n)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if not directed:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = LI()
A,B = LIR(M,2)

pt = edges_to_pt(A,B,N)
par = [0]*N
s = 0

n = len(pt)
d = [-1]*n
d[s] = 0
q = [s]
c = 1
while q:
    q1 = []
    for v in q:
        for u in pt[v]:
            if d[u] == -1:
                d[u] = c
                par[u] = v
                q1.append(u)
    q = q1
    c += 1

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