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 defaultdict as dd
n, m = map(int, input().split())
Ways = dd(set)
for i in range(m):
    a, b = map(int, input().split())
    Ways[a].add(b)
    Ways[b].add(a)

visited = set([1])
Ans = [0] * (n+1)
stack = [1]
while stack != [] and len(visited) != n:
    temp = []
    for room in stack:
        for next_room in list(Ways[room] - visited):
            Ans[next_room] = room
            visited.add(next_room)
            temp.append(next_room)
    stack = temp

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
def main():
    N, M = map(int,input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int,input().split())
        G[A-1].append(B-1)
        G[B-1].append(A-1)
    Q = deque([0])
    ans = [-1]*N
    while len(Q) > 0:
        ima = Q.popleft()
        for tsugi in G[ima]:
            if ans[tsugi] == -1:
                ans[tsugi] = ima+1
                Q.append(tsugi)
    print("Yes")
    for e in ans[1:]:
        print(e)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

to = [[] for i in range(n + 1)]


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

ans = [-1] * (n+1)


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

while q:
    now = q.popleft()
    for t in to[now]:
        if ans[t] == -1:
            q.append((t))
            ans[t] = now

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

Submission status: Accepted

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

table.add(0)

while len(table) != 0:
    new_table = set()
    for point in table:
        for next_room in room[point]:
            if navi[next_room] != -1:
                continue
            navi[next_room] = point
            new_table.add(next_room)

    table = new_table

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

Submission status: Accepted

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

def main():
    N,M,*ab = map(int, read().split())

    E = [[] for _ in range(N+1)]
    for a, b in zip(*[iter(ab)]*2):
        E[a].append(b)
        E[b].append(a)

    par = [0] * (N+1)
    seen = [-1] * (N+1)
    seen[1] = 0
    queue = deque([1])

    while queue:
        v = queue.popleft()
        for e in E[v]:
            if seen[e] == -1:
                seen[e] = seen[v] + 1
                par[e] = v
                queue.append(e)
    
    for i in range(1, N+1):
        if seen[i] == -1:
            print("No")
            exit()
    
    print("Yes")
    print("\n".join(map(str, par[2:])))

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()


def resolve():
    N, M = LI()
    G = [[] for _ in range(N)]
    for _ in range(M):
        A, B = LI_()
        G[A].append(B)
        G[B].append(A)

    que = collections.deque()
    que.append(0)
    dist = [INF]*N
    dist[0] = 0
    ans = [-1]*N
    while que:
        room_c = que.popleft()
        for room_n in G[room_c]:
            if dist[room_n]>=INF:
                que.append(room_n)
                dist[room_n] = dist[room_c] + 1
                ans[room_n] = room_c
    # print('dist', dist)
    # print('ans', ans)
    if -1 in ans[1:]:
        print('No')
    else:
        print('Yes')
        for i in ans[1:]:
            print(i+1)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

from collections import deque

d_list = [N + 1] * N
queue = deque()
queue.append(0)
d_list[0] = 0
while len(queue) > 0:
	cur = queue.popleft()
	d = d_list[cur] + 1
	for n in edges[cur]:
		d2 = d_list[n]
		if d2 > d:
			d_list[n] = d
			queue.append(n)

d_pair_list = [(d, i) for i, d in enumerate(d_list)]

def check():
	result = [None] * N
	result[0] = -1
	for d, cur in d_pair_list:
		for n in edges[cur]:
			if d_list[n] == d - 1:
				result[cur] = n
				break
		if result[cur] == None:
			return None
	return result

result = check()
if result != None:
	print("Yes")
	for i in range(1, N):
		print(result[i] + 1)
else:
	print("No")

Submission status: Accepted

Solution code:
import collections


def solve(N, M, ABs):
    nextrooms = []
    for _ in range(N):
        nextrooms.append(-1)

    ways = {}
    for a, b in ABs:
        ways.setdefault(a - 1, []).append(b - 1)
        ways.setdefault(b - 1, []).append(a - 1)

    queue = collections.deque()
    queue.append(0)
    while queue:
        room = queue.popleft()
        for nextroom in ways[room]:
            if nextrooms[nextroom] == -1:
                nextrooms[nextroom] = room + 1
                queue.append(nextroom)

    nextrooms[0] = "Yes"
    return "\n".join(str(r) for r in nextrooms)


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

Submission status: Accepted

Solution code:
from collections import deque

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

G = {k: [] for k in range(N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a-1].append(b-1)
    G[b-1].append(a-1)

visited = [-1] * N
visited[0] = 0
que = deque([(0, -1)])

while que:
    ci, p = que.popleft()

    for ni in G[ci]:
        if visited[ni] == -1:
            que.append((ni, ci))
            visited[ni] = ci+1

if -1 in visited:
    print('No')
else:
    print('Yes')
    print(*visited[1:], sep='\n')

Submission status: Accepted

Solution code:
# D - Double Dots

from collections import deque

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

# BFS
parent = {}
queue = deque()
queue.append((1, 1))

while len(queue) > 0:
    p, q = queue.popleft()
    if q in parent: # 訪問済
        continue
    parent[q] = p
    for v in adj[q]:
        queue.append((q, v))

if all(u in parent for u in range(2, n+1)):
    print('Yes')
    for u in range(2, n+1):
        print(parent[u])
else:
    print('No')

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic=defaultdict(list)
for i in range(m):
    a,b=ab[i]
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)

itta=[-1]*n

d=deque([0])
while d:
    tmp=d.popleft()
    for i in range(len(dic[tmp])):
        if itta[dic[tmp][i]]==-1:
            itta[dic[tmp][i]]=tmp
            d.append(dic[tmp][i])

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def dijkstra(n, graph, s):
    dist = [float('inf')] * n
    from_v = [-1] * n
    hq = [(0, s)]
    dist[s] = 0
    while hq:
        c, v = heappop(hq)
        if dist[v] < c:
            continue
        for t, cost in graph[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                from_v[t] = v
                heappush(hq, (dist[t], t))
    return dist, from_v

def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append((b,1))
        graph[b].append((a,1))
    dist, from_v = dijkstra(N, graph, 0)
    if float("inf") in dist:
        print("No")
        sys.exit()
    else:
        print("Yes")
        for ans in from_v[1:]:
            print(ans+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
graph={i:[] for i in range(1,N+1)}
for _ in range(M):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
visited=[False for i in range(N+1)]
par=[-1 for i in range(N+1)]
from collections import deque
d=deque()
visited[1]=True
d.append(1)
e=deque()
while d:
    while d:
        x=d.popleft()
        for node in graph[x]:
            if visited[node]==False:
                par[node]=x
                visited[node]=True
                e.append(node)
    if e:
        d=e
        e=deque()
    else:
        d=deque()
flag=True
for i in range(2,N+1):
    if par[i]<0:
        flag=False
        break
if flag:
    print("Yes")
    for i in range(2,N+1):
        print(par[i])
else:
    print("No")

Submission status: Accepted

Solution code:
import math
import collections

N, M = [int(s) for s in input().split()]
graph = {i:[] for i in range(1, N+1)}
for _ in range(M):
    v1, v2 = [int(s) for s in input().split()]
    graph[v1].append(v2)
    graph[v2].append(v1)

queue = collections.deque([1])
visited = set([1])
pre = dict()
while queue:
    v = queue.popleft()
    for w in graph[v]:
        if w not in visited:
            queue.append(w)
            visited.add(w)
            pre[w] = v
if len(visited) != N:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(pre[i])

Submission status: Accepted

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

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

d = [0]*(N+1)

def bfs(v):
    stack = deque([v])
    while stack:
        v = stack[0]
        if graph[v]:
            w = graph[v].popleft()
            if d[w] == 0:
                d[w] = v
                stack.append(w) 
        else:
            stack.popleft()        

bfs(1)

for i in range(2, N+1):
    if d[i] == 0:
        print("No")
        sys.exit()

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    edge[u].append(v)
    edge[v].append(u)

ans = [-2] * n
def bfs(p, v):
    dq = deque()
    dq.append((p, v))
    while dq:
        p, v = dq.popleft()
        if ans[v] == -1:
            ans[v] = p
        for nv in edge[v]:
            if nv == p:
                continue
            if ans[nv] == -2:
                dq.append((v, nv))
                ans[nv] = -1 

bfs(-1, 0)
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    for item in ans[1:]:
        print(item + 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


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

    """
    幅優先探索
    """

    parent = [-1] * N
    parent[0] = 0
    q = deque([0])

    while q:
        u = q.popleft()
        for v in repn[u]:
            if parent[v] != -1:
                continue
            parent[v] = u
            q.append(v)
    print("Yes")
    for i in range(1, N):
        print(parent[i] + 1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def dijkstra(s):
    used = [1] * N
    dp = [INF] * N
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

INF = 10 ** 18

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

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

dp1 = dijkstra(0)

for i in dp1:
    if i == INF:
        print('No')
        exit()

print('Yes')
for i in range(1, N):
    tmp = dp1[i] - 1
    for j in cost[i]:
        if dp1[j[1]] == tmp:
            print(j[1] + 1)
            break

Submission status: Accepted

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

colist=[]
checks=[0]*n
kyori=[0]*n
mae=[0]*n

for i in range(n):
    colist.append([])

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

#print(colist)

#now=[0]
#tugi=colist[0]
tugi=[0]
checks[0]=1
point=1
turn=1

while point<n and len(tugi)!=0:
    koho=[]
    for t in tugi:
        koho2=colist[t]
        for k2 in koho2:
            if checks[k2]==0:
                checks[k2]=1
                kyori[k2]=turn
                mae[k2]=t
                point+=1
                koho.append(k2)
    tugi=koho
    turn+=1

if point==n:
    print("Yes")
    for i in range(n-1):
        print(mae[1+i]+1)
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque
N,M = list(map(int,input().split()))
edges = [[] for i in range(N+1)]
for i in range(M):
    A,B = list(map(int,input().split()))
    edges[A].append(B)
    edges[B].append(A)

queue = deque()
queue.append(1)

guideposts = [-1]*(N+1)
guideposts[1] = 0
while queue:
    room = queue.popleft()
    for next_room in edges[room]:
        if guideposts[next_room] == -1:
            guideposts[next_room] = room
            queue.append(next_room)

for i in range(2,N+1):
    if guideposts[i] == -1:
        print('No') #なんか常にYesな気がする
        break
else:
    print('Yes')
    for i in range(2,N+1):
        print(guideposts[i])

Submission status: Accepted

Solution code:
from collections import deque
INF = float('inf')
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
dist = [INF] * (N+1)
dist[1] = 0
flag = [-1] * (N+1)
check = 1
q = deque([1])
while q:
  x = q.popleft()
  for nextx in graph[x]:
    if(dist[nextx] != INF):
      continue
    flag[nextx] = x
    dist[nextx] = dist[x] + 1
    q.append(nextx)
print('Yes')
for i in range(2, N+1):
  print(flag[i])

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque([0])
#辺の定義
#辺E(u,v)の重みがw
for _ in range(M):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  E[u].append(v)
  E[v].append(u)

#各頂点が白(0)か黒(1)か
color = [-1 for _ in range(N)]

#dfsで色を塗っていく
#頂点の数をN、辺の数をMとすると、O(N+M)で解ける

color[0] = 0
while q:
  u = q.popleft()
  for v in E[u]:
    if color[v] == -1:
      q.append(v)
      color[v] = u

#各頂点の色を出力
print('Yes')
for i in range(1,N):
  print(color[i]+1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
es = [[] for _ in range(N)]

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


from collections import deque

q = deque()
INF = float("inf")
dist = [INF] * N
dist[0] = 0
come_by = [0] * N
q.append((0,0))
while q:
    cost, curr = q.popleft()
    for nxt in es[curr]:
        if cost + 1 < dist[nxt]:
            dist[nxt] = cost+1
            come_by[nxt] = curr+1
            q.append((dist[nxt], nxt))

print("Yes")
print(*come_by[1:], sep="\n")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

adj=[set() for _ in range(N)]

for a,b in edges:
    adj[a].add(b)
    adj[b].add(a)

start=0
dst=[-1]*N
visited={0}

Q={start}

while Q:
    tmp=set()
    for cur in Q:
        for nex in adj[cur]:
            if nex in visited:
                continue
            dst[nex]=cur
            visited.add(nex)
            tmp.add(nex)
    Q=tmp

print("Yes")
print("\n".join(map(str,[v+1 for v in dst[1:]])))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# ダイクストラ法、自分の部屋から行けるところの中から最小の距離の部屋
N, M = lr()
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist = dijkstra(1)
if INF in dist[1:]:
    print('No'); exit()

answer = [None] * (N+1)
for i in range(2, N+1):
    a = INF
    for c in graph[i]:
        if dist[c] < a:
            a = dist[c]
            answer[i] = str(c)

print('Yes')
print('\n'.join(answer[2:]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
tuuro = []
for i in range(m):
	a,b = map(int,input().split())
	tuuro.append((a-1,b-1))
#行ける部屋は.?
ikeru = [[] for _ in range(n)]
for i,j in tuuro:
	ikeru[i].append(j)
	ikeru[j].append(i)

fukasa = [0 for _ in range(n)]
fukasamoto = [0 for _ in range(n)]
kaisuu = 0
settansaku = set([])
listmada = [0]
setmada = set([0])

while len(setmada) != 0:
	kaisuu += 1
	for i in listmada[:]:
		settansaku.add(i)
		listmada.remove(i)
		setmada.remove(i)
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					listmada.append(k)
					setmada.add(k)
					fukasa[k] = kaisuu
					fukasamoto[k] = i+1

print("Yes")
for i in range(1, n):
	print(fukasamoto[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

YES = "Yes"  # type: str

class Room:
    def __init__(self,index):
        self.index = index
        self.nPath = -1
        self.refs = []

    def connect(self,ref):
        self.refs.append(ref)
        ref.refs.append(self)

    def recSolve(self,queue):
        for r in self.refs:
            if r.nPath == -1:
                queue.append()

    def __str__(self):
        c = ""
        for r in self.refs:
            c += f"{r.index},"
        return f"{self.index}->{c} ({self.nPath})"

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    rooms = [Room(i) for i in range(N)]
    for j in range(M):
        rooms[A[j]-1].connect(rooms[B[j]-1])
    current = deque()
    current.append((rooms[0],0))
    while len(current) > 0:
        next = deque()
        for r in current:
            if r[0].nPath == -1:
                r[0].nPath = r[1]
                for k in r[0].refs:
                    if k.nPath == -1:
                        next.append((k,r[0].index))
        current = next
    # for r in rooms:
    #     print(r)
    print(YES)
    for r in rooms[1:]:
        print(r.nPath+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:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))
n,m=l_in()

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

for _ in range(m):
    a,b=l_in()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

from collections import deque    
vis = set()
vis.add(0)

marks = [-1]*n

q = deque()
q.append(0)

while len(q) > 0:
    u = q.popleft()

    for v in edges[u]:
        if v not in vis:
            q.append(v)
            marks[v] = u
            vis.add(v)


print("Yes")
[print(u+1) for u in marks[1:]]

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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

    root = [[] for _ in range(N + 1)]
    for a, b in AB:
        root[a].append(b)
        root[b].append(a)

    que = deque()
    que.append(1)
    front = [-1] * (N + 1)
    front[1] = 1
    while que:
        point = que.popleft()
        for i in root[point]:
            if front[i] > 0:
                continue
            front[i] = point
            que.append(i)

    if min(front[1:]) < 0:
        print('No')
    else:
        print('Yes')
        for i in range(2, N + 1):
            print(front[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
data = [list(map(int,input().split())) for i in range(M)]

A = {}
for i in range(1,N+1):
    A[i] = []

for a,b in data:
    A[a].append(b)
    A[b].append(a)

from collections import deque

q = deque([1])
d = [-1]*(N+1)
d[1] = 0

while q:
    n = q.pop()
    for i in A[n]:
        if d[i] != -1:
            continue
        else:
            d[i] = n
            q.appendleft(i)
print('Yes')

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

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    E = defaultdict(list)
    michi = [-1] * (N+1)
    for _ in range(M):
        a, b = ZZ()
        E[a].append(b)
        E[b].append(a)

    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        if v == 1: michi[v] = 0
        for to in E[v]:
            if michi[to] != -1: continue
            michi[to] = v
            d.append(to)
    print('Yes')
    print(*michi[2:], sep='\n')

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import queue


n,m = readints()
path  =[[] for i in range(n)]

for i in range(m):
    a,b = readints()
    a-=1
    b-=1
    path[a].append(b)
    path[b].append(a)
d = [[] for i in range(n)]
d[0].append(0)

q = queue.Queue()
q.put(0)
visited = [-1]*n
visited[0]=0

ans = [0]*n

while not q.empty():
    p = q.get()
    for x in path[p]:
        if visited[x]==-1:
            visited[x]=visited[p]+1
            d[visited[x]].append(x)
            q.put(x)
            ans[x]=p+1

print('Yes')
printrows(ans[1:])

Submission status: Accepted

Solution code:
[N,M] = list(map(int,input().split()))
G = [[] for i in range(N)]

for i in range(M):
    Atmp,Btmp = list(map(int,input().split()))
    G[Atmp-1].append(Btmp-1)
    G[Btmp-1].append(Atmp-1)

out = [None]*N

from collections import deque

dist = [None]*N
que = deque([0])
out[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] is not None:
            continue
        dist[w] = 1
        out[w] = v
        que.append(w)

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

Submission status: Accepted

Solution code:
from collections import deque

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)

next_v = deque([0])
history = [-1]*n
INF = 10**18
dist = [INF]*n
dist[0] = 0
while next_v:
    v = next_v.popleft()

    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        history[v2] = v
        next_v.append(v2)


print('Yes')
for x in history[1:]:
    print(x+1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

q = deque([])
q.append(0)

is_visited = [False] * N
pre_room = [-1] * N

while(len(q) != 0):
    tmp = q.popleft()
    is_visited[tmp] = True

    for i in to[tmp]:
        if is_visited[i]:
            continue
        q.append(i)
        is_visited[i] = True
        pre_room[i] = tmp

for i in range(1, N):
    if i == -1:
        print("No")
        exit()

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

Submission status: Accepted

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

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

mae = [-1]*n
from collections import deque
def bfs(v):
    queue = deque([])
    d = [None]*n
    d[v] = 0
    queue.append(v)
    while queue:
        u = queue.popleft()
        for i in g[u]:
            if d[i] is None:
                d[i] = d[u] + 1
                mae[i] = u
                queue.append(i)
    return d
d = bfs(0)
print("Yes")
for i in mae[1:]:
    print(i + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    dist = [-1] * N
    before = [-1] * N
    dist[0] = 0
    q = deque([0])
    while q:
        v = q.popleft()
        for e in G[v]:
            if dist[e] >= 0:
                continue
            dist[e] = dist[v] + 1
            before[e] = v + 1
            q.append(e)
    flag = True
    for i in range(N):
        if dist[i] < 0:
            flag = False
            break

    if flag:
        print('Yes')
        print('\n'.join(map(str,before[1:])))
    else:
        print('No')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n, M = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [[b, 1]]
  graph[b] += [[a, 1]]

def dijkstra(s):
  dist = [float('inf')]*n
  dist[s] = 0
  num = [0]*n
  num[s] = 1
  q = [[0, s]]
  pre = [0]*n
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
        pre[v] = u
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num, pre

dist, num, pre = dijkstra(0)
print('Yes')
for i in pre[1:]:
  print(i+1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

answers = [0 for i in range(n)]

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

d = deque()
d.append(0)

seen = {}
will_seen = {}

while len(seen) < n:
    pos = d.popleft()
    if seen.get(pos, None) is not None:
        continue
    else:
        for next_pos in roads[pos]:
            if will_seen.get(next_pos, None) is None:
                d.append(next_pos)
                answers[next_pos] = pos + 1
                will_seen[next_pos] = 1
            seen[pos] = 1

print("Yes")
for ans in answers[1:]:
    print(ans)