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

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    AB = {m + 1: [] for m in range(M+1)}
    for _ in range(M):
        a, b = il()
        AB[a].append(b)
        AB[b].append(a)

    visit = [0] * (N + 1)
    fifoqu = queue.Queue()
    fifoqu.put(1)

    while not fifoqu.empty():
        now = fifoqu.get()
        next = AB[now]
        for n in next:
            if visit[n] != 0:
                continue
            visit[n] = visit[now] + 1
            fifoqu.put(n)
    else:
        if visit[1] == 0:
            print('No')
            exit()
        else:
            visit[1] = 0
            print('Yes')
            for n in range(2, N + 1):
                deep = visit[n]
                rooms = AB[n]
                for room in rooms:
                    if visit[room] == deep - 1:
                        print(room)
                        break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    AB = {m + 1: [] for m in range(M+1)}
    for _ in range(M):
        a, b = il()
        AB[a].append(b)
        AB[b].append(a)

    ret = []
    visit = [0] * (N + 1)
    fifoqu = queue.Queue()
    fifoqu.put(1)

    while not fifoqu.empty():
        now = fifoqu.get()
        next = AB[now]
        for n in next:
            if visit[n] != 0:
                continue
            visit[n] = visit[now] + 1
            fifoqu.put(n)
    else:
        if visit[1] == 0:
            print('No')
            exit()
        else:
            visit[1] = 0
            print('Yes')
            for n in range(2, N + 1):
                deep = visit[n]
                rooms = AB[n]
                for room in rooms:
                    if visit[room] == deep - 1:
                        print(room)
                        break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

# 頂点数と辺数
N, M = map(int, input().split())
# 辺
AB = [map(int, input().split()) for _ in range(M)]

# 無向グラフの隣接リスト設定
link = [[] for _ in range(N + 1)]
for a, b in AB:
  link[a].append(b)
  link[b].append(a)

# BFSのデータフレーム
dist = [-1] * (N + 1)  # 看板未設定
que = deque([1])       # 頂点1を始点とした訪問キュー

# BFS 開始 (キューが空になるまで探索を行う)
while que:
    v = que.popleft() # キューから先頭頂点(現在地)v取得

    for i in link[v]:
      # 未設定頂点iに現在地への看板を設定し訪問キューに追加する
      if dist[i] == -1:
        dist[i] = v
        que.append(i)

# 結果出力（各頂点に設置する看板）
print('Yes')
print('\n'.join(str(v) for v in dist[2:]))

Submission status: Accepted

Solution code:
import sys
import copy
from io import StringIO
import unittest
from collections import deque

# 参考：https://atcoder.jp/contests/abc168/submissions/13401646

def resolve():
    n, m = map(int, input().split())
    ms = [list(map(int, input().split())) for i in range(m)]

    # 各部屋のつながりを整理整頓する(添え字0は使わないので、+1して一つ多い配列を作成)
    roots = [[] for i in range(n + 1)]
    for i in ms:
        roots[i[0]].append(i[1])
        roots[i[1]].append(i[0])

    # 各部屋の深さを保持する配列を作成(配列は0始まりだが、番号は1始まりなので+1(添え字0は使用しない想定))
    deeps = [99999 for i in range(n + 1)]
    aaa = [False for i in range(n + 1)]

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

    # 調べ終えた道を格納するタプル
    # searched = []

    # 初期値を代入
    que = deque()
    que.append(1)  # スタート地点
    deeps[1] = 0  # スタート地点の深さは0

    # BFS開始
    while not len(que) is 0:

        now = que.popleft()

        # 無限ループ防止のため調査済みフラグを立てる
        # searched.append(now)

        # 最適解を代入し続けて、適切な深さを求める
        for target in roots[now]:
            # 調査済みの道には何もしない。
            if aaa[target] is True:
                continue

            # 新しい道の場合。最適解を取得+キュー追加
            deeps[target] = deeps[now] + 1
            que.append(target)
            aaa[target] = True
            # 最適な道しるべを設定
            best_signs[target] = now

    # 不要な添え字を削除(0番目=未使用なので不要 1番目=出力しないので不要)
    # del best_signs[0:2]

    # ans = "Yes"
    print("Yes")
    for i in range(2, len(best_signs)):
        # ans = ans + "\n" + str(best_signs[i])
        print(best_signs[i])

    # print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 4
1 2
2 3
3 4
4 2"""
        output = """Yes
1
2
2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6"""
        output = """Yes
6
5
5
1
1"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
#この解答を自分で写経してみる
N,M=map(int,input().split())
AB=[map(int,input().split()) for _ in range(M)]
#map関数を格納したリストを作る
#この_表記で繰り返すという文化に慣れよう

links=[[] for _ in range(N+1)]
#移動先を出力する
#リストの入れ子にしたかったら、最初から入れ子として定義しないといけない
#何か + for _ in range(M)　で、何かをM回繰り返す
for a,b in AB:
#map関数それぞれに対して、値を抽出する
    links[a].append(b)
    links[b].append(a)

from collections import deque
result=[-1]*(N+1)
#これで[-1,-1,,,]のリストは作れる
#各部屋ごとの出力先

q=deque([1])
#始点の定義
while len(q)>0:
    i=q.popleft()
    for j in links[i]:
        if result[j] ==-1:
            result[j] = i
            #新しいものをどんどん加えていくことで、層がどんどん深くなっていく
            q.append(j)
print("Yes")
print("\n".join(str(i) for i in result[2:] ))

Submission status: Accepted

Solution code:
from collections import deque

room_num, path_num = map(int, input().split(" "))
graph = [[] for _ in range(room_num)]
dis = [-1] * room_num
for _ in range(path_num):
    a, b = map(int, input().split(" "))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
dis[0] = 0
q = deque()
q.append(0)
while q:
    pop = q.popleft()
    for n in graph[pop]:
        if dis[n] > 0:
            pass
        else:
            dis[n] = pop+1
            q.append(n)
if -1 in dis:
    print("No")
else:
    del dis[0]
    print("Yes")
    for s in dis:
        print(s)

Submission status: Accepted

Solution code:

from collections import deque

room_num, path_num = map(int, input().split(" "))
graph = [[] for _ in range(room_num)]
dis = [-1] * room_num
count = [0] * room_num
count[0] = 1
for _ in range(path_num):
    a, b = map(int, input().split(" "))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
dis[0] = 0
q = deque()
q.append(0)
while q:
    pop = q.popleft()
    for n in graph[pop]:
        if count[n] ==1:
            continue
        else:
            count[n] = 1
            dis[n] = pop+1
            q.append(n)
if sum(dis) == room_num:
    print("No")
else:
    del dis[0]
    print("Yes")
    for s in dis:
        print(s)

Submission status: Accepted

Solution code:
from collections import deque 

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

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

q = deque()
q.append(1)
ans = [0]*N

while len(q) > 0:
	v = q.popleft()
	for ike in root[v - 1]:
		q.append(ike)
		if(ans[ike - 1] == 0):
			ans[ike - 1] = v

	root[v-1].clear()

print('Yes')
for a in ans[1::]:
	print(a)

Submission status: Accepted

Solution code:
from collections import deque 

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

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

q = deque()
q.append(1)
ans = [0 for _ in range(N)]

while len(q) > 0:
	v = q.popleft()
	for ike in root[v - 1]:
		q.append(ike)
		if(ans[ike - 1] == 0):
			ans[ike - 1] = v

	root[v-1].clear()

print('Yes')
for a in ans[1::]:
	print(a)

Submission status: Accepted

Solution code:
import queue
import math
def dijkstra(i,n,adj):
  pq=queue.PriorityQueue()
  dist=[float("inf") for i in range(n+1)]
  parent=[0]*(n+1)
  dist[i]=0
  pq.put((dist[i],i))
  while(not pq.empty()):
    (x,y)=pq.get()
    for e in adj[y]:
      if dist[y]+1 < dist[e]:
        dist[e]=dist[y]+1
        parent[e]=y
        pq.put((dist[e],e))
  if float('inf') in dist[1:]:
      print('No')
  else:
      print('Yes')
  for p in parent[2:]:
      print(p)

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

Submission status: Accepted

Solution code:
from collections import deque

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

next_r = [float('inf')]*(n+1) #0-index, 道標
next_r[0] = 0
next_r[1] = 0
seen = [0]*(n+1) #0-index, 訪問履歴

#今の部屋から行ける部屋を順番に訪問
#初めての部屋なら、元の部屋のを道しるべに記載
seen[1] = 1
q = deque()
q.append(1)
while q:
    pos = q.popleft()    
    for next_v in g[pos]:
        if seen[next_v] == 1: continue
    
        seen[next_v] = 1
        next_r[next_v] = pos
        q.append(next_v)

if sum(next_r) == float('inf'):
    print('No')
else:
    print('Yes')
    for i in range(2,n+1):
        print(next_r[i])

Submission status: Accepted

Solution code:
import networkx as nx
N,M = map(int, input().split())
E = [list(map(int,input().split())) for i in range(M)]

G = nx.Graph() 
G.add_edges_from(E)
di = nx.predecessor(G, source = 1)

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

Submission status: Accepted

Solution code:
import queue

mod = 998244353
INF = 1<<29
lINF = 1<<35

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

# indexを部屋番号とし、各部屋から繋がる部屋番号をリストに持つ
graph = [[] for _ in range(n)]
for i in range(m):
    x,y = list(map(int,input().split()))
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)
# 各部屋に設定する番号を記録
v = [-1 for _ in range(n)]
# 部屋１は-1以外にする
v[0] = [0]
# queueを作成し部屋１を追加
q = queue.Queue()
q.put(0)
while not q.empty():
    # queueの先頭（今の部屋番号）を取り出す
    x = q.get()
    # 今いる部屋とつながる部屋を順に探索
    for y in graph[x]:
        if v[y] != (-1):
            continue
        q.put(y)
        v[y] = x
print('Yes')
for i in range(1,n):
    print(v[i]+1)

Submission status: Accepted

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

while len(q) > 0:
  node = q.popleft()
  connects = edge_list[node]
  for c in connects:
    if depth_list[c] == -1:
      depth_list[c] = depth_list[node] + 1
      q.append(c)
      ans_list[c] = node
      
if -1 in ans_list:
  print("No")
else:
  print("Yes")
  for _ in ans_list[1:]:
    print(_ + 1)

Submission status: Accepted

Solution code:
from collections import deque
 
N,M=map(int,input().split())
 
graph=[[]for _ in range(N+1)]
 
for _ in range(M):
    A,B=map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)
 
dist=[-1]*(N+1)
dist[0]=0
dist[1]=0
 
D=deque()
D.append(1)
 
while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)
 
print('Yes')
for j in dist[2:]:
    print(j)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
tuna = [[] for i in range(n+1)]
ans = [0 for i in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    tuna[a].append(b)
    tuna[b].append(a)
q = deque()
q.append(1)
while q:
    now = q.popleft()
    saki = tuna[now]
    for i in saki:
        if ans[i] == 0:
            q.append(i)
            ans[i] = now
print("Yes")
for i in range(2,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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((1, b))
    edges[b].append((1, a))

INF = 10 ** 9
dist = [INF] * n
prev = [-1] * n
def dijkstra(s):
    q = [(0, s)]
    dist[s] = 0
    while q:
        v = heappop(q)[1]
        for cost, to in edges[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                prev[to] = v
                heappush(q, (dist[to], to))

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

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(v):
    q = deque()
    prev[v] = -99999
    q.append(v)
    while q:
        v = q.popleft()
        for u in edges[v]:
            if prev[u] == -1:
                prev[u] = v
                q.append(u)

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

Submission status: Accepted

Solution code:
def resolve():
    N, M = [int(i) for i in input().split()]
    AB = [[] for _ in range(N + 1)]
    AB[0] = [1]
    for _ in range(M):
        A, B = [int(i) for i in input().split()]
        AB[A].append(B)
        AB[B].append(A)
    from collections import deque
    dq = deque([1])
    ans = [-1] * (N + 1)
    while len(dq) > 0:
        p = dq.popleft()
        c = AB[p]
        for cc in c:
            if ans[cc] == -1:
                ans[cc] = p
                dq.append(cc)
    if -1 in ans[2:]:
        print("No")
        print(ans, file=sys.stderr)
    else:
        print("Yes")
        for a in ans[2:]:
            print(a)


resolve()

Submission status: Accepted

Solution code:
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)

s=[-1]*N
d=[-1]*N
next=[[] for _ in range(N)]
next[0].append(0)

s[0]=0
d[0]=0


for i in range(N):
  finish=1
  for j in next[i]:
    if d[j]==i:
      for saki in graph[j]:
        if d[saki]==-1:
          d[saki]=i+1
          s[saki]=j
          next[i+1].append(saki)
          finish=0
  if finish==1:
    break

print("Yes")
for i in range(N-1):
  print(s[i+1]+1)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
prev = [-1] * n
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

def bfs(v):
    q = deque()
    visited[v] = True
    q.append(v)
    while q:
        v = q.popleft()
        for child in edges[v]:
            if not visited[child]:
                visited[child] = True
                prev[child] = v
                q.append(child)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

q = deque()
q.append(1)
paths = [-1]*(n + 1)
paths[1] = 0

while q:
    rnum = q.popleft()
    for i in rooms[rnum]:
        if paths[i] == -1:
            paths[i] = rnum
            q.append(i)
print("Yes")
for i in paths[2:]:
    print(i)

Submission status: Accepted

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

import collections

seen = [-1]*(n+1)
todo = collections.deque()

for i in info[1]:
    todo.append(i)
    seen[i] = 1

while len(todo) != 0:
    now = todo.popleft()
    for i in info[now]:
        if seen[i] == -1:
            todo.append(i)
            seen[i] = now

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

Submission status: Accepted

Solution code:
'''
参考
https://www.charter-blog.com/entry/2020/05/18/163000#D--Double-Dots
https://atcoder.jp/contests/abc168/submissions/13442966
BFS（幅優先探索について）
https://qiita.com/drken/items/996d80bcae64649a6580
'''
import collections

N, M = map(int, input().split())
'''
グラフ入力を受け取るためのリストを準備（部屋数分のリスト要素）
（2次元配列の初期化方法に注意）
https://note.nkmk.me/python-list-initialize/
'''
graph = [[] for _ in range(N+1)]    # グラフを用意（本来なら必要なのは部屋数分だがindex+1して出力するのが煩雑なので+1しておく）

for _ in range(M):                  # グラフ入力を受け取る（各通路がどの部屋間をつないでいるか）
    A, B = map(int, input().split())
    graph[A].append(B)              # Aで指定した部屋から通じる部屋Bの番号をAからの通路リストに追加
    graph[B].append(A)              # Bも同様

q = collections.deque([1])          # グラフから取り出した、通路がつながった先の部屋番号を格納するキュー
dest = [-1] * (N+1)                 # 全部屋を「未訪問」で初期化
dest[0] = 1                         # リストの先頭（出力対象外）は「1」にしておく
dest[1] = 1                         # 部屋1も訪問済ということにする（目的地なので）

while q:
    room = q.popleft()              # キューの先頭要素である部屋番号を取り出す（ここをリストにしてしまっていると計算量が増大する）
    for n_room in graph[room]:      # 部屋からの全ての通路で行ける次の部屋について
        if dest[n_room] == -1:
            dest[n_room] = room     # 今いる部屋の番号を格納
            q.append(n_room)        # キューの末尾に次の部屋を追加

if -1 in dest:
    print('No')
else:
    print('Yes')
    print('\n'.join(map(str, dest[2:])))    # 出力は2番目の部屋以降

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        #print("->", g)

    queue = deque([1])
    d = [None] * (N + 1)
    d[0] = 0
    d[1] = 0

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

    if None in d:
        print("No")
    else:
        print("Yes")
        print("\n".join(map(str, d[2:])))


if __name__ == '__main__':
	main()

exit()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

    queue = deque([1])
    d = [None] * (N + 1)
    d[0] = 0
    d[1] = 0

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

    if None in d:
        print("No")
    else:
        print("Yes")
        print("\n".join(map(str, d[2:])))


if __name__ == '__main__':
	main()

exit()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

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

    while queue:
        v = queue.popleft()
        for i in g[v]:
            if not d[i]:
                d[i] = v
                queue.append(i)

    if all(d):
        print("Yes")
        print("\n".join(map(str, d[2:])))
    else:
        print("No")


if __name__ == '__main__':
	main()

exit()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

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

    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] == 0:
                d[i] = v
                queue.append(i)

    if all(d):
        print("Yes")
        print("\n".join(map(str, d[2:])))
    else:
        print("No")


if __name__ == '__main__':
	main()

exit()

Submission status: Accepted

Solution code:
#import sys
from collections import deque


def main():
    #N, M, *AB = map(int, sys.stdin.buffer.read().split())
    N, M, *AB = map(int, open(0).read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        #print("->", g)

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

    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] == 0:
                #d[i] = d[v] + 1
                d[i] = v
                queue.append(i)

    if all(d):
        print("Yes")
        print("\n".join(map(str, d[2:])))
    else:
        print("No")


if __name__ == '__main__':
	main()

exit()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        #print("->", g)

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

    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] == 0:
                #d[i] = d[v] + 1
                d[i] = v
                queue.append(i)

    if all(d):
        print("Yes")
        print("\n".join(map(str, d[2:])))
    else:
        print("No")


if __name__ == '__main__':
	main()

exit()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        #print("->", g)

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

    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] == -1:
                #d[i] = d[v] + 1
                d[i] = v
                queue.append(i)

    if -1 in d:
        print("No")
    else:
        print("Yes")
        print("\n".join(map(str, d[2:])))


if __name__ == '__main__':
	main()

exit()

Submission status: Accepted

Solution code:
from collections import deque

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

links=[[] for _ in range(N+1)]
for a,b in AB:
  links[a].append(b)
  links[b].append(a)
  
result=[-1]*(N+1)
q=deque([1])
while q:
  i=q.popleft()
  for j in links[i]:
    if result[j]==-1:
      result[j]=i
      q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Submission status: Accepted

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


dist=[-1]*(N+1)
dist[0]=0
dist[1]=0
 
D=deque()
D.append(1)

while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)

print('Yes')
for j in dist[2:]:
    print(j)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
way_list = [ [] for _ in range(n)]
ans = [0] * n

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

marked = {0}
que = [0]
for q in que:
    for i in way_list[q]:
        if i in marked:
            continue
        que.append(i)
        marked.add(i)
        ans[i] = q+1
        
if ans.count(0) > 1:
    print("No")
else:
    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+1)]
 
for _ in range(M):
    A,B=map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)
 
dist=[-1]*(N+1)
dist[0]=0
dist[1]=0
 
D=deque()
D.append(1)
 
while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)
 
print('Yes')
for j in dist[2:]:
    print(j)

Submission status: Accepted

Solution code:
from collections import deque
from sys import maxsize
from copy import deepcopy


class Graph:
    def __init__(self, No_of_nodes):
        self.n = No_of_nodes
        self.adj = [[] for i in range(self.n)]

    def addEdge(self, a, b, w):
        self.adj[a].append([b, w])

    def BFS(self, start):
        visited = [False] * self.n
        depth = [0 for i in range(self.n)]
        que = deque()
        q = [start]
        que.append(start)
        visited[start] = True
        ans = ''
        f = 0
        while que:
            s = que.popleft()
            ans += str(s) + ' '
            for i in self.adj[s]:
                if not visited[i[0]]:
                    depth[i[0]] = s
                    que.append(i[0])
                    visited[i[0]] = True
        return depth

    def dijkstra(self, start):
        nxtpoint = [None for i in range(self.n)]
        distance = [maxsize for i in range(self.n)]
        distance[start] = 0
        q = deque()
        q.append(start)
        while len(q) != 0:
            a = q.pop()
            for u in self.adj[a]:
                b, w = u
                if distance[a] + w < distance[b]:
                    distance[b] = distance[a] + w
                    nxtpoint[b] = a
                    q.append(b)
        return nxtpoint


n, m = map(int, input().split())
ls = []
g = Graph(n)
ans = 'Yes\n'
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g.addEdge(a, b, 1)
    g.addEdge(b, a, 1)
point = g.BFS(0)
for i in range(1, n):
    if point[i] is None:
        ans = 'No'
        break
    else:
        ans += str(point[i] + 1) + '\n'
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

dist=[-1]*(N+1)
dist[0]=0
dist[1]=0

D=deque()
D.append(1)

while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)

print('Yes')
for j in dist[2:]:
    print(j)

Submission status: Accepted

Solution code:
(n,m),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*-~n)
for a,b in t:e[a]+=b,;e[b]+=a,
q=[1]
d=[0]*-~n
for v in q:
 for w in e[v]:
  if d[w]<1:d[w]=v;q+=w,
print('Yes',*d[2:])

Submission status: Accepted

Solution code:

from collections import deque

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

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

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Submission status: Accepted

Solution code:
_input = input
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

import queue

#データ読み込み
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]

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

#マップ作成
for route in s:
	t[route[0]].append(route[1])
	t[route[1]].append(route[0])

#ルート作成
saitan = [n+10 for i in range(n+1)]
shirube=[[] for i in range(n+1)]
itta=[0 for i in range(n+1)]


q = queue.Queue()
q.put(1)
saitan[1]=0
while not q.empty():
	i=q.get()
	for j in t[i]:
		itta[j]=1
		if saitan[i]+1 < saitan[j]:
			saitan[j] = saitan[i]+1
			q.put(j)
			shirube[j] = i

if sum(itta) == n:
	print("Yes")
	for i in shirube[2:n+1]:
		print(i)
else:
	print("No")
	
input = _input