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:
# 入力
N, M = map(int, input().split()) # ノード数, エッジ数
edges = [[] for i in range(N)] # エッジ
for i in range(M):
    A, B = map(int, input().split())
    edges[A - 1] += [B - 1]
    edges[B - 1] += [A - 1]

# 幅優先探索
que = [0] # 探索用キュー
ans = [0] + [-1 for i in range(N - 1)] # 未探索ノード 兼 道しるべ
while -1 in ans: # 未探索ノードがある間
    quetmp = que
    que = []
    for node in quetmp: # 探索キュー内のノードに対して
        for neighbor in edges[node]: # 全ての隣接ノードに対して
            if ans[neighbor] == -1: # 未探索なら
                ans[neighbor] = node + 1 # 道しるべを設定
                que += [neighbor] # キューに入れる

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

Submission status: Accepted

Solution code:
import queue
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    p = q.get()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.put(c)
print('Yes')
for x in ans[2:]: print(x)

Submission status: Accepted

Solution code:
import queue
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    p = q.get()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.put(c)
print('Yes')
print(*ans[2:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

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

    p=[-1]*N
    q=deque([0])
    while q:
        i=q.popleft()
        for j in r[i]:
            if p[j] == -1:
                p[j] = i
                q.append(j)
    print('Yes')
    for i in range(1,N):
        print(p[i]+1)

main()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

from collections import deque

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    #グラフの作成
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
#    print(graph)
    #幅優先探索
    q = deque()
    q.append(0)
    seen = [-1]*N
    seen[0] = 0
    while len(q)>0:
        cur = q.popleft()
        lvl = seen[cur]
        for i in graph[cur]:
            if seen[i]==-1:
                #階層
                #seen[i] = lvl + 1
                #親
                seen[i] = cur
                q.append(i)
#    print(seen)
    if min(seen)==-1:
        print('No')
    else:
        print('Yes')
        for i in seen[1:]:
            print(i+1)


if __name__ == '__main__':
    main()

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

rooms = [-1] * N
def bfs(u):
    q = deque()
    q.append(u)
    while 0 < len(q):
        v = q.popleft()
        for e in edges[v]:
            if rooms[e] == -1:
                rooms[e] = v + 1
                q.append(e)

bfs(0)
print("Yes")
print(*rooms[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

while len(q):
    p = q.popleft()
    for x in u[p]:
        if ans[x] == -1:
            ans[x] = p+1
            q.append(x)

ans[0] = 'Yes'

for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

def bfs(n,dict):
    que = deque()
    distance = [-1 for _ in range(n)]
    que.append([1,0,0])
    ans = [0 for _ in range(n)]
    while(len(que) > 0):
        tmp = que.popleft()
        now = tmp[0]
        step = tmp[1]
        prev = tmp[2]
        if distance[now-1] == -1:
            distance[now-1] = step
            ans[now-1] = prev
            for x in dict[now-1]:
                que.append([x,step+1,now])
        else:
            continue
    return ans

def main():
    n,m = map(int,input().split())
    L = [list(map(int,input().split())) for _ in range(m)]
    dict = [[] for _ in range(n)]
    for l in L:
        dict[l[0]-1].append(l[1])
        dict[l[1]-1].append(l[0])
    result = bfs(n,dict)
    print("Yes")
    for x in result[1:]:
        print(x)
main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  N,M=map(int,input().split())

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

  p=[-1]*N
  q=deque([0])
  while q:
    i=q.popleft()
    for j in r[i]:
      if p[j]==-1:
        p[j]=i
        q.append(j)

  print('Yes')
  for i in range(1,N):
    print(p[i]+1)

main()

Submission status: Accepted

Solution code:
from collections import deque

ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,m,l):
    g = creategraph(n,l)
    for i in range(1,len(g)):
        if len(g[i]) == 0:
            print("No")
            return
    navi = bfs(n,g)
    if min(navi[2:]) == 0:
        print("No")
    else:
        print("Yes")
        for i in navi[2:]:
            print(i)
    
def bfs(n,g):
    navi = [0]*(n+1)
    navi[1] = -1
    q = deque()
    q.append(1)
    while len(q) > 0:
        cp = q.popleft()
        np = g[cp]
        for i in np:
            if navi[i] == 0:
                navi[i] = cp
                q.append(i)
    return navi
    
def creategraph(n,l):
    g = {i:[] for i in range(n+1)}
    for a,b in l:
        g[a].append(b)
        g[b].append(a)
    return g

def resolve():
    n,m = mi()
    l = mix(m)
    main(n,m,l)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
d = [[] for _ in range(n+1)]
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    s  = "\n".join(map(str, ans[1:]))
    print(s)

Submission status: Accepted

Solution code:
from collections import deque

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

room_reached = [False] * (N + 1)
room_clue = [-1] * (N + 1)

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

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

q = deque()
q.append(1)

while len(q) > 0:
    start = q.popleft()
    for next_room in room_path_list[start]:
        if not room_reached[next_room]:
            room_reached[next_room] = True
            room_clue[next_room] = start
            q.append(next_room)

print("Yes")
for i in room_clue[2:]:
    print(i)

Submission status: Accepted

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

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

  p=[-1]*N
  q=[0]
  while q:
    i=q.pop(0)
    for j in r[i]:
      if p[j]==-1:
        p[j]=i
        q.append(j)

  print('Yes')
  for i in range(1,N):
    print(p[i]+1)

main()

Submission status: Accepted

Solution code:
import math
import queue

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

# キューの定義
q = queue.Queue()
# キューにデータを挿入
q.put(0)
    
# キューからデータがなくなるまで取り出しを行う
flag = [0]*N 
flag[0]  = 1
ans_list = [0]*N

while(1):
  if(q.empty()):
    break
  num = q.get()
  for n in Map[num]:
    if(flag[n] != 1): # 訪問済みでないなら
      flag[n] = 1 # 訪問済みに
      ans_list[n] = num #　接続ノード(n)の1つ前のノードを今のノード(now)に
      q.put(n) # queueに接続ノードを入れる

print('Yes')
for i in range(1,N):
  print(ans_list[i]+1)

Submission status: Accepted

Solution code:
from collections import deque
dic = {}
def make_map(a, b, dic):
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
N, M = map(int, input().split())
for m in range(M):
    a, b = map(int, input().split())
    make_map(a-1, b-1, dic)
    make_map(b-1, a-1, dic)
queue = deque([0])
count = 0
dekai = 10**5
lenlist = [dekai]*N
lenlist[0] = 0
while queue:
    a = queue.popleft()
    for i in dic[a]:
        if lenlist[i] ==dekai or a == 0:
            queue.append(i)#今までいったことないなら見るリストに追加
            lenlist[i] = a #今いる座標の距離+!が次の座標の距離
print("Yes")
for n in range(1,N, 1):
    print(lenlist[n]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

def intinp():
    return int(input())


n, m = mapint_inp()
graph = [[] for _ in range(n)]
ans = [0]*n

for _ in range(m):
    a, b = mapint_inp()
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a) 

q = deque([0])
visited = [False]*n
visited[0] = True
while q:
    now = q.popleft()
    for i in graph[now]:
        if visited[i]: continue
        visited[i] = True
        ans[i] = now
        q.append(i)

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

Submission status: Accepted

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

p = [-1]*n
p[0] = 0
q = [0]
while len(q)>0:
    u = q.pop(0)
    for v in e[u]:
        if p[v]==-1:
            p[v] = u
            q.append(v)
if min(p)==-1:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(p[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs_tree(graph, v=1):
    """
    graph: グラフ
    v: スタート
    """
    # 矢印がどこを向いているか
    # -1だと未探索
    arrow = [-1]*len(graph) 
    q = deque()
    q.append(v)
    arrow[v] = 0
    while q:
        now = q.popleft()
        for next_v in graph[now]:
            if arrow[next_v] != -1:
                continue
            else:
                q.append(next_v)
                arrow[next_v] = now
    return arrow

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

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

arrow = bfs_tree(graph, 0)

print('Yes')
for i in range(1, N):
    print(arrow[i]+1)

Submission status: Accepted

Solution code:

from collections import deque

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

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

ans = [-1] * (N)

que = deque([0])

while que:
    now = que.popleft()
    for i in l[now]:
        if ans[i] == -1:
            ans[i] = now
            que.append(i)



if(min(ans) == -1):
    print("No")


print("{} ".format('Yes'))
for i in range(1,N):
    print("{} ".format(ans[i] + 1))

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
p = [0]
ans = [0]
for i in range(N):
    p.append(list())
    if i == 0:
        ans.append(0)
    else:
        ans.append(-1)
for i in range(M):
    A, B = map(int, input().split())
    p[A].append(B)
    p[B].append(A)
D = deque([1])
while D:
    ind = D.popleft()
    for i in p[ind]:
        if ans[i] == -1:
            D.append(i)
            ans[i] = ind

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

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
G = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    
dist = [-1] * (N + 1)
que = collections.deque()

dist[1] = 0
que.append(1)

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

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

Submission status: Accepted

Solution code:
#------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
#-------------------game starts now----------------------------------------------------
from collections import defaultdict,deque 
n,m=map(int,input().split())
d=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
l=[0]
dist=[0]*n
l=deque(l)
while(l):
    s=l.popleft()
    for i in d[s]:
        if dist[i]==0:
            dist[i]=s+1
            l.append(i)
if 0 in dist[1:]:
    print("No")
else: 
    print("Yes")
    print(*dist[1:],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque


def bfs(rooms, v=1):
    arrow = [-1] * len(rooms)
    q = deque()
    q.append(v)

    while q:
        now = q.popleft()
        for next_v in rooms[now]:
            if arrow[next_v] != -1:
                continue
            else:
                q.append(next_v)
                arrow[next_v] = now
    return arrow


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

    anss = bfs(rooms)
    print("Yes")
    for ans in anss[2:]:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
G = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    
dist = [-1] * (N + 1)
que = collections.deque()

dist[1] = 0
que.append(1)

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

memo = collections.defaultdict(int)
memo[0] = 1

print('Yes')
for i in range(2, N+1):
    memo[dist[i]] = i
for dis in dist[2:]:
    print(memo[dis-1])

Submission status: Accepted

Solution code:
import math
from queue import Queue

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

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

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

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

q = Queue()
q.put(1)

while (not q.empty()):
    now = q.get()
    for i in root[now]:
        if (check[i] == 0):
            check[i] = now
            q.put(i)

flag = 1
for i in range(2, n + 1):
    if (check[i] == 0):
        flag = 0

if (flag == 1):
    print("Yes")
    for j in range(2, n + 1):
        print(check[j])
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

def bfs(graph,v=1):
    #args:
    #   graph グラフ本体
    #   v 現在注目しているノード（スタート地点）
    arrow = [-1]*len(graph) #矢印がどこを向いているか
    q = deque()
    q.append(v)
    arrow[v] = 0
    while q:

        now = q.popleft()
        for next_v in graph[now]:
            if arrow[next_v] != -1:
                continue
            else:
                q.append(next_v)
                arrow[next_v] = now
    return arrow

def main():
    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)
    answer = bfs(graph)
    print("Yes")
    for ans in answer[2:]: #矢印が置かれているのは2部屋目以降
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

n,m=list(map(int,input().split()))
graph = [[] for i 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 i in range(n)]
v[0] = [0]

q = queue.Queue()
q.put(0)
    
while not q.empty():
  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
q = deque([0])

def dfs():
    while q:
        v = q.popleft()
        for nv in g[v]:
            if p[nv] < 1:
                p[nv] = v + 1
                q.append(nv)
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(lambda x:int(x) - 1,input().split())
    g[a].append(b)
    g[b].append(a)
    # ループ？お互いに辺がある場合やねこれ
p = [0] * n
dfs()
if 0 in p:
    print('No')
else:
    print('Yes',*p[1:],sep='\n')

Submission status: Accepted

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

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    
import collections
que = collections.deque()
que.append(0)
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        if ans[to] == -1:
            ans[to] = x + 1
            que.append(to)
            
print("Yes")
print(*ans[1:],sep="\n")

Submission status: Accepted

Solution code:
import queue

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

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

# 各部屋に設定する番号を記録する
v = [-1 for i in range(N)]  # 全頂点を「未訪問」に初期化
v[0] = 0  # スタート地点を0にする
# queueを作成し部屋1（インデックスは0）を入れる
q = queue.Queue()
q.put(0)

while not q.empty():
    # queueの先頭（今いる部屋の番号）を取り出す
    x = q.get()
    # 今いる部屋と繋がっている部屋を順に探索する
    for y in graph[x]:
        # -1 でない場合は探索済みなのでスキップする
        if v[y] != -1:
            continue
        # あとで探索するためにqueueに入れておく
        q.put(y)
        v[y] = x

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

Submission status: Accepted

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

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    
import collections
que = collections.deque()
que.append(0)
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        if ans[to] == -1:
            ans[to] = x + 1
            que.append(to)
            
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    print(*ans[1:],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

while q:
    now = q.popleft()
    for i in links[now]:
        if dist[i] == -1:
            dist[i] = dist[now] + 1
            michi[i] = now
            q.append(i)

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,stdin.readline().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
queue=[0]
ans=[-1]*n
ans[0]=0
while len(queue)!=0:
    now_check=queue.pop(0)
    for i in ab[now_check]:
        if ans[i]==-1:
            queue.append(i)
            ans[i]=now_check
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
import numpy as np
import sys
import math
from collections import deque

N , M = map(int,input().split())
miti = [ [] for _ in range(N)]
for m in range(M):
    a , b = map(int , input().split())
    if b-1 != 0:
        miti[a-1].append(b-1)
    if a-1 != 0:
        miti[b-1].append(a-1)
visit = [0] * N
point = [ -1 for _ in range(N)]

def bfs():
    G = deque([0])
    visit[0] = 1
    while G:
        m = G.popleft()
        for n in miti[m]:
            if visit[n] == 0 :
                visit[n] = 1
                point[n] = m
                G.append(n)

def solve():
    bfs()
    print("Yes")
    for a in point[1::]:
        print(a+1)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

import sys

input = sys.stdin.readline

#Dequeを用いたBFS
from collections import deque

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

r = [[] for i in range(N+1)] #ノードの初期化

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

miteru = deque([1]) #見てる要素
mita = {1} #見た要素
res = [-1]*(N+1)

while  miteru: 
    now = miteru.popleft()
    x =set( r[now])
    x = x - mita
    for i in x:
        miteru.append(i)
        if res[i] == -1:res[i] =now
        mita.add(i)
    
print("Yes")
for i in res[2:]:
    print(i)
#print("\n".join(res))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
AB = []
ans = [-1] * (n) #####

edge = [[] for _ in range(n)] #edge[i] := 頂点iから伸びてる辺の行き先のリスト #####

for i in range(m):
    a,b = map(int,input().split())
    a-=1; b-=1 #####
    edge[a].append(b)    
    edge[b].append(a)    
    
import collections
que = collections.deque()
que.append(0) #####
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        a = x
        b = to
        
        if ans[b] == -1: #####
            ans[b] = x + 1 #####
            que.append(b)
            
print("Yes")
print(*ans[1:],sep="\n")

Submission status: Accepted

Solution code:
from queue import Queue

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

l = [[] for _ in range(n)]
for a, b in ab:
    l[a-1].append(b-1)
    l[b-1].append(a-1)

q = Queue()
ans = [0] * n
ans[0] = 1
f = [0] * n
f[0] = 1
for v in l[0]:
    q.put((v, 0))
    f[v] = 1
    
cnt = 0
x = 0
while not q.empty():
    i = q.get()
    ans[i[0]] = i[1]+1
    for v in l[i[0]]:
        if f[v] == 0:
            q.put((v, i[0]))
            f[v] = 1

if 0 not in ans:
    print("Yes")
else:
    print("No")
    exit()

for v in ans[1:]:
    print(v)

Submission status: Accepted

Solution code:

#Dequeを用いたBFS
from collections import deque

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

r = [[] for i in range(N+1)] #ノードの初期化

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

miteru = deque([1]) #見てる要素
mita = {1} #見た要素
res = [-1]*(N+1)

while  miteru: 
    now = miteru.popleft()
    x =set( r[now])
    x = x - mita
    for i in x:
        miteru.append(i)
        if res[i] == -1:res[i] =now
        mita.add(i)
    
print("Yes")
for i in res[2:]:
    print(i)
#print("\n".join(res))

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

signposts = [None] * N
que = deque([0])

while que:
    n = que.popleft()
    for room in rooms[n]:
        if signposts[room] is None:
            que.append(room)
            signposts[room] = n + 1

if None in signposts:
    print("No")
else:
    signposts[0] = "Yes"
    for s in signposts:
        print(s)

Submission status: Accepted

Solution code:
import collections
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]
ans = [None] * (N + 1)
G = collections.defaultdict(set)
for a, b in AB:
    G[a].add(b)
    G[b].add(a)
Q = collections.deque([1])
while Q:
    i = Q.popleft()
    for j in G[i]:
        if ans[j] is None:
            Q += [j]
            ans[j] = i
print('Yes')
print('\n'.join(map(str, ans[2:])))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
AB = []
ans = [0] * (n-1)

edge = [[] for _ in range(n+1)] #edge[i] := 頂点iから伸びてる辺の行き先のリスト

for i in range(m):
    a,b = map(int,input().split())
    edge[a].append(b)    
    edge[b].append(a)    
    
import collections
que = collections.deque()
que.append(1)
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        a = x
        b = to
        
        if b!=1 and ans[b-2] == 0:
            ans[b-2] = x
            que.append(b)
            
if 0 in ans:
    print("No")
else:
    print("Yes")
    
    for i in ans:
        print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    parents = [-1]*N
    G = defaultdict(list)
    for _ in range(M):
        a, b = read_ints()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    Q = deque([(0, 0)])
    count = 0
    while len(Q) != 0:
        node, parent = Q.popleft()
        for child in G[node]:
            if child != parent and parents[child] == -1:
                parents[child] = node
                count += 1
                Q.append((child, node))
    if count == N-1:
        print('Yes')
        for p in parents[1:]:
            print(p+1)
    else:
        print('No')


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import queue

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

INF = 1001001001
q = queue.Queue()
dist = [INF for i in range(n)]
pre = [-1 for i in range(n)]
dist[0] = 0
q.put(0)
while not q.empty():
    v = q.get()
    for u in to[v]:
        if dist[u] != INF:
            continue
        dist[u] = dist[v] + 1
        pre[u] = v
        q.put(u)

print('Yes')
for i in range(n):
    if i == 0:
        continue
    print(pre[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)


INF = 10**20
def main():
    N,M = map(int,input().split())

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

    stack = deque([0])
    ans = [0]*N
    visited = set()
    while len(stack) > 0:
        x = stack.popleft()
        for next in graph[x]:
            if not next in visited:
                ans[next] = x
                visited.add(next)
                stack.append(next)

    if len(visited) != N:
        print("No")
    else:
        print("Yes")
        for i in ans[1:]:
            print(i+1)



if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
graph = [[] for i in range(n)]
# print(graph)
seen = [False for i in range(n)]

ans = [0] * (n)
for i in range(0, m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    # print(graph)
q = deque()
q.append(0)
INF = float('inf')
dist = [INF for i in range(n)]
dist[0] = 0
pre = [-1 for i in range(n)]
seen[0] = True
while len(q) > 0:
    v = q.popleft()
    for next_v in graph[v]:
        if seen[next_v]:
            continue
        q.append(next_v)
        seen[next_v] = True
        dist[next_v] = dist[v] + 1
        pre[next_v] = v

print('Yes')

for i in range(1, n):
    ans = pre[i] + 1
    print(ans)