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
import sys

N,M = map(int,input().split())
T = [ [] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
used_1 = [0]*N
used_2 = [0]*N
ans = [0]*N

P = deque([0])
while(len(P)>0):
    c = P.popleft()
    if used_1[c] == 0:
        used_1[c] = 1
        used_2[c] = 1
        for i in T[c]:
            if used_2[i] == 0:
                ans[i] = c+1
                used_2[i] = 1
                P.append(i)
for i in range(N):
    if used_2[i] == 0:
        print("No")
        sys.exit()

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import*
n,m=map(int,input().split())
e = defaultdict(list)
dist = [2**60]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
q = [(0,0)]
dist[0] = 0
prev = [-1]*n
while q:
    s = heappop(q)
    c,v = s
    for u in e[v]:
        if dist[u] > dist[v]+1:
            dist[u] = dist[v]+1
            heappush(q,(dist[u],u))
            prev[u]=v
if -1 in prev[1:]:
    print('No')
else:
    print('Yes')
    for p in prev[1:]:
        print(p+1)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = [int(i) for i in input().split()]
A = [ [int(j)-1 for j in input().split()] for i in range(m)]
G = defaultdict(set)
for i, j in A:
    G[i].add(j)
    G[j].add(i)

visited = [False for i in range(n)]
ans = [-1 for i in range(n)]
def bfs(start):
    Q = []
    visited[start] = True
    Q.append(start)
    while Q:
        v = Q.pop(0)
        for w in G[v]:
            if not visited[w]:
                ans[w] = v
                Q.append(w)
                visited[w] = True
bfs(0)
terminate_flag = False
for i in range(1,n):
    if ans[i] == -1:
        print("No")
        terminate_flag = True
        break
if not terminate_flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i]+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import math
input=sys.stdin.readline


n,m=map(int,input().split())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(m))
node=[[] for _ in range(n)]
d=deque()
ans=[-1]*n
ans[0]=0
d.append(0)
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
while True:
    if not d:
        break
    a=d.popleft()
    l=node[a]
    for i in l:
        if ans[i]==-1:
            d.append(i)
            ans[i]=a+1
if -1 in ans:
    print("No")
    exit()
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    graph = {}
    for i in range(n):
        graph[i+1]=[]
    for i in range(m):
        a,b = map(int,input().split())
        graph[a]+=[b]
        graph[b]+=[a]
    dist = [-1 for i in range(n)]
    ans = [0 for i in range(n)]
    dist[0]=0
    que = [1]
    while len(que)>0:
        q = que.pop(0)
        for v in graph[q]:
            if dist[v-1]!=-1:
                continue
            dist[v-1] = dist[q-1]+1
            ans[v-1] = q
            que.append(v)
    print('Yes')
    for i in range(n-1):
        print(ans[i+1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
def sol():
  n,m=map(int,input().split())
  neighbors={i+1:set() for i in range(n)}
  for i in range(m):
    a,b=map(int,input().split())
    neighbors[a].add(b)
    neighbors[b].add(a)
  res=[0 for _ in range(n)]
  que=deque([1])
  while len(que)>0:
    #print(que)
    a=que.popleft()
    for b in neighbors[a]:
      if res[b-1]==0:
        res[b-1]=a
        que.append(b)
  #print(neighbors,res)
  print('Yes')
  for b in res[1:]:
    print(b)
    
sol()

Submission status: Accepted

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n, m = map(int, input().strip().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        a_temp,b_temp = map(lambda x: int(x) - 1, input().strip().split())
        g[a_temp].append(b_temp)
        g[b_temp].append(a_temp)
    
    usedlist=[-100 for _ in range(n)]
    Q=Queue()

    #
    Q.put(0)
    usedlist[0] = -1
    while not(Q.empty()):
        u=Q.get()
        for v in g[u]:
            if usedlist[v]==-100:
                usedlist[v] = u # usedlist[u] + 1
                Q.put(v)
            else:
                pass
    eprint('g ',end=':\n')
    eprint(g)
    eprint('usedlist ',end=':\n')
    eprint(usedlist)
    print("Yes")
    for i in range(1,n):
        print( usedlist[i]+1)
    
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
edge = [[] for k in range(n)]
for k in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

start = 0

from collections import deque
que = deque([start])
done = {start}
depth = [1e9]  * n
depth[start] = 0
parents = [-1] * n
while True:
    if len(que) == 0:
        break
    now = que.popleft()
    dep = depth[now]
    
    for node in edge[now]:
        if node not in done:
#             if dep < depth[node]:
            depth[node] = dep + 1
            parents[node] = now
            que.append(node)
        done.add(node)
#     done.add(now)
#     print(now)
if max(depth) == 1e9:
    print("No")
else:
    print("Yes")
    for k in range(1, n):
        print(parents[k] + 1)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
from collections import deque
from collections import defaultdict
MOD = 10**9+7

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

stack = deque()
stack.append((1,1))
not_visit = [True]*(N+1)
ans = [0]*(N+1)
while stack:
    now = stack.popleft()
    if not_visit[now[0]]:
        not_visit[now[0]] = False
        ans[now[0]] = now[1]
        for room in lines[now[0]]:
            if not_visit[room]:
                stack.append((room,now[0]))

flag = 0
for i in not_visit[1:]:
    if i:
        flag = 1
        break

if flag == 1:
    print("No")
else:
    print("Yes")
    for i in ans[2:]:
        print(i)

Submission status: Accepted

Solution code:
from collections import deque
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m=INTM()
    roots=[[]for i in range(n)]
    visit=[0]*n
    visit[0]=1
    q=deque([0])
    for i in range(m):
        a,b=INTM()
        roots[a-1].append(b-1)
        roots[b-1].append(a-1)
    while q:
        temp=q.popleft()
        for root in roots[temp]:
            if visit[root]!=0:
                continue
            else:
                q.append(root)
                visit[root]=temp+1
    
    print('Yes')
    for i in visit[1:]:
        print(i)
        

                
if __name__ == '__main__':
    do()

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque


n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
g = defaultdict(list)

for u, v in edges:
    g[u].append(v)
    g[v].append(u)


ans = [0] + [0] * n
queue = deque([(1, 0)])
visited = set()
dist = 0

while queue:
    for _ in range(len(queue)):
        node, pre_node = queue.popleft()
        if node in visited:
            continue
        ans[node] = pre_node
        visited.add(node)
        for n in g[node]:
            if n in visited:
                continue
            queue.append((n, node))
    dist += 1

if len(visited) < n:
    print("No")
else:
    print("Yes")
    for i in range(2, len(ans)):
        print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque


def bfs(s):
    queue = deque([s])
    cv = [0] * n
    cv[s] = 1
    dist[0] = 0
    while queue:
        u = queue.popleft()
        for nxt in adj[u]:
            if not cv[nxt]:
                queue.append(nxt)
                cv[nxt] = 1
                if dist[u] + 1 < dist[nxt]:
                    dist[nxt] = dist[u] + 1
                    parent[nxt] = u


def dfs(u):
    st = [u]
    cv = [0] * n
    dist[0] = 0
    while st:
        u = st.pop()
        if cv[u]:
            continue
        cv[u] = 1
        for nxt in adj[u]:
            if dist[u] + 1 < dist[nxt]:
                parent[nxt] = u
                dist[nxt] = dist[u] + 1
            st.append(nxt)


n, m = [int(item) for item in input().split()]
parent = [-1] * n
dist = [float('inf')] * n
parent[0] = 0
adj = defaultdict(list)
for i in range(m):
    u, v = [int(item) - 1 for item in input().split()]
    adj[u].append(v)
    adj[v].append(u)
bfs(0)
# print(parent, adj)
if -1 in parent:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(parent[i] + 1)

Submission status: Accepted

Solution code:
import queue

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

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

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

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

while not q.empty():
  i = q.get()
  for j in link[i]:
    if j != 0 and mark[j] == -1:
      mark[j] = i
      q.put(j)

flag = True
for i in range(1, n):
  if mark[i] == -1:
    flag = False

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

Submission status: Accepted

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

import sys
import pprint
from collections import deque

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n, m = map(int, sys.stdin.readline().split())
	graph = [[] for i in range(n)]
	for i in range(m):
		ai, bi = map(int, sys.stdin.readline().split())
		graph[ai-1].append(bi-1)
		graph[bi-1].append(ai-1)
	stack = deque([0])
	dist = [-1]*len(graph)
	ans = [-1]*n
	log.print(graph)
	while len(stack) != 0:
		v = stack.popleft()
		d = dist[v]
		nexts = graph[v]
		for next in nexts:
			if dist[next] != -1:
				continue
			dist[next] = d + 1
			ans[next] = v
			stack.append(next)
	if -1 in ans:
		print("No")
	else:
		print("Yes")
		for i in range(1, n):
			print(ans[i]+1)

	


main()

Submission status: Accepted

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

res = [-1]*n
res[0] = 0
q = []
q.append(0)
while len(q) > 0:
    current = q.pop(0)

    for nex in d_list[current]:
        if res[nex] == -1:

            res[nex] = current
            q.append(nex)
if -1 not in res:
    print('Yes')
    for ans in res[1:]:
        print(ans+1)
else:
    print("No")

Submission status: Accepted

Solution code:
import queue
q = queue.Queue()
n, m = map(int, input().split())
mat = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  mat[a-1].append((a-1,b-1))
  mat[b-1].append((b-1,a-1))

d_list = [(-1,-1)]*n

d_list[0] = (0,0)
while len(mat[0]) > 0:
  q.put(mat[0].pop())

while not q.empty():
  u,v = q.get()

  if d_list[v][1] != -1 and d_list[v][1] <= d_list[u][1]+1:
    pass
  else:
    d_list[v] = (u, d_list[u][1]+1)
    while len(mat[v]) > 0:
      q.put(mat[v].pop())
print("Yes")
for i in range(1,n):
  print(d_list[i][0]+1)

Submission status: Accepted

Solution code:
N, M =  map(int, input().split())
path = [[] for _ in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
ans = [-1]*N
def bfs():
  que = [0]
  while len(que)>0:
    a = que.pop(0)
    for i in path[a]:
      if ans[i] == -1:
        ans[i] = a+1
        que.append(i)
  if -1 in ans:
    print("No")
  else:
    print("Yes")
    for i in range(1, N):
      print(ans[i])
if  __name__ == "__main__":
  bfs()

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, M = map(int, readline().split())
    path = [[] for _ in range(N+1)]
    path[0].append(1)
    for _ in range(M):
        a, b = map(int, readline().split())
        path[a].append(b)
        path[b].append(a)
    d = deque([0])
    parents = [0] * (N+1)
    parents[0] = -1
    while d:
        x = d.popleft()
        for i in path[x]:
            if parents[i] == 0:
                parents[i] = x
                d.append(i)
    ans = parents[2:N+1]
    if 0 in ans:
        print('No')
    else:
        print('Yes')
        for i in range(N-1):
            print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())

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

q = deque()
q.append((0, -1))

# 幅優先探索
visited = set()
ans = {} # どの部屋に戻るべきか
while q:
    pos, prev = q.popleft()
    if pos in visited:
        continue
    ans[pos] = prev
    visited.add(pos)

    for next_pos in edges[pos]:
        q.append((next_pos, pos))

if len(ans) != N:
    print("No")
    sys.exit()

print("Yes")
for (pos, prev) in sorted(ans.items()):
    if pos == 0:
        continue
    print(prev+1)

Submission status: Accepted

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

from heapq import heappush, heappop
INF = float("inf")
miti = [-1]*N
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                if miti[t] == -1:
                    miti[t] = v+1
                heappush(que, (dist[t], t))
    return dist

edge = [[] for _ in range(N)]

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

dist = dijkstra(N,edge,0)

if -1 in miti[1:]:
    print("No")
else:
    print("Yes")
    for t in miti[1:]:
        print(t)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n,m = map(int,readline().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
ans = [-1]*n
from collections import deque

que = deque()
que.append((0,1))
chk = [False]*n
chk[0] =True
cnt = 1
while que:
    now,p = que.popleft()
    if cnt == n:
      break
    for i in g[now]:
        if not chk[i]:
          ans[i] = p
          chk[i] = True
          cnt += 1
          que.append((i,i+1))

if cnt!=n:
  print('No')
  exit()
  
print('Yes')
for i in ans[1:]:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

ans=[-1 for _ in range(n)]
ch=[False for _ in range(n)]

def bfs(graph):
    ch[0]=True
    Q=deque()
    Q.append([graph[0],0])

    while len(Q)>0:
        v,y=Q.popleft()

        for e in v:
            if ch[e]==False:
                ch[e]=True
                ans[e]=y
                Q.append([graph[e],e])



bfs(graph)

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

print("Yes")
for i in range(1,len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
memo = [0]*n
now = [[0,0]]
nxt = []
done = [False]*n
done[0] = True


while now:
    for l in now:
        for j in graph[l[1]]:
            if not done[j]:                
                done[j] = True
                nxt.append([l[1],j])
                memo[j] = l[1]+1
    now = copy.copy(nxt)
    nxt = []
for l in now:
    done[l[1]] = True
if False in done:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(memo[i])

Submission status: Accepted

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

out = [0 for _ in range(n)]
out[0] = -1

import queue

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

while not next_visit.empty():
    i = next_visit.get()
    for j in graf[i]:
        if out[j] == 0:
            out[j] = i+1
            next_visit.put(j)
cnt = 1

for i in range(1, n):
    if out[i] == 0:
        cnt = 0
        break
if cnt:
    print("Yes")
    for i in out[1:]:
        print(i)
else:
    print("No")

Submission status: Accepted

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

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

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

ans_li = [-1]*n
ans_li[0] = 1

q = deque()

q.appendleft(0)

while len(q) > 0 :
    for i in range(len(q)):
        tmp = q.popleft()
        #print(tmp)
        for j in range(len(ab[tmp])):
            if ans_li[ab[tmp][j]] == -1:
                ans_li[ab[tmp][j]] = tmp+1
                q.append(ab[tmp][j])
                #print(q)

print('Yes')

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def solve():
    N,M = map(int,input().split())
    G = defaultdict(list)

    for i in range(M):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    visited = [False] * N
    ans = [float('inf')] * N

    q = deque()
    q.append((0,-1))
    visited[0] = True
    while len(q) > 0:
        now,before = q.popleft()
        ans[now] = min(before + 1,ans[now])

        # print("now",now)
        for next in G[now]:
            if not visited[next]:
                # print(next)
                q.append((next,now))
                visited[next] = True


    print('Yes')
    print(*ans[1:],sep='\n')

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
N, M = list(map(int, input().split()))

visited = [False] * (N+1)
visited[0] = True
visited[1] = True
T = defaultdict(list)
for _ in range(M):
    a, b = list(map(int, input().split()))
    T[a].append(b)
    T[b].append(a)

q = deque()
q.append(1)

route = [0] * (N+1)

while q:
    v = q.popleft()
    for n in T[v]:
        if not visited[n]:
            route[n] = v
            q.append(n)
            visited[n] = True

if visited.count(False) > 0:
    print("No")
    sys.exit(0)

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

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
C = [[] for _ in range(N+1)]
for _ in range(M):
    tmp = list(map(int,input().split()))
    C[tmp[0]].append(tmp[1])
    C[tmp[1]].append(tmp[0])
d = [1000000000]*(N+1)
d[1] = 0
visited = [False]*(N+1)
q = deque()
q.append(1)

sirube = [0]*(N+1)
while q:
    node = q.popleft()
    for adj in C[node]:
        if visited[adj] == False:
            sirube[adj] = node
            q.append(adj)
            visited[adj] = True



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

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
def search(l,dic1,dic2):
    if not l:
        return(dic2)
    else:
        x=l.pop()
        for y in dic1[x]:
            if dic2[y]==0:
                l.appendleft(y)
                dic2[y]=x
        return search(l,dic1,dic2)

n,m=map(int,input().split())
l=[i+1 for i in range(n)]
dic1={i:[] for i in l}
dic2={i:0 for i in l}
for _ in range(m):
    a, b = map(int, input().split())
    dic1[a].append(b)
    dic1[b].append(a)
l=deque(dic1[1])
for z in l:
    dic2[z]=1

d=search(l,dic1,dic2)
print('Yes')
for k in range(2,n+1):
    print(dic2[k])

Submission status: Accepted

Solution code:
import numpy as np
from scipy import sparse

n, m = map(int, input().split())
ab = np.array([list(map(int, input().split())) for _ in range(m)])

g = sparse.csr_matrix(([1]*m, (ab[:, 0]-1, ab[:, 1]-1)), shape=(n, n))
_bfo, predecessors = sparse.csgraph.breadth_first_order(g, 0, directed=False)
if all(predecessors[1:] >= 0):
    print('Yes')
    for p in predecessors[1:]:
        print(p+1)
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
li=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    li[a-1].append(b)
    li[b-1].append(a)
ans=[0]*n
a=[[]  for _ in range(n)]
d=deque([1])
while len(d)>0:
    x=d.popleft()
    if ans[x-1]==0:
        ans[x-1]+=1
        for v in li[x-1]:
            if ans[v-1]==0:
                d.append(v)
                a[v-1].append(x)
if sum(ans)==n:
    print("Yes")
    for i in range(1,n):
        print(a[i][0])
else:
    print("No")

Submission status: Accepted

Solution code:
#import numpy as np
import heapq
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')


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+[s])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        pn = minedge[2]
        pns[v] = pn
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, [e[0]+d[v], e[1], v])
    return d

N, M = map(int, input().split())
edge = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    edge[x].append([1, y])
    edge[y].append([1, x])

pns = [0]*N
dijkstra_heap(0)

print('Yes')
for pni in pns[1:]:
    print(pni+1)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
l=[set() for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  l[a-1].add(b-1)
  l[b-1].add(a-1)
ope=[1]*N
ope[0]=0
s={0}
ans=[-1]*N
while len(s):
  news=set()
  for j in s:
    for k in l[j]:
      if ope[k]:
        news.add(k)
        ans[k]=j
        ope[k]=0
  s=news
print('Yes')
for i in range(1,N):
  print(ans[i]+1)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
input = stdin.readline

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

graph = [[] for _ in range(N)]

for a, b in ab:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

seen = [-1] * N

seen[0] = 1


def bfs(x):
    q = deque([])
    q.append(x)

    while q:
        now = q.popleft()

        for nex in graph[now]:
            if seen[nex] != -1:
                continue
            seen[nex] = now + 1
            q.append(nex)


bfs(0)

if - 1 in seen:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(seen[i])

Submission status: Accepted

Solution code:
import math

n, m = map(int, input().split())
ansTimes = [10**6]*(n+1)
ans = [0]*(n+1)
ansTimes[1] = 0
routeList = [[] for j in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    routeList[a].append(b)
    routeList[b].append(a)

checkedList = [0]*(n+1)
tugiChecks = [1]
while tugiChecks != []:
    i = tugiChecks.pop(0)
    for target in routeList[i]:
        if ansTimes[i]+1 < ansTimes[target]:
            ansTimes[target] = ansTimes[i]+1
            ans[target] = i
        if checkedList[target] == 0:
            tugiChecks.append(target)
            checkedList[target] = 1


if 10**6 in ansTimes[1:]:
    print("No")
else:
    print("Yes")
    for i in range(2, n+1):
        print(ans[i])

Submission status: Accepted

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

INF = int(1e10)
MOD = int(1e9 + 7)

def input():
    return stdin.readline()[:-1]

class Dijkstra:
    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) > 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        return prev

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

def main():
    from builtins import int, map
    n, m = map(int,input().split())
    route_map = [dict() for _ in range(n)]
    for i in range(m):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        route_map[u][v] = 1
        route_map[v][u] = 1

    prev = Dijkstra(route_map, 0).execute()
    print("Yes")
    for i in range(1, n):
        print(prev[i] + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

explored = {0}

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

q = deque()
parent = 0
for k in graph[0]:
    ans[k] = 0
    q.append(k)
    explored.add(k)
ans[0] = 0
while len(q) != 0:
    now = q.popleft()
    parent = now
    for node in graph[now]:
        if node not in explored:
            q.append(node)
            ans[node] = parent
            explored.add(node)

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