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:
from collections import deque

class Cave():
    def __init__(self):
        self.graph = {}
    def add_room(self, r):
        self.graph[r] = []
    def add_passage(self, r1, r2):
        self.graph[r1].append(r2)
        self.graph[r2].append(r1)
    def next_rooms(self, r):
        return self.graph[r]
    def __str__(self):
        return self.graph.__str__()

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

    cave = Cave()
    for i in range(1, N+1):
        cave.add_room(i)
    for r1, r2 in AB:
        cave.add_passage(r1, r2)

    q = deque()
    q.append(1)
    visited = [0]*(N+1)
    visited[1] = -1

    while q:
        r_now = q.popleft()
        for r_next in cave.next_rooms(r_now):
            if visited[r_next] == 0:
                visited[r_next] = r_now
                q.append(r_next)

    print('Yes')
    for i in visited[2:]:
        print(i)
main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10000000)
N, M = map(int, input().split())
class tree():
    def __init__(self):
        self.num = 0
        self.flag = 0
        self.step = -1
        self.leaf = []

li = [tree() for i in range(N)]
def saiki(que, step):
    pop = que.popleft()
    li[pop].flag = 2


    for i in range(len(li[pop].leaf)):
        if li[li[pop].leaf[i]].flag == 0:
            que.append(li[pop].leaf[i])
            li[li[pop].leaf[i]].flag = 1
            if li[li[pop].leaf[i]].step != -1:
                if li[li[pop].leaf[i]].step > li[pop].step + 1:
                    li[li[pop].leaf[i]].step = li[pop].step + 1
                    li[li[pop].leaf[i]].num = pop
            else:
                li[li[pop].leaf[i]].step = li[pop].step + 1
                li[li[pop].leaf[i]].num = pop


    #print(que)
    if len(que) != 0:
        saiki(que, li[pop].step)
for i in range(M):
    A, B = map(int, input().split())
    li[A-1].leaf.append(B-1)
    li[B-1].leaf.append(A-1)

que = deque()
que.append(0)
li[0].step = 0
saiki(que, 0)
flag = 1

for i in range(len(li)):
    if li[i].flag == 0:
        flag = 0
        break
if flag == 0:
    print("No")
else:
    print("Yes")
for i in range(1, len(li)):
    print(li[i].num+1)

Submission status: Accepted

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

def bfs(start):
    queue = deque()
    visited = [False] * n
    visited[start-1] = True
    queue.append(start)
    while queue:
        target = queue.popleft()
        for i in g[target]:
            if not visited[i-1]:
                ans[i-2] = target
                visited[i-1] = True
                queue.append(i)

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

Submission status: Accepted

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

for i in range(m):
    aa, bb = map(int,input().split())

    if aa not in dic:
        dic[aa] = set()
        dic[aa].add(bb)
    else:
        dic[aa].add(bb)

    if bb not in dic:
        dic[bb] = set()
        dic[bb].add(aa)
    else:
        dic[bb].add(aa)

dist = 0
visited = set()

sirube = {}

queue = deque([1])
dist_dic = {}
dist_dic[1] = 0

while len(queue) != 0:
    v = queue.popleft()
    visited.add(v)
    
    for i in dic[v]:
        if i not in visited:
            visited.add(i)
            queue.append(i)
            dist_dic[i] = dist_dic[v] + 1
            sirube[i] = v

print("Yes")

sirube_sorted = sorted(sirube.items(), key=lambda x:x[0])

for i in range(n-1):
    print(sirube_sorted[i][1])

Submission status: Accepted

Solution code:
from collections import deque

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

tree=[[0] for _ in range(N)]

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

dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
ans=[0 for _ in range(N)]
for i in range(1,N):
    for t in tree[i]:
        if dist[t]==dist[i]-1:
            ans[i]=t+1
            break

print("Yes")
for j in range(1,N):
    print(ans[j])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!python3

import sys
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, M = iim()
    it = map(int, sys.stdin.read().split())

    d1 = defaultdict(list)

    for i, j in zip(it, it):
        d1[i].append(j)
        d1[j].append(i)

    ans = [0] * (N+1)
    dq = [1]
    visited = set([1])

    updated = True
    while updated:
        updated = False
        dq2 = []
        for i in dq:
            for j in d1[i]:
                if j in visited:
                    continue
                ans[j] = i
                dq2.append(j)
                visited.add(j)
                updated = True
        dq = dq2

    if len(visited) == N:
        print("Yes", *ans[2:], sep="\n")
    else:
        print("No")






if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(9999)

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

ps = [-1] * n
ps[0] = 0
tmps = {}
for _ in range(m):
    a,b=map(int,input().split())
    ai,bi=a-1,b-1
    if ai not in tmps:
        tmps[ai] = []
    tmps[ai].append(bi)
    if bi not in tmps:
        tmps[bi] = []
    tmps[bi].append(ai)

# print(tmps)

if 0 not in tmps:
    print("No")
    exit()


def puts(ks):
    nks = []
    for k in ks:
        _nks = tmps[k]
        for nk in _nks:
            if ps[nk] == -1:
                ps[nk] = k
                nks.append(nk)
    if nks == []:
        return None
    # puts(nks)
    return nks

ks = [0]
while True:
    nks = puts(ks)
    if nks is None:
        break
    else:
        ks = nks

#print(ps)

if -1 in ps:
    print("No")
    exit()

print("Yes")
for p in ps[1:]:
    print(p+1)

Submission status: Accepted

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

tunagari = [[] for i in range(n)]
sirusi = [-1 for i in range(n)]
sirusi[0] = 0

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

que = [0]
while que:
    for i in tunagari[que[0]]:
        if sirusi[i] == -1:
            sirusi[i] = que[0]
            que.append(i)
    que.pop(0)

sirusi.pop(0)
print("Yes")
for i in sirusi:
    print(i+1)

Submission status: Accepted

Solution code:
dg=10**7
import heapq
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([1,b])
  edge[b].append([1,a])

s=0
d=[10**20]*n
used=[False]*n
used[s]=True
d[s]=0
edgelist=[]
fromv=[-1]*n

for e in edge[s]:
  e.append(s)
  heapq.heappush(edgelist,e)
while len(edgelist):
  minedge=heapq.heappop(edgelist)
  v=minedge[1]
  if used[v]:
    continue
  d[v]=minedge[0]
  used[v]=True
  fromv[v]=minedge[2]
  for e in edge[v]:
    if not used[e[1]]:
      heapq.heappush(edgelist,[e[0]+d[v],e[1],v])
      fromv[e[1]]=v
if any([x==-1 for x in fromv[1:]]):
  print('No')
else:
  print('Yes')
  for x in fromv[1:]:
    print(x+1)

Submission status: Accepted

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


def solve():
    N, M = map(int, input().split())
    loadmap = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, input().split())
        loadmap[A].append(B)
        loadmap[B].append(A)

    dbrmap = [[float('inf'), -1, 0] for _ in range(N + 1)]  # 部屋の深度, しるべ, 予約状態

    # rooms = [[0, 1, 0]]  # [移動前の部屋, 移動後(現在)の部屋, 深度]
    rooms = deque()
    rooms.append([0, 1, 0])
    dbrmap[1][2] = 1
    while rooms:
        # br, r, d = heappop(rooms)
        br, r, d = rooms.popleft()
        if d <= dbrmap[r][0]:
            # update room data
            dbrmap[r][0] = d
            dbrmap[r][1] = br
            # add new room data
            for load in loadmap[r]:
                # heappush(rooms, [r, l, d + 1])
                if dbrmap[load][2] == 0:
                    rooms.append([r, load, d + 1])
                    dbrmap[load][2] = 1

    if min([db[1] for db in dbrmap[1:]]) <= -1:
        print('No')
    else:
        print('Yes')
        for db in dbrmap[2:]:
            print(db[1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

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

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    edge[x-1].append([1,y-1])
    edge[y-1].append([1,x-1]) 
d = dijkstra_heap(0)

OK_flag = True

dic = {}
for i in range(n):
    if d[i] == float("inf"):
        OK_flag = False
    dic[d[i]] = i


if OK_flag == True:
    print("Yes")
    for i in range(1, n):
        print(dic[d[i]-1]+ 1)
else:
    print("No")

Submission status: Accepted

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

road = {k:[] for k in range(1,n+1)}
for _ in range(m):
  a,b = map(int,input().split())
  road[a].append(b)
  road[b].append(a)


next_visited = [1]
visited = {1:None}
temp_next = []

visit_num = {}
count = 0

while True:
  temp_next = []
  for room in next_visited:
    ava_room = road[room]
    for r in ava_room:
      try:
        visited[r]
      except:
        visit_num[r] = room
        temp_next.append(r)
        visited[r] = None
        
  if temp_next == []:
    break
  next_visited = temp_next

if len(visit_num) != n-1:
  print('No')

else:
  print('Yes')
  for v in sorted(visit_num.items()):
    print(v[1])

Submission status: Accepted

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

import sys

input = sys.stdin.readline
R = [[] for _ in range(n)]
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0

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

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

if min(Dis)<0:
  print('No')
  sys.exit()
print('Yes')
for i in range(1,n):
  print(Sin[i])

Submission status: Accepted

Solution code:
from collections import deque

def main():
    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-1)
        G[b-1].append(a-1)

    dist = [-1] * N
    que = deque([0])
    dist[0] = 0
    parent = [-1] * N
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            parent[w] = v
            que.append(w)

    ans = [x + 1 for x in parent[1:]]

    print('Yes')
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def get_input():
    N, M =  list(map(int, input().split()))
    routes = {}
    for i in range(M):
        a, b =  list(map(int, input().split()))
        a_idx = a - 1
        b_idx = b - 1
        if a_idx in routes:
            routes[a_idx].append(b_idx)
        else:
            routes[a_idx] = [b_idx]
        
        if b_idx in routes:
            routes[b_idx].append(a_idx)
        else:
            routes[b_idx] = [a_idx]

    return N, M, routes

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy


marks = {0:0}

N, M, routes = get_input()
mark = {0:0}
start_nodes = [0]
while start_nodes:
    next_nodes = []
    for i in start_nodes:
        for n in routes[i]:
            if n in marks:
                continue
            marks[n] = i
            next_nodes.append(n)
    start_nodes = next_nodes   
write_result(marks, N)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
R = [[] for _ in range(N)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for _ in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(que):
    if que==[]:
        return
    i = que[0]
    for j in R[i-1]:
        if ans[j-1]==0:
            ans[j-1]=i
            que.append(j)
    que.pop(0)
    bfs(que)
    
bfs(queue)
print('Yes')
for i in range(1,N):
    print(ans[i])

Submission status: Accepted

Solution code:
import queue

N,M = map(int, input().split())
V   = []

for _ in range(N):
    V.append(set())

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

q = queue.Queue()

q.put(0)
visit = [False]*N
visit[0] = True
ans_list = [0]*N
while not (q.empty()):
    node = q.get()
    for next_node in V[node]:
        if visit[next_node]:
            continue
        visit[next_node] = True
        ans_list[next_node] = node
        q.put(next_node)

if False in visit:
    print("No")
else:
    print("Yes")
    for i in range(1, len(ans_list), 1):
        print(ans_list[i]+1)

Submission status: Accepted

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

g=[[] for i in range(N+1)]

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

from collections import deque

queue = deque([1])
d = [None] * (N+1)
while queue:
	v = queue.popleft()
	for i in g[v]:
		if d[i] is None:
			d[i] = v
			queue.append(i)

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

Submission status: Accepted

Solution code:
import queue

n,m = map(int, input().split())
root = [[] for i in range(n)]
for i in range(m):
    tmp1, tmp2 = map(int, input().split())
    root[tmp1 - 1].append(tmp2 - 1)
    root[tmp2 - 1].append(tmp1 - 1)
q = queue.Queue()
q.put(0)
arrive = [0 for i in range(n)]
ans = [0 for i in range(n)]
arrive[0] = 0
while not q.empty():
    now = q.get()
    for i in root[now]:
        if arrive[i] == 0 and i != 0:
            arrive[i] = arrive[now] + 1
            ans[i] = now + 1
            q.put(i)
        else:
            if arrive[i] > arrive[now] + 1:
                ans[i] = now + 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

n, m = [int(i) for i in input().split()]
graph = defaultdict(list)
for _ in range(m):
    a, b = [int(i) for i in input().split()]
    graph[a].append(b)
    graph[b].append(a)

def bfs():
    q = deque([(1, None)])
    visited = set()
    posts = {}

    while q:
        node, last_node = q.pop()
        if last_node:
            posts[node] = last_node
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                q.appendleft((neighbor, node))
                visited.add(neighbor)
    
    return posts, len(visited)

posts, total_visited = bfs()
if total_visited != n:
    print('No')
else:
    print('Yes')
    for p in range(2, n+1):
        print(posts[p])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-05-17 22:04:10 +0900
# LastModified: 2020-05-17 22:24:55 +0900
#

from collections import deque

def bfs(path_list,guide,n):
    color = [0]*(n+1)
    color[1] = 1
    Q = deque()
    Q.append(1)
    while Q:
        u = Q.popleft()
        for v in path_list[u]:
            if color[v] == 0:
                color[v]=1
                Q.append(v)
                guide[v]=u

def main():
    n,m = map(int,input().split())
    path_list = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,input().split())
#        print(a,b)
        path_list[a].append(b)
        path_list[b].append(a)

#    print(path_list)
    
    guide = [0]*(n+1)
    bfs(path_list,guide,n)
    print("Yes")
    for i in range(2,n+1):
        print(guide[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
nodes = [None] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    if nodes[A] is None:
        nodes[A] = set()
    nodes[A].add(B)
    if nodes[B] is None:
        nodes[B] = set()
    nodes[B].add(A)
r = [None] * N
r[0] = "Yes"
Q = collections.deque([0])
while len(Q) != 0:
    i = Q.popleft()
    for j in nodes[i]:
        if r[j] is None:
            r[j] = i+1
            Q.append(j)
for x in r:
    print(x)

Submission status: Accepted

Solution code:
n,m = [int(e) for e in input().split(" ")[:2]]

r_dic = {i+1: [] for i in range(n)}
for i in range(m):
	a,b = [int(e) for e in input().split(" ")[:2]]
	r_dic[a].append(b)
	r_dic[b].append(a)

m_dic = {i+1: None for i in range(1,n)}
search_flag_dic = {i+1: False for i in range(n)}

s_ls = [1]
while True:
	next_s_ls = []
	for s in s_ls:
		search_flag_dic[s] = True
		# 目的地の検索
		d_ls = r_dic[s]
		# 道しるべの書き込み
		for d in d_ls:
			if d == 1: continue
			if m_dic[d] is None: m_dic[d] = s
			next_s_ls.append(d)
	# 終了条件
	next_s_ls = list(set(next_s_ls))
	next_s_ls = [e for e in next_s_ls if search_flag_dic[e] is False]
	if len(next_s_ls) == 0: break
	s_ls = next_s_ls

result = "Yes" if len([k for k in m_dic if m_dic[k] is None]) == 0 else "No"
print(result)
if result == "Yes":
	for i in range(1,n):
		print(m_dic[i+1])

Submission status: Accepted

Solution code:
def resolve():
    from collections import deque
    n, m = map(int, input().split())
    michi = [[] for j in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        michi[a-1].append(b-1)
        michi[b - 1].append(a - 1)
    heya=[-1]*n

    def f():
        check=0
        que = deque([])
        que.append(0)
        while que:
            p = que.popleft()
            for i in michi[p]:
                if heya[i] == -1:
                    heya[i] = p + 1
                    check += 1
                    if check == n :
                        break
                    que.append(i)

        return

    f()
    print("Yes")
    for i in heya[1:]:
        print(i)
resolve()

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    ab = {}
    ab1 = {}
    for _ in range(m):
        a,b=map(int,input().split())
        ab.setdefault(a,set()).add(b)
        ab.setdefault(b,set()).add(a)
        ab1.setdefault(a,set()).add(b)
        ab1.setdefault(b,set()).add(a)
    g = []
    g.append(set([1]))
    marked = set()
    marked.add(1)
    while ab:
        g_add = set()
        for k in g[-1]:
            for x in ab[k]:
                if x not in marked:
                    g_add.add(x)
                    marked.add(x)
            del ab[k]
        g.append(g_add)
    if len(marked) < n:
        print('No')
        return
    print('Yes')
    result = [None] * n
    for i,s in enumerate(g):
        if not i:
            continue
        for k in s:
            result[k-1] = (g[i-1]&ab1[k]).pop()
    for i in range(1,n):
        print(result[i])

main()

Submission status: Accepted

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


YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    root = []
    for i in range(N):
        root.append([])
    next = [-1] * N
    for a, b in zip(A, B):
        root[a - 1].append(b - 1)
        root[b - 1].append(a - 1)

    q = queue.Queue()
    q.put(0)

    while not q.empty():
        #print(next)
        n = q.get()
        for i in root[n]:
            if next[i] == -1:
                next[i] = n
                q.put(i)

    if -1 in next:
        print("No")
        exit()
    
    print("Yes")
    for i in range(1, len(next)):
        print(next[i] + 1)
    

    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for idx in range(n):
    road[idx] = []

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

visited = [-1 for i in range(n)]

from collections import deque
def bfs(road):
    global visited
    queue = deque([0])
    visited[0] = 0
    while queue:
        x = queue.popleft()
        for r in road[x]:
            if visited[r] == -1:
                visited[r] = x
                queue.append(r)

bfs(road)
if (-1) in visited:
    print('No')
else:
    print('Yes')
    for x in visited[1:]:
        print(x + 1)

Submission status: Accepted

Solution code:
from queue import Queue
import sys

sys.setrecursionlimit(10 ** 6)

def main():
  n, m = map(int, input().split())

  edges = [[] for _ in range(n)]

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

  visited = {0: -1}

  q = Queue()
  q.put(0)

  while not q.empty():
    current = q.get()
    for nxt in edges[current]:
      if nxt not in visited:
        visited[nxt] = current
        q.put(nxt)

  if len(visited) == n:
    print("Yes")
    for i in range(1, n):
      print(visited[i] + 1)
  else:
    print("No")


main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
#ab = [list(map(int, input().split()))]
ab = [[] for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    ab[ai].append(bi)
    ab[bi].append(ai)
from collections import deque
# g : グラフ
# 例 [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]]
# i : 始点
def bfs(g, i, N):
    
    #各頂点への距離
    dis = [float('Inf')] * N 
    route = [0] * N
    #訪れたかどうか
    d = [False] * N
    #初期設定
    que = deque()
    que.append(i)
    d[i] = True
    dis[i] = 0
    
    while que:
        p = que.popleft()
        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[k] = dis[p] + 1
                route[k] = p

    return dis, route
dis, route = bfs(ab, 0, n)
for i in range(n):
    if i == 0:
        continue
    if dis[i] == 0:
        print('No')
        #quit()
print('Yes')
for i in range(1, n):
    print(route[i] + 1)

Submission status: Accepted

Solution code:
def main():
    n, m = [int(v) for v in input().split(' ')]
    map_table = {}
    for _ in range(m):
        a, b = [int(v) - 1 for v in input().split(' ')]
        if a not in map_table.keys():
            map_table[a] = [b]
        else:
            map_table[a].append(b)

        if b not in map_table.keys():
            map_table[b] = [a]
        else:
            map_table[b].append(a)

    stack = [0]
    min_step = [None for _ in range(n)]
    min_step[0] = 0
    n_step = 0

    while len(stack) > 0:
        n_step += 1
        next_stack = []
        for n in stack:
            next_nodes = map_table[n]
            for next_n in next_nodes:
                if min_step[next_n] is None:
                    min_step[next_n] = n
                    next_stack.append(next_n)
        stack = next_stack

    suucess = True
    for v in min_step:
        if v is None:
            suucess = False
    if suucess is True:
        print('Yes')
        for n in min_step[1:]:
            print(int(n) + 1)
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
r = [[0] for i in range(n+1)]
num = {0:0, 1:1}
e = deque([]) 
for i in range(m):
	a, b = map(int, input().split())
	r[a].append(b)
	r[b].append(a)
e.append(1)
while len(e) > 0:
	x = e.popleft()
	for y in r[x]:
		if y not in num:
			num[y] = x
			e.append(y)
print("Yes")
for i in range(2, n+1):
	print(num[i])

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
import heapq
class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v in self.list[u]:
				if self.dist[v] > u_dist + 1:
					self.dist[v] = u_dist + 1
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

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

d = DijkstraList(adj, 0)
d.solve()
print("Yes")
for x in d.prev[1:]:
	print(x+1)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict,deque
    sys.setrecursionlimit(10**5+2)

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=defaultdict(list)
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A].append(B)
        dic[B].append(A)
    
    L=[-1]*(N+1)
    R=[-1]*(N+1)


    d = deque()
    d.append((1,1))
    while len(d):
        now,count=d.popleft()
        for goto in dic[now]:
            if L[goto]==-1 or count<L[goto]:
                L[goto]=count
                R[goto]=now
                d.append((goto,count+1))

    if any(x+1 for x in R[2:]):
        print('Yes')
        for x in R[2:]:
            print(x)
    else:
        print('No')
    


main()

Submission status: Accepted

Solution code:
from collections import deque

R=lambda: map(int, input().split())

n, m = R()
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = R()
  g[u - 1].append(v - 1)
  g[v - 1].append(u - 1)

r = ['Yes'] + [None] * (n - 1)
V = [True] + [False] * (n - 1)
q = deque([0])
while q:
  u = q.popleft()
  for v in g[u]:
    if not V[v]:
      V[v] = True
      r[v] = u + 1
      q.append(v)

print(*(['No'], r)[all(r)], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque



n,m = map(int,input().split())
ab = [[] for _ in range(m)]
kr = [[] for _ in range(n)]
dist = [-1 for _ in range(n)]
dist[0] = 0
ans = [-1 for _ in range(n)]
qn = deque([1])
for i in range(m):
    a,b = map(int,input().split())
    a,b = min(a,b),max(a,b)
    ab[i] = [a,b]
    kr[a-1].append(b)
    kr[b-1].append(a)

dis = 1
while len(qn) > 0:
    v = qn.popleft()
    d = dist[v-1]
    for w in kr[v-1]:
        if dist[w-1] > -1:
            continue
        dist[w-1] = d + 1
        qn.append(w)
        ans[w-1] = v


#print(dist)

#ab.sort()
#print(ab)
#print(kr)

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