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

def mapinput():
    return map(int,input().split())

n,m = mapinput()
rootlist = [[] for i in range(n)]
flag = [False for i in range(n)]

for i in range(m):
    a,b= mapinput()
    rootlist[a-1].append(b)
    rootlist[b-1].append(a)

que = deque()
que.append(1)
while len(que) !=0:
    now = que.popleft()
    for room in rootlist[now-1]:
        if flag[room-1] == False:
            flag[room-1] = now
            que.append(room)

print('Yes')
for root in flag[1:]:
    print(root)

Submission status: Accepted

Solution code:
from collections import deque

def mapinput():
    return map(int,input().split())

n,m = mapinput()
rootlist = [[] for i in range(n)]
flag = [False for i in range(n)]

for i in range(m):
    a,b= mapinput()
    rootlist[a-1].append(b)
    rootlist[b-1].append(a)

que = deque()
que.append(1)
while len(que) !=0:
    now = que.popleft()
    for room in rootlist[now-1]:
        if flag[room-1] == False:
            flag[room-1] = now
            que.append(room)

print('Yes')
for i,root in enumerate(flag):#スライスで実装
    if i == 0:
        continue
    print(root)

Submission status: Accepted

Solution code:
from collections import deque

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

grid = [[] for _ in range(n + 1)]

ans = [0] * n
visited = [False] * n
visited[0] = True

for _ in range(m):
  s, t = map(int, input().split())
  grid[s].append(t)
  grid[t].append(s)

queue = deque([1])

while queue:
  node = queue.popleft()
  for i in grid[node]:
    if visited[i - 1]:
      continue
    visited[i - 1] = True
    ans[i - 1] = node
    queue.append(i)

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

Submission status: Accepted

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

from collections import deque

def bfs(u): #点uからの最短距離
    memo=[0]*(n+1)
    queue=deque([u])
    d=[None]*(n+1)
    d[u]=0
    while queue:
        v=queue.popleft()
        for i in edges[v]:
            if d[i] is None:
                d[i]=d[v]+1
                queue.append(i)
                memo[i]=v
    return d,memo
d,memo=bfs(1)
print("Yes")
for i in range(2,n+1):
    print(memo[i])

Submission status: Accepted

Solution code:
from collections import deque
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

d = [0] * n
queue = deque([0])
while queue:
    current_node = queue.popleft()
    for next_node in graph[current_node]:
        if d[next_node] == 0:
            d[next_node] = current_node+1
            queue.append(next_node)
print('Yes')
print(*d[1:], sep='\n')

Submission status: Accepted

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

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

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

q = deque([0])
INF = float('inf')
dis = [INF] * n
dis[0] = 0
back = [-1] * n

while q:
    zzz = q.popleft()
    for i in rt[zzz]:
        if dis[zzz] + 1 >= dis[i]:
            continue
        dis[i] = dis[zzz]
        back[i] = zzz + 1
        q.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(i) for i in input().split(' ')]
    
links = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = [int(i) for i in input().split(' ')]
    links[a].append(b)
    links[b].append(a)

q = deque([1])

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

while q:
    i = q.popleft()
    for j in links[i]:
        if results[j] == -1:
            results[j] = i
            q.append(j)

print('Yes')
print('\n'.join(str(i) for i in results[2:]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
import networkx as nx
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

g = nx.Graph()
g.add_edges_from([LIST() for _ in range(M)])
q = deque()
q.append(1)
ans = [None]*N
ans[0] = 0
while q:
	n = q.popleft()
	for node in g[n]:
		if ans[node-1] == None:
			q.append(node)
			ans[node-1] = n
print("Yes")
for i in range(1, N):
	print(ans[i])

Submission status: Accepted

Solution code:
#inport
import sys
import numpy as np
from collections import deque


#input
N,M = [int(x) for x in sys.stdin.readline().split()]
g = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = [int(x) for x in sys.stdin.readline().split()]
    g[a].append(b)
    g[b].append(a)



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

if num_crew == N:
    print('Yes')
    for i in range(N-1):
        print(d[i+2])
else:
    print('No')

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:
import glob
import math


# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\168\\D'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    alph = []

    def rec(self, result, now, max, N):

        if now == N:
            res = ""
            for i in result:
                res += self.alph[i]
            print(res)
            return

        if now == 0:
            result[0] = 0
            self.rec(result, now+1, 0, N)
            return

        for i in range(0, max+2):
            if i == N:
                return
            result[now] = i
            if i > max:
                self.rec(result, now+1, i, N)
            else:
                self.rec(result, now+1, max, N)

    def resolve(self):

        count = 0

        N, M = map(int, self.input_data().split())
        node = [list(map(int, self.input_data().split())) for i in range(M)]
        sp = [[0, 200000] for i in range(N+1)]   # signpost
        path = [[] for i in range(N+1)]
        for n in node:
            path[n[0]].append(n[1])
            path[n[1]].append(n[0])

        next = [1]
        sp[1][1] = 0
        while len(next) != 0:
            now = next.pop(0)
            for n in path[now]:
                if sp[n][1] > sp[now][1]+1:
                    sp[n][0] = now
                    sp[n][1] = sp[now][1]+1
                    next.append(n)


        print('Yes')
        for i in range(2,N+1):
            print(str(sp[i][0]))

solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Accepted

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

AB = dict()

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

    AB.setdefault(b, [])
    AB[b].append(a)

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

a[1] = 0
current = 1
pos = [1]

while True:
    next_pos = []

    for p in pos:
        for n in AB[p]:
            if a[n] == -1:
                a[n] = p
                next_pos.append(n)

    pos = next_pos
    if not pos:
        break

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

Submission status: Accepted

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

#print(graph)

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

d = deque()
d.append(1)

while d: #dの中が空になるまで続ける
  v = d.popleft()#一番最初に入れたものから探索する。
  for i in graph[v]:#vから行けるところを探索。例v=1,i=2, v=2,i=1,3,4
    if dist[i] != -1: #iが未訪問でなければ（=訪問済みであれば）
      continue#何もしない
    dist[i]=v#一個前の探索地点を入れる（一個前がほしいとき）  
#    dist[i] = dist[v] + 1#iのdistにv＋1したものを追加（原点からの距離がほしいとき）
    d.append(i)#訪問リストにiを追加

#print(graph)
#print(dist)
print('Yes')
[print(dist[i]) for i in range(2,n+1)]

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
visited = [float('inf') for i in range(n)]
visited[0] = 0
ans = [float('inf') for i in range(n)]
que = deque()
que.append(0)
while que:
    t = que.popleft()
    for j in edge[t]:
        if visited[j] == float('inf'):
            visited[j] = t+1
            que.append(j)
if float('inf') in visited:
    print("No")
    exit()
print("Yes")
for i in range(1,n):
    print(visited[i])

Submission status: Accepted

Solution code:
from collections import deque

# 頂点数n、辺の本数m
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)

# FIFO(取り出しの順番を決める)
q = deque([])
# 0で初期化
q.append(0)
# 頂点が訪問済かどうかを格納(距離情報を保存)
dist = [-1] * n
dist[0] = 0
# 深さ-1の部屋番号を保存
pre = [-1] * n

while q:
    v = q.popleft()
    for nv in G[v]:
        nv -= 1
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + 1
        pre[nv] = v + 1
        q.append(nv)

if -1 in pre[1:]:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        print(pre[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

from collections import deque

def bfs(graph, queue, prev):
    while queue:
        current = queue.popleft()

        for n in graph[current]:
            if prev[n] != -1:
                continue
            prev[n] = current
            queue.append(n)

queue = deque([1])
prev = [0] + [-1] * n
prev[1] = 0
bfs(graph, queue, prev)

if -1 not in prev:
    print('Yes')
    for i in prev[2:]:
        print(i)
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque([0])
used[0] = 1
while q:
    u = q.popleft()
    for v in G[u]:
        if used[v] == 1:
            continue
        q.append(v)
        used[v] = 1
        prev[v] = u + 1

for i in range(n):
    if used[i] != 1:
        print("No")
        exit()

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

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, input().split())
        G[A].append(B)
        G[B].append(A)
    ans = [0] * (N + 1  )
    ans[1] = 1
    cnt = 1
    q = deque([1])
    while q:
        v = q.popleft()
        for to in G[v]:
            if ans[to] > 0: continue
            ans[to] = v
            q.append(to)
            cnt += 1
    if cnt < N:
        print('No')
        return
    print('Yes')
    for i in range(2, N + 1):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        route[a].append(b)
        route[b].append(a)
    ans = [None]*(n+1)
    q = deque([1])
    while q:
        parent = q.pop()
        children = route[parent]
        for child in children:
            if ans[child] is None:
                ans[child] = parent
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy
import sys
input = sys.stdin.readline
N,M = (int(x) for x in input().split())
connection ={i:[] for i in range(0,N+1)}
connection[0] =[1]
#connection[1] =[0]
#構造入力
for i in range(M):
    a,b = (int(x) for x in input().split())
    connection[a].append(b)
    connection[b].append(a)

# 幅優先探索
parent ={i:-1 for i in range(1,N+1)} #親＝通過済、通過してない部屋はー１
parent[1] =0
children = deque()
children.extend(connection[1])
for i in children:
    parent[i] =1
while children:
    next =children.popleft()

    for i in connection[next]:
        if parent[i] != -1:
            continue
        else:
            parent[i] =next

            children.append(i)
#出力
print("Yes")
for i in range(2,N+1):
    print(parent[i])

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
g = [[] for i in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)
Q = deque()
vstd = [0]*(N+1)
mark = [0]*(N+1)
vstd[1] = 1
Q.append(1)
while Q:
    par = Q.popleft()
    for r in g[par]:
        if vstd[r]:
          continue
        mark[r]=par
        vstd[r]=1
        Q.append(r)
print('Yes')
for mk in mark[2:]:
    print(mk)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
g = [[] for i in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)
Q = deque()
vstd = [0]*(N+1)
mark = [0]*(N+1)
vstd[1] = 1
Q.append(1)
while Q:
    par = Q.popleft()
    for r in g[par]:
        if vstd[r]:
          continue
        else:
          mark[r]=par
          vstd[r]=1
          Q.append(r)
print('Yes')
for mk in mark[2:]:
    print(mk)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
g = [[] for i in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)
Q = deque()
vstd = [0]*(N+1)
mark = [0]*(N+1)
vstd[1] = 1
Q.append(1)
while Q:
    par = Q.popleft()
    for r in g[par]:
        if vstd[r]==0:
            mark[r]=par
            vstd[r]=1
            Q.append(r)
print('Yes')
for mk in mark[2:]:
    print(mk)

Submission status: Accepted

Solution code:
from collections import deque

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

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

d = deque([1])
ans = [-1] * 2 + [0 for i in range(n - 1)]

while d:
    parent = d.popleft()
    for child in t[parent]:
        if ans[child] == 0:
            d.append(child)
            ans[child] = parent

print('Yes')
[print(v) for v in ans[2:]]

Submission status: Accepted

Solution code:
import sys
import sys
import heapq
def dijkstra(s, es):
    '''Single Source Shortest Path (cost must not be negative)
    arguments
        s : source node number
        es: adjacency list
    returns
        cs: shortest path costs to each nodes
    '''
    INF=sys.maxsize
    cs=[INF]*len(es)
    ss=[-1]*len(es)
    cs[s],hq=0,[]
    heapq.heapify(hq)
    heapq.heappush(hq,(cs[s],s))
    while hq:
        d,v=heapq.heappop(hq)
        if cs[v]<d:continue
        for t,c in es[v]:
            if cs[t]>cs[v]+c:
                cs[t]=cs[v]+c
                ss[t]=v
                heapq.heappush(hq,(cs[t],t))
    return cs,ss
def main():
    N,M=tuple(map(int,sys.stdin.readline().split()))
    es=[[] for _ in range(N)]
    for _ in [0]*M:
        a,b=tuple(map(int,sys.stdin.readline().split()))
        a,b=a-1,b-1
        es[a].append((b,1))
        es[b].append((a,1))
    cs,ss=dijkstra(0,es)
    if ss.count(-1)>1:print('No')
    else:
        print('Yes')
        for d in ss[1:]:print(str(d+1))
if __name__=='__main__':main()

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+1)]
    for _ in range(M):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
    ans = [-1]*(N+1)
    Q = deque()
    Q.append(1)
    while len(Q) > 0:
        ima = Q.popleft()
        for tsugi in G[ima]:
            if ans[tsugi] == -1:
                ans[tsugi] = ima
                Q.append(tsugi)
    print("Yes")
    for e in ans[2:]:
        print(e)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
# ab = [list(map(int,input().split())) for i in range(m)]
v = [[0]]*2 + [[10**9] for i in range(n-1)]
# print(v)
for i in range(m):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
q = deque([1])
# print(v)
while q:
    temp = q.popleft()
    for i in v[temp][1:]:
        if v[i][0] == 10**9:
            v[i][0] = temp
            q.append(i)
print("Yes")
for i in v[2:]:
    print(i[0])

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def bfs(G, s, t=None):
    """
    G[v] = [x1, x2,...]
    """
    dist = [-1] * len(G)
    dist[s] = 0
    par = [-1] * len(G)
    q = deque([s])
    while q:
        v = q.popleft()
        for x in G[v]:
            if dist[x] < 0 or dist[x] > dist[v] + 1:
                par[x] = v + 1
                dist[x] = dist[v] + 1
                q.append(x)
    return par


def solve():
    n, m = nm()
    G = [list() for _ in range(n)]
    for _ in range(m):
        u, v = nm()
        u -= 1; v -= 1
        G[u].append(v)
        G[v].append(u)
    par = bfs(G, 0)
    print('Yes')
    print(*par[1:], sep='\n')
    return

solve()

# T = ni()
# for _ in range(T):
#     solve()

Submission status: Accepted

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

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

queue = [0]
dist = [0] * N
prev = [-1] * N
while(len(queue) != 0):
    now = queue[0]
    queue.pop(0)
    for i in loads[now]:
        if dist[i] != 0:
            continue
        else:
            queue.append(i)
            dist[i] = dist[now] + 1
            prev[i] = now + 1
print('Yes')
for i in prev[1:]:
    print(i)

Submission status: Accepted

Solution code:
#abc168d
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
 a,b=map(int,input().split())
 g[a-1].append(b-1)
 g[b-1].append(a-1)
p=[-1]*n
q=[0]
while q:
 i=q.pop(0)
 for j in g[i]:
  if p[j]==-1:
   p[j]=i
   q.append(j)
print('Yes')
for i in range(1,n):
 print(p[i]+1)

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    L = [[0] for _ in range(n)]
    for _ in [0] * m:
        a, b = map(int, input().split())
        L[a-1].append(b-1)
        L[b-1].append(a-1)
    L[0][0] = 1
    ans = [0] * n
    dq = deque([0])
    while dq:
        t = dq.popleft()
        for i in range(1, len(L[t])):
            next = L[t][i]
            if ans[next] != 0:
                continue
            ans[next] = t + 1
            dq.append(next)
        else:
            L[t][0] = 1
    print('Yes')
    print(*ans[1:], sep='\n')

main()

Submission status: Accepted

Solution code:
from collections import deque

WHITE=0
GRAY=1
BLACK=2

nList = []
labelList = []
color = []
Q = deque([])

def readinput():
    global nList
    global color
    global Q
    global labelList

    n,m=list(map(int,input().split()))
    nList = []
    for _ in range(n+1):
        nList.append([])  # 1-オリジンの隣接リスト

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

    labelList = [0]*(n+1)
    color = [WHITE]*(n+1)
    Q = deque([])

    #print(nList)

def bfs(p):
    global Q
    global nList
    global color
    global labelList

    Q.append(p)
    color[p]=GRAY
    #print(Q)
    #print(color)
    while(len(Q)>0):
        current=Q.popleft()
        for next in nList[current]:
            if(color[next]==WHITE):
                Q.append(next)
                color[next]=GRAY
                labelList[next]=current
                #print(Q)
                #print(color)
                #print(labelList)
        color[current]=BLACK

def main():

    bfs(1)


if __name__=='__main__':
    readinput()

    main()
    print('Yes')
    for l in labelList[2:]:
        print(l)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
for _ in range(M):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)

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

q = deque([1])
while q:
    a = q.popleft()
    for b in d[a]:
        if par[b]!=-1:continue
        par[b] = a
        q.append(b)

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(n)]
sirusi=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
D=deque([0])
visited=[False]*n
visited[0]=True
while D:
    v=D.popleft()
    for i in graph[v]:
        if visited[i]:continue
        visited[i]=True
        sirusi[i]=v
        D.append(i)
print("Yes")
for i in range(1,n):
    print(sirusi[i]+1)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ls_pass=[list(map(int,input().split())) for i in range(M)]
#各iと繋がっている部屋の番号
ls=[[] for i in range(N+1)]
for i in range(M):
  ls[ls_pass[i][0]].append(ls_pass[i][1])
  ls[ls_pass[i][1]].append(ls_pass[i][0])
#各部屋に振る道標
ls_mark=[""]*2+[0]*(N-1)

#幅優先探索の実装
from queue import Queue 
S=Queue()
S.put(1)
while not S.empty():
  a=S.get()
  for i in ls[a]:
    if ls_mark[i]==0:
      ls_mark[i]=a
      S.put(i)
if 0 in ls_mark:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(ls_mark[i])

Submission status: Accepted

Solution code:
"""
 - https://atcoder.jp/contests/abc168/tasks/abc168_d
 - 幅優先探索
 - 部屋(d+1)の道しるべが部屋(d)を指すように設定すれば目標を達成できる
"""
from collections import deque
n, m = map(int, input().split()) 
list_init = [0]*(n+1)
c = [[] for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
    
que = deque([1])
check = [0 for i in range(n+1)]
check[1] = 1
while que:
    now = que.popleft()
    nx = c[now]
    for i in nx:
        if check[i] == 1:
            continue
        check[i] = 1
        list_init[i] = now
        que.append(i)
if 0 in list_init[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join(map(str, list_init[2:])))

Submission status: Accepted

Solution code:
# ダミーノード'0'を設定 ※※※
# AtCoder Beginner Contest 168
# https://atcoder.jp/contests/abc168/tasks/abc168_d

import sys
input = sys.stdin.readline

n, m =  map(int, input().split()) # nは頂点の数、mは辺の数
pic = [[] for _ in range(n+1)] # 隣接リスト_初期化 ※※※

for _ in range(m): # 隣接リスト_取り込み
    a, b = map(int, input().split())
    pic[a].append(b) # ※※※
    pic[b].append(a) # ※※※

from collections import deque

def BFS(u): # 'u'を開始位置として各頂点までの距離を探索する関数_dis → 親ノードを探索して'ans'に記録
    queue = deque([u]) # dequeオブジェクトとして初期化、初期値は開始位置の'u'のみ
    dis = [None] * (n+1) # uからの距離を全ノード分初期化 ※※※
    dis[u] = 0 # 開始位置'u'の距離は'0'
    ans = [-1] * (n+1) # 親ノードを記録する
    while queue:
        v = queue.popleft() # 'v'に探索候補のノードを popleft
        for i in pic[v]: # pic[v]: 探索候補のノードに隣接するノードのリスト
            if ans[i] == -1: # 親ノードを記録
                ans[i] = v
            if dis[i] is None:
                dis[i] = dis[v]
                queue.append(i)
    return ans

tmp = BFS(1) # ここは開始位置'1'
print('Yes')
for j in tmp[2:]:
    print(j) # ※※※

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
inf = float('inf')
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,m=reads()
ls=[]
link=[[]for i in range(n)]
for i in range(m):
  a,b=reads()
  a-=1
  b-=1
  link[a].append(b)
  link[b].append(a) 
count=[inf]*n
count[0]=0
#check={i:1 for i in range(n)}
#target=1-1
hoge=[0]
for i in range(n):
    targets=hoge
    hoge=[]
    for target in targets:
        for ele in link[target]:
            if count[ele]==inf:
                count[ele]=target+1
                #link[ele-1].remove(target)
                hoge.append(ele)
    if not hoge:
        break
if inf in count:
    print("No")
    exit()
print("Yes")
for i in count[1:]:
    print(i)

Submission status: Accepted

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

fukasa = [0 for _ in range(n)]
fukasamoto = [0 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = {0}
kouho = 1

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

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

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N, M = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(M)]

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

    #output
    #queue
    from collections import deque

    #iを出発して、ループが形成できるか確認。
    search_stack = deque([1])

    signpost = [-1] * (N+1)

    while search_stack:
        next_position = search_stack.popleft()
        for node in C[next_position]:
            if signpost[node] == -1:
                signpost[node] = next_position
                search_stack.append(node)

    print("Yes")
    for i in range(2, N+1):
        print(signpost[i])
    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    g = [ [] for i 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)

    q = deque([0])
    f = [ -1 ] * n

    while q:
        u = q.popleft()

        for v in g[u]:
            if f[v] == -1:
                f[v] = u
                q.append(v)

    ans = [ f[x] + 1 for x in range(1, n) ]
    print('Yes')
    print("\n".join(map(str, ans)))

main()