Problem:


Score: 400 points

Problem Statement

There is a cave.

The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.

It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.

Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.

If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.

Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 2 \times 10^5

1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)

A_i \neq B_i\ (1 \leq i \leq M)

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

If there is no way to place signposts satisfying the objective, print No.

Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

If we place the signposts as described in the sample output, the following happens:

Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.

Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.

Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.

Thus, the objective is satisfied.

Sample Input 2

6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6

Sample Output 2

Yes
6
5
5
1
1

If there are multiple solutions, any of them will be accepted.



Sample input:
4 4
1 2
2 3
3 4
4 2


Sample output:
Yes
1
2
2

Submission status: Accepted

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

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

    distances = [-1] * N
    instructions = [-1] * N
    distances[0] = 0
    d = deque([0])
    while d:
        current_room = d.popleft()
        for next_room in graph[current_room]:
            if distances[next_room] == -1 or distances[current_room] + 1 < distances[next_room]:
                distances[next_room] = distances[current_room] + 1
                instructions[next_room] = current_room
                d.append(next_room)
    print('Yes')
    for v in instructions[1:]:
        print(v+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

from collections import deque

INF = 10**9+1
steps = [INF] * (N+1)
mk = [0] * (N+1)
ck = deque([1])
steps[1] = 0

while len(ck)>0:
    i = ck.popleft()
    current = steps[i]
    for j in rooms[i]:
        if steps[j] > current+1:
            ck.append(j)
            steps[j] = current+1
            mk[j] = i

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
import numpy as np
class edge(object):
    def __init__(self, to, rev):
        self.to = to
        self.rev = rev
def add_edge(from_, to_, G):
    G[from_].append(edge(to_, len(G[to_])))
    G[to_].append(edge(from_, len(G[from_])-1))

def bfs(src, level, li, li_from):
    que = deque([src])
    level[src] = 0
    while len(que)!=0:
        v = que.popleft()
        for i in range(len(li[v])):
            e = li[v][i]
            if level[e.to]<0:
                level[e.to] = level[v]+1
                li_from[e.to] = v
                que.append(e.to)

n,m = map(int, input().split())
li = []
for i in range(n):
    li.append([])
for i in range(m):
    a, b = map(int,  stdin.readline().split())
    if a > b:
        a, b = b, a
    add_edge(a-1, b-1, li)


if len(li[0])==0:
    print("No")
else:
    print("Yes")
    level = np.full(n, -1, dtype=np.int)
    li_from = np.full(n, -1, dtype=np.int)
    bfs(0,level,li, li_from)
    for i in li_from:
        if i==-1:
            continue
        print(i+1)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

q = deque()
q.append(0)
ans = [0]*N
while q:
    par = q.popleft()
    for e in E[par]:
        if ans[e] > 0:
            continue
        ans[e] = par+1
        q.append(e)

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]

for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
def bfs(u):
    queue = deque([u])
    d = [None]*n
    
    d[u] = 0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v]+1
                queue.append(i)
    return d


d = bfs(0)
print('Yes')
for i in range(1,n):
    for j in g[i]:
        if d[j]<d[i]:
            print(j+1)
            break

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n, m = map(int, input().split())
    es = [[] for _ in range(n+1)]
    ans = [0 for _ in range(n+1)]

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

    q = deque([1])
    while len(q) > 0:
        p = q.popleft()

        for t in es[p]:
            if ans[t] > 0:
                continue
            ans[t] = p
            q.append(t)

    if 0 in ans[2:]:
        print("No")
    else:
        print("Yes")
        for a in ans[2:]:
            print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue


def main():
    n, m = map(int, input().split())
    es = [[] for _ in range(n+1)]
    ans = [0 for _ in range(n+1)]

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

    q = queue.Queue()
    q.put(1)
    while not q.empty():
        p = q.get()

        for t in es[p]:
            if ans[t] > 0:
                continue
            ans[t] = p
            q.put(t)

    if 0 in ans[2:]:
        print("No")
    else:
        print("Yes")
        for a in ans[2:]:
            print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

for _ in range(m):
    x, y = map(int, input().split())
    V[x].append(y)
    V[y].append(x)

d = deque([1])

while d:
    l = d.popleft()
    for v in V[l]:
        if ans[v] != -1:
            continue
        ans[v] = l
        d.append(v)
        

    
if ans.count(-1) > 0:
    print('No')
else :
    print('Yes')
    print(*ans[2:], sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
path = defaultdict(list)

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

prev = [0] * N
dist = [0] * N
q = deque([0])

while (len(q) > 0):
    a = q.popleft()
    for b in path[a]:
        if dist[b] != 0:continue
        q.append(b)
        prev[b] = a
        dist[b] = dist[a] + 1

print('Yes')

for a in prev[1:]:
    a += 1
    print(a)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(int,input().split())

from collections import deque
links = [[] for _ in range(N+1)]
for i in range(M):
    links[A[i]].append(B[i])
    links[B[i]].append(A[i])

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*
(n,m),*c = [[*map(int,i.split())]for i in open(0)]
g = [[]for _ in range(n+1)]

for a,b in c:
    g[a]+=[b]
    g[b]+=[a]

q=deque([1])
r=[0]*(n+1)

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

print("Yes",*r[2:],sep="\n")

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        sign[u] = v
        dfs(u,v)

def bfs(v):
    que = deque([])
    que.append(v)
    while que:
        p = que.popleft()
        if visited[p] == 0:
            visited[p] = 1
            for u in graph[v]:
                que.append(u)

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (N+1) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for u in graph[v]:
            tmp = 1 + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                path[u] = v
                heapq.heappush(hq, (tmp, u))
    return path

N,M = map(int,input().split())
graph = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
path = [0]*(N+1)
c = dijkstra(1)
print("Yes")
for i in range(2,N+1):
    print(c[i])

Submission status: Accepted

Solution code:
from collections import deque
N , M = map(int,input().split())
g = [[] for _ in range(N)]
for _ in range(M):
    a,b = [int(x) for x in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
branch_list = [0 for i in range(N)]
def bfs(u):
    queue = deque([u])
    d = [None] *N
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] +1
                queue.append(i)
                branch_list[i] = v +1
    return d
d = bfs(0)
for i in range(1,len(branch_list)):
    if branch_list[i] == 0:
        print("No")
        break
    if i == 1:
        print("Yes")
    print(branch_list[i])

Submission status: Accepted

Solution code:
from collections import deque

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

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

tai = [False] * (n+1)
tai[1] == True
ans = [0] * (n+1)

tri = deque([1])
while len(tri) > 0:
    num = tri.popleft()
    for i in lst[num]:
        if tai[i]:
            continue
        tri.append(i)
        tai[i] = True
        ans[i] = num

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

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
ans = [-1] * (n - 1)
used = [0]*n
used[0] = 1
que = deque([0])
while que:
    posi = que.popleft()
    for p in graph[posi]:
        if not used[p]:
            que.append(p)
            ans[p-1] = posi+1
            used[p] = 1
print('Yes')
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
V=[[]for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
print('Yes')
p,q=0,[0]
seen=[0]*N
d=[0]*N
while len(q)!=p:
    for i in V[q[p]]:
        if not seen[i]:
            q.append(i)
            d[i]=q[p]+1
        seen[i]+=1
    p+=1
d.pop(0)
for i in d:print(i)

Submission status: Accepted

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

visited = set()
ans = [0]*n
stack = [0]
for i in stack:
    # このへんあやしい
    for j in AB[i]:
        if j in visited:
            continue
        visited.add(j)
        ans[j] = i+1
        stack.append(j)
    # このへんまで
for i in ans[1:]:
    if i==0:
        print('No')
        exit()
print('Yes')
for i in ans[1:]:
    print(i)

Submission status: Accepted

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

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

used = [False]*(N+1)
used[1] = True

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

cand = deque([1])
while len(cand)>0:
    tar = cand.popleft()
    for each in Es[tar]:
        if used[each]:
            continue
        cand.append(each)
        ans[each]=tar
        used[each]= True

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

Submission status: Accepted

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


from collections import deque

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

    labeled = [False] * (N+1)
    # 部屋1は道しるべを付与済み
    labeled[1] = True

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

    queue = deque([1])

    while len(queue) > 0:
        room = queue.popleft()
        nexts = next_rooms[room]
        for n in nexts:
            if labeled[n]:
                continue
            labels[n] = room
            labeled[n] = True
            queue.append(n)

    for i in range(1, N+1):
        if not labeled[i]:
            print("No")
            return

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


main()

Submission status: Accepted

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

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

# 1の部屋からBFSして、初めて来た部屋だったら直前の部屋番号(+1)を入れる
ans = [None] * N

from collections import deque
q = deque([])

q.append((0, -1))
while q:
  v, parent = q.popleft()
  if ans[v] is not None:
    continue
  ans[v] = parent + 1
  for child in G[v]:
    if child == parent:
      continue
    q.append((child, v))

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

q = deque()
q.append(0)
used = {0}
while q:
  node = q.popleft()
  for next_node in graph[node]:
    if next_node in used:
      continue
    q.append(next_node)
    used.add(next_node)
    ans[next_node - 1] = node + 1

print('Yes')
print(*ans, sep='\n')

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, dist, prev):
    while queue:
        current = queue.popleft()

        for _next in graph[current]:
            if dist[_next] != -1:
                continue
            else:
                dist[_next] = dist[current] + 1
                prev[_next] = current
                queue.append(_next)

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for _ in range(n+1)]
dist = [0] * (n+1)
visited = [0] * (n+1)


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

root = 1
visited[root] = 1
d  = deque([root])

while d:
    v = d.popleft()
    for i in graph[v]:
        if visited[i]:
            continue
        visited[i] = 1
        dist[i] = v
        d.append(i)

print('Yes')
ans = dist[2:]
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(m)]
g = [[] for _ in range(n)]
l = [float('inf')] * n

for x,y in li:
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

def bfs():
    que = deque()
    l[0] = 0
    que.append(0)
    while que:
        a = que.popleft()
        for i in g[a]:
            if l[i] != float('inf'):continue
            l[i] = a
            que.append(i)
bfs()
for i in l:
    if i == float('inf'):
        print('No')
        exit()
print('Yes')
for i in l[1:]:
    print(i+1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
t = [[i+1] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    t[A-1].append(B)
    t[B-1].append(A)
from collections import deque
d = deque()
ans = [-1]*(N)
d.append(t[0])
while len(d) > 0:
    z = d.popleft()
    x = z[0]
    for i in range(1,len(z)):
        if ans[z[i]-1] == -1:
            ans[z[i]-1] = x
            d.append(t[z[i]-1])
print("Yes")
for i in range(1,len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
INF = 1_000_000_000
def main():
    n, m = map(int, input().split(" "))
    to = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda i:int(i)-1, input().split(" "))
        to[a].append(b)
        to[b].append(a)
    que = deque()
    d = {i:INF for i in range(n)}
    prev = {i:-1 for i in range(n)}
    d[0] = 0
    que.append(0)
    while que:
        v = que.popleft()
        for i in to[v]:
            if d[i] != INF: continue
            d[i] = d[v] + 1
            prev[i] = v
            que.append(i)
    print("Yes")
    for i in range(n):
        if i == 0: continue
        print(prev[i]+1)
        
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)]  # 各ノードと隣接するノード
    INF = 10 ** 12

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

    d = deque()
    d.append(0)
    dist = [0] + [INF] * (n - 1)  # 根からの距離
    pre = [-1] * n  # 各ノードの親

    while d:
        u = d.popleft()
        for v in route[u]:
            if dist[v] != INF:
                continue
            dist[v] = dist[u] + 1
            pre[v] = u
            d.append(v)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  adj_list[_].append(__)
  adj_list[__].append(_)
  
distance = [None for i in range(n)]
updated_from = [None for i in range(n)]

newly_visited = deque([0])
distance[0] = 0

while len(newly_visited) > 0:
  now = newly_visited.popleft()
  for i in adj_list[now]:
    if distance[i] is not None: continue
    newly_visited.append(i)
    distance[i] = distance[now] + 1
    updated_from[i] = now

# i に到達できてれば distance[i] ==（0 から i までの距離）
# i に到達できてなければ distance[i] == None   
    
"""
print(distance)

for i in range(n):
  # i から 0 に行く経路を求める
  now = i
  path = [now]
  while now != 0:
    now = updated_from[now]
    path.append(now)
  print(i, path) 
"""

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

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    
def bfs(u):
    queue = deque([u])
    d = [None]*n
    
    d[u] = 0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v]+1
                p[i] = v
                queue.append(i)
    return d

p = [None]*n
d = bfs(0)
if None in p[1:]:
    print('No')
else:
    print('Yes')
        
for q in range(1,n):
    print(int(p[q])+1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    
def bfs(u):
    queue = deque([u])
    d = [None]*n
    
    d[u] = 0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v]+1
                p[i] = v
                queue.append(i)
    return d

p = [None]*n
d = bfs(0)
if None in p[1:]:
    print('No')
else:
    print('Yes')
        
for q in range(1,len(p)):
    print(int(p[q])+1)

Submission status: Accepted

Solution code:
# 参考にした提出:https://atcoder.jp/contests/abc168/submissions/16604668 #
from collections import deque
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
d = [-1] * (n+1)
d[0],d[1] = 0,0
queue = deque()
queue.append(1)
while queue:
    x = queue.popleft()
    for i in l[x]:
        if d[i] == -1:
            d[i] = x
            queue.append(i)
print('Yes')
for i in d[2:]:
    print(i)

Submission status: Accepted

Solution code:
# 参考にした提出:https://atcoder.jp/contests/abc168/submissions/16604668 #
from collections import deque
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
d = [-1] * (n+1)
d[0],d[1] = 0,0
queue = deque()
queue.append(1)
while queue:
    x = queue.popleft()
    for i in l[x]:
        if d[i] == -1:
            d[i] = x
            queue.append(i)
if -1 in d:
    print('No')
else:
    print('Yes')
    for i in d[2:]:
        print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(M):
  a,b = map(int,input().split())
  room_g[a].append(b)
  room_g[b].append(a)
  
sign = [-1]*(N+1)
sign[0] = 0
sign[1] = 0

d = deque()
d.append(1)

while d:
  x = d.popleft()
  for i in room_g[x]:
    if sign[i] != -1:
      continue
    sign[i] = x
    d.append(i)
    
ans = sign[2:]
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

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

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

INF = float('inf')
dist = [INF]*n
dist[0] = 0

pre = [-1]*n

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

while que:
    v = que.popleft()
    for u in to[v]:
        if dist[u] != INF:continue
        dist[u] = v + 1
        pre[u] = v
        que.append(u)
print("Yes")
for i in range(1,n):
    print(dist[i])

Submission status: Accepted

Solution code:
from collections import deque

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

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

c = [0]*n
que = deque([])
que.append(0)

while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1,n):
    print(c[i])

Submission status: Accepted

Solution code:
# ABC 168 D
from collections import deque

N,M=map(int,input().split())
G=[[] for _ in [0]*(N+1)]
for _ in [0]*M:
    a,b=map(int,input().split())
    G[a]+=[b]
    G[b]+=[a]

F=[-1]*(N+1)
q=deque()
q.append((1,1))
while q:
    room,par=q.popleft()
    if F[room]>0:
        continue
    F[room]=par
    for nroom in G[room]:
        q.append((nroom,room))
        
print('Yes')
print(*F[2:],sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

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

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

for i in range(m):
  a,b = map(int, input().split())
  connected[a].add(b)
  connected[b].add(a)
  
def bfs(x):
  queue = deque([x])
  d = [None] * (n+1)
  d[x] = 0
  while queue:
    v = queue.popleft()
    for i in connected[v]:
      if d[i] is None:
        d[i] = v
        queue.append(i)
  return d

print('Yes')
ans = bfs(1)[2:]

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque

print("Yes")

N, M = map(int, input().split())
net = [[] for _ in range(N+1)]
vect = [0]*(N+1)

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

q = deque()
q.append(1)

while len(q)>0:
	t = q.popleft()
	for i in net[t]:
		if t != i and vect[i] == 0:
			vect[i] = t
			q.append(i)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 21:29:58 2020

@author: liang
"""

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

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

visited = [False for i in range(N)]
sign = [-1]*N

from collections import deque

visited[0] = True
q = deque()
q.append(0)
sign[0] = 0

while q:
    cur = q.popleft()
    for a in adj[cur]:
        if not visited[a]:
            visited[a] = True
            sign[a] = cur + 1
            q.append(a)

if all(x >= 0 for x in sign):
    print("Yes")
    [print(a) for a in sign[1:] ]
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

que = deque()
que.append(0)

visited = [0 for _ in range(n)]
visited[0] = 1
ans = [None for _ in range(n)]

print('Yes')
while len(que) > 0:
    c = que.popleft()
    for ne in graph[c]:
        if visited[ne] == 1:
            continue
        que.append(ne)
        ans[ne] = c
        # print(f'ans[{ne}] = {c}')
        visited[ne] = 1

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

Submission status: Accepted

Solution code:
import collections

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

ways = collections.defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ways[a].add(b)
    ways[b].add(a)

dist = [-1] * N
q = collections.deque()

dist[0] = True
q.append(0)

while q:
    n = q.popleft()
    for adjacent in ways[n]:
        if dist[adjacent] != -1:
            continue
        dist[adjacent] = dist[n] + 1
        q.append(adjacent)


if -1 in dist:
    print('No')
else:
    print('Yes')
    for n, d in enumerate(dist):
        if n == 0:
            continue
        for adjacent in ways[n]:
            if d - 1 == dist[adjacent]:
                print(adjacent + 1)
                break

Submission status: Accepted

Solution code:
import queue

q = queue.Queue()
bool = True


def bfs():
    q.put(0)
    while not q.empty():
        now = q.get()
        for i in nodes[now]:
            if dist[i] != -1:
                continue
            dist[i] = dist[now] + 1
            q.put(i)
            ans[i] = now
    # bool = False


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

dist = [-1] * N
ans = [-1] * N
bfs()
if bool:
    print("Yes")
    for i in range(1, N):
        print(ans[i] + 1)
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

#print(data)

while q:
    x = q.popleft()
    for y in data[x[1]]:
        if y == x[0]:
            continue
        if ans[y] == -1:
            ans[y] = x[1]
            q.append((x[1],y))
    #print(x,q,ans)

if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in range(1,N):
        print(ans[i]+1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

go_to = [None] * N

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

while q:
    node, prev = q.popleft()
    if node in is_visited:
        continue
    is_visited.add(node)
    go_to[node] = prev + 1
    for dest in edges[node]:
        q.append((dest, node))

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

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
routes = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  routes[a].append(b)
  routes[b].append(a)
checked = [0 for _ in range(N+1)]
route = deque(routes[1])
for r in routes[1]:
  checked[r] = 1
while(len(route) > 0):
  r = route.popleft()
  for rr in routes[r]:
    if checked[rr] == 0:
      checked[rr] = r
      route.append(rr)
for i in range(2, N+1):
  if checked[i] == 0:
    print('No')
    exit()
print('Yes')
for j in range(2, N+1):
  print(checked[j])

Submission status: Accepted

Solution code:
from collections import deque


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

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

def main():
    dist = [-1] * N
    dist[0] = 0
    que = deque([0])
    ans = [0] * (N - 1)
    
    while que:
        v = que.popleft()
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                ans[nv - 1] = v + 1
                que.append(nv)
                
    print('Yes')
    print(*ans, sep='\n')
    
    
if __name__ == '__main__':
    main()