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

q = deque([])
path = [-1] * n
ver = [[] for _ in range(n)]
for i in range(m):
    ab[i].sort()
    if ab[i][0] == 1:
        q.append([ab[i][0]-1,ab[i][1]-1])
        #path[ab[i][1]-1] = 1
    ver[ab[i][0]-1].append(ab[i][1]-1)
    ver[ab[i][1]-1].append(ab[i][0]-1)

def bfs(q, visited_list):
    while len(q) > 0:
        now = q.popleft()
        go = now[1]
        if visited_list[go] == -1:
            visited_list[go] = now[0]+1
            for i in range(len(ver[go])):
                q.append([go,ver[go][i]])
    return visited_list
ans = bfs(q,path)
print('Yes')
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = inpl()
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)
res = [-1] * n
res[0] = 0
q = deque()
q.append(0)
while q:
    now = q.popleft()
    for v in g[now]:
        if res[v] != -1:
            continue
        res[v] = now + 1
        q.append(v)
print('Yes')
for i in res[1:]:
    print(i)

Submission status: Accepted

Solution code:

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import breadth_first_order

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

    row = AB.T[0]-1
    col = AB.T[1]-1
    data = [1]*M
    csr = csr_matrix((data, (row, col)), shape=(N, N))
    _, proc = breadth_first_order(csr, 0, directed=False)

    impos = any(proc[1:] >= 0)
    if impos:
        print("Yes")
        print(*proc[1:]+1, sep="\n")
    else:
        print("No")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import queue
N, M = map(int, input().split())
G = [[] for _ in range(N)]
dist = [-1] * N
pre = [-1] * N

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

q = queue.Queue()
dist[0] = 0
q.put(0)

while not q.empty(): 
    v = q.get()
    for u in range(len(G[v])):
        if dist[G[v][u]] != -1:
            continue
        dist[G[v][u]] = dist[v] + 1
        pre[G[v][u]] = v
        q.put(G[v][u])
    
print('Yes')

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

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split());n,m=f();g=[[] for _ in range(n)]
for _ in [0]*m:a,b=f();g[a-1]+=[b-1];g[b-1]+=[a-1]
p=[0]*n;from collections import*;q=deque([0])
while q:
    for c in g[(v:=q.popleft())]:
        if p[c]<1:p[c]=v+1;q.append(c)
print('Yes',*p[1:],sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

for _ in range(M):
    A, B = map(int, input().split())
    G[A - 1].append(B - 1)
    G[B - 1].append(A - 1)
    if A == 1 or B == 1:
        goal = True

if goal:
    print("Yes")
else:
    print("No")
    sys.exit()

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

while d:
     q = d.popleft()
     for g in G[q]:
         if ans[g] == -1:
             ans[g] = q + 1
             d.append(g)

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

def main():
    INF = 10**9
    n, m = list(map(int,sys.stdin.readline().split()))
    rank = [False] * (n + 1)
    next_room = [None] * n
    next_room[0] = 0
    group = [[] for _ in range(n)]
    
    for _ in range(m):
        a, b = list(map(int,sys.stdin.readline().split()))
        a -= 1
        b -= 1
        group[a].append(b)
        group[b].append(a)
    #print(group)

    #幅優先探索
    queue = deque([0])
    while(queue != deque([])):
        now = queue.popleft()
        now_group = group[now]
        for mem in now_group:
            if rank[mem] or mem == 0:
                continue
            rank[mem] = True
            next_room[mem] = now
            queue.append(mem)

    if None in next_room:
        print("No")
        return 0
    print("Yes")
    for i in range(1,n):
        print(next_room[i] + 1)
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from dataclasses import dataclass
from collections import deque


@dataclass
class Query:
    now: int
    prev: int
    cost: int


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

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

res = [-1 for _ in range(N + 1)]
cost = [float('inf') for _ in range(N + 1)]
cost[1] = 0

queue = deque()

for next in E[1]:
    queue.append(Query(next, 1, 1))

while len(queue):
    q = queue.popleft()
    if cost[q.now] > q.cost:
        res[q.now] = q.prev
        cost[q.now] = q.cost

        for next in E[q.now]:
            if cost[next] > q.cost + 1:
                queue.append(Query(next, q.now, q.cost + 1))

for r in res[2:]:
    if r == -1:
        print('No')
        exit()

print('Yes')
for r in res[2:]:
    print(r)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda n: int(n) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
visited = bfs(graph, N, 0)[1:]
if all(visited):
    print("Yes")
    print(*visited, sep="\n")
else:
    print("No")

Submission status: Accepted

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

    l = {i: [] for i in range(n + 1)}
    for _ in range(m):
        i, j = map(int, input().split())
        l[i].append(j)
        l[j].append(i)

    ll = [None] * (n + 1)
    vis = [False] * (n + 1)
    que = deque([1])
    vis[1] = True
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if vis[i]:
                continue
            vis[i] = True
            ll[i] = now
            que.append(i)
    if all(vis[1:]):
        print("Yes")
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())

    l = {i: [] for i in range(n + 1)}
    for i, j in zip(*[iter(ab)] * 2):
        l[i].append(j)
        l[j].append(i)

    ll = [None] * (n + 1)
    vis = [False] * (n + 1)
    que = deque([1])
    vis[1] = True
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if vis[i]:
                continue
            vis[i] = True
            ll[i] = now
            que.append(i)
    if all(vis[1:]):
        print("Yes")
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split());n,m=f();g=[[] for _ in range(n)]
for _ in [0]*m:a,b=f();g[a-1]+=[b-1];g[b-1]+=[a-1]
p=[0]*n;from queue import*;q=Queue();q.put(0)
while not q.empty():
    v=q.get()
    for c in g[v]:
        if p[c]<1:p[c]=v+1;q.put(c)
print('Yes',*p[1:],sep='\n')

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())

    l = {i: [] for i in range(n + 1)}
    for i, j in zip(*[iter(ab)] * 2):
        l[i] += [j]
        l[j] += [i]

    ll = [None] * (n + 1)
    vis = [False] * (n + 1)
    que = deque([1])
    vis[1] = True
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if vis[i]:
                continue
            vis[i] = True
            ll[i] = now
            que.append(i)
    if all(vis[1:]):
        print("Yes")
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split());n,m=f();g=[[] for _ in range(n)]
for _ in [0]*m:a,b=f();g[a-1]+=[b-1];g[b-1]+=[a-1]
p=[0]*n;from collections import*;q=deque([0])
while q:
    v=q.popleft()
    for c in g[v]:
        if p[c]<1:p[c]=v+1;q.append(c)
print('Yes',*p[1:],sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
def bfs(G,s,N):
    dist=[-1]*N
    d=deque()
    dist[s]=0
    d.append(s)
    while(len(d)!=0):
        v=d[0]
        d.popleft()
        for nv in G[v]:
            if(dist[nv]!=-1):
                continue
            dist[nv]=dist[v]+1
            par[nv]=v
            d.append(nv)
    return dist
    
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
par=[-1]*N
dist=bfs(G,0,N)
print('Yes')
for i in range(1,N):
    print(par[i]+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
nan=deque([0])
check=[1 if i==0 else -1 for i in range(n)]
def bfs():
    global n,m,path,nan
    l=len(nan)
    if not l:
        return
    for _ in range(l):
        x=nan.popleft()
        for j in path[x]:
            if check[j]==-1:
                check[j]=x
                nan.append(j)
    bfs()
bfs()
if any([i==-1 for i in check]):
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(check[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

ans_li = [-1]*n
queue=deque()
queue.append(0)

while queue:
    now = queue.popleft()
    for c in map_li[now]:
        if ans_li[c]==-1:
            ans_li[c]=now
            queue.append(c)

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
route =[[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    route[a].append(b)
    route[b].append(a)
visited = [0 for i in range(n+1)]
visited[1] = 1
ans = [0 for i in range(n+1)]
D = deque()
D.append(1)
while D:
    visit = D.popleft()
    for i in route[visit]:
        if visited[i] == 0:
            D.append(i)
            visited[i] = 1
            ans[i] = visit
print('Yes')
for i in range(2, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import queue

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

numRoom,numPath = intMap() # numRoom = n, numPath = m
#room = [[]] * numRoom # <- これが間違いでした。
#                           これだと全てのroom[ほにゃらら]が同じオブジェクトを指す（らしい）
room = [[] for i in range(numRoom)]

for _ in range(numPath):
    a,b = intMap()
    a -= 1
    b -= 1
    room[a].append(b)
    room[b].append(a)

prevRoom = [-1] * numRoom
distance = [-1] * numRoom
q = queue.Queue()

distance[0] = 0
q.put(0)
while not q.empty():
    checkRoom = q.get()
    for connectedTo in room[checkRoom]:
        if distance[connectedTo] != -1:
            continue
        distance[connectedTo] = distance[checkRoom] + 1
        prevRoom[connectedTo] = checkRoom
        q.put(connectedTo)

print('Yes')
for i in range(1,numRoom):
    print(prevRoom[i]+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)
N, M = map(int, input().split())
connect_list = [set() for _ in range(N)]    #繋がっているリスト
for _ in range(M):
    A, B = map(int, input().split())
    connect_list[A-1].add(B)
    connect_list[B-1].add(A)

root_list = [0]*N
root_list[0] = "Yes"

for i in list(connect_list[0]):
    root_list[i-1] = 1
now_set = connect_list[0]

def do_ranking(now_set):
    global connect_list, root_list
    if len(now_set) == 0:
        return 0
    for j in list(now_set):
        for m in list(connect_list[j-1]):
            if root_list[m-1] == 0:
                root_list[m-1] = j
                now_set.add(m)
        now_set.remove(j)
    do_ranking(now_set)


do_ranking(now_set)   #道しるべ作成

for k in root_list:
    print(k)

Submission status: Accepted

Solution code:
import queue
n, m = map(int, input().split())
graph = [[] for i in range(n)]
depth = [-1] * n
route = []
result = [0] * (n - 1)
for i in range(m):
    temp = list(map(int, input().split()))
    graph[temp[0] - 1].append(temp[1] - 1)
    graph[temp[1] - 1].append(temp[0] - 1)
    route.append(temp)
q = queue.Queue()
q.put(0)
depth[0] = 0
for i in range(n-1):
    item = q.get()
    for j in graph[item]:
        if(depth[j] == -1):
            q.put(j)
            depth[j] = depth[item] + 1
print("Yes")
for i in route:
    if(i[0] == 1):
        result[i[1] - 2] = 1
    elif(i[1] == 1):
        result[i[0] - 2] = 1
    elif(depth[i[0] - 1] - depth[i[1] - 1] == 1):
        result[i[0] - 2] = i[1]
    elif(depth[i[1] - 1] - depth[i[0] - 1] == 1):
        result[i[1] - 2] = i[0]
for i in result:
    print(i)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
 
N,M=map(int,input().split())
E=[[] for i in range(N+1)]
 
for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

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

Q=deque()
Q.append(1)

while Q:
    x=Q.pop()
    for to in E[x]:
        if USE[to]==-1:
            USE[to]=x
            Q.appendleft(to)
 
if -1 in USE:
    print("No")
else:
    print("Yes")
    for i in USE[2:]: print(i)

Submission status: Accepted

Solution code:
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)
P = [-1] * (N + 1)
P[1] = 0
Q = deque()
Q.append(1)

while Q:
    v = Q.popleft()
    for r in R[v]:
        if P[r] == -1:
            P[r] = v
            Q.append(r)
print('Yes')
for p in P[2:]:
    print(p)

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)

queue = deque([0])
ans = [-1]*n
ans[0] = 0
while len(queue)>0:
    node = queue.popleft()
    for c_node in graph[node]:
        if ans[c_node]>=0:
            continue
        ans[c_node] = node+1
        queue.append(c_node)
print('Yes')
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = [-1] * N
queue = deque()


def bfs():
    queue.append(0)
    while queue:
        now = queue.popleft()

        for c in nei_L[now]:
            if ans[c] == -1:
                ans[c] = now
                queue.append(c)


bfs()

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:
import sys
input=sys.stdin.readline
from collections import deque

def main():
    N, M = list(map(int, input().split()))
    E = [deque() for i in range(N)]
    
    for i in range(M):
        a, b = list(map(int, input().split()))
        a -= 1; b -= 1
        E[a].append(b)
        E[b].append(a)
        
    par = [-1] * N
    q = deque([(0, 0)])
    c = 0
    while q:
        v, p = q.popleft()
        
        if par[v] != -1: continue
        par[v] = p+1
        c += 1
        
        for u in E[v]:
            if par[u] != -1: continue
            q.append((u, v))
        
    if c < N: print('No')
    else: 
        print('Yes')
        print('\n'.join(list(map(str, par[1:]))))
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

ans_li = [-1]*n
queue=deque()
queue.append(0)
visited = [False]*n

while queue:
    x = queue.popleft()
    for g in map_li[x]:
        if ans_li[g]==-1:
            ans_li[g]=x
            queue.append(g)
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Submission status: Accepted

Solution code:
from queue import Queue
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)
que = Queue()
que.put(0)
visit = [0] * N
ans = [0] * N
while not que.empty():
    v = que.get()
    for next_v in G[v]:
        if visit[next_v] == 1:
            continue
        ans[next_v] = v
        visit[next_v] = 1
        que.put(next_v)
print("Yes")
for i in list(map(lambda x: x+1, ans[1:])):
    print(i)

Submission status: Accepted

Solution code:
import queue
n,m=map(int,input().split())
graph=[[] for _ in range(n+1)]
dist=[-1 for _ in range(n+1)]
guide=[0 for _ in range(n+1)]

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

que=queue.Queue()
dist[1]=0
que.put(1)

while not que.empty():
    v=que.get()
    for nv in graph[v]:
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+1
        guide[nv]=v
        que.put(nv)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
connect_list = [set() for _ in range(N)]    #繋がっているリスト
for _ in range(M):
    A, B = map(int, input().split())
    connect_list[A-1].add(B)
    connect_list[B-1].add(A)

root_list = [0]*N
root_list[0] = "Yes"

for i in list(connect_list[0]):
    root_list[i-1] = 1
now_set = connect_list[0]
while len(now_set) != 0:
    for j in list(now_set):
        for i in list(connect_list[j-1]):
            if root_list[i-1] == 0:
                root_list[i-1] = j
                now_set.add(i)
        now_set.remove(j)

for i in root_list:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(graph, n, s):
  visited = [0]*n
  visited[s] = 1
  q = deque([s])
  while q:
    node = q.popleft()
    for i in graph[node]:
      if not visited[i]:
        visited[i] = node + 1
        q.append(i)
  return visited

n,m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda n: int(n)-1, input().split())
  graph[a].append(b)
  graph[b].append(a)
visited = bfs(graph, n, 0)[1:]
if all(visited):
  print("Yes")
  print(*visited, sep="\n")
else:
  print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

def ri():
    return int(input())

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

def rl2():
    return list(rl())

N, M = rl()
edges = dd(list)
for i in range(M):
    A, B = rl()
    edges[A].append(B)
    edges[B].append(A)

parents = {1:0}
ring = [1]
while ring:
    nxt = []
    for room in ring:
        for nbr in edges[room]:
            if nbr not in parents:
                parents[nbr] = room
                nxt.append(nbr)
    ring = nxt

if len(parents) < N:
    print ("No")
else:
    print ("Yes")
    for i in range(2, N + 1):
        print (parents[i])

Submission status: Accepted

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

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

ans = [-1] * n

from collections import deque

q = deque([0])

while q:
    _q = q.popleft()
    for x in G[_q]:
        if ans[x] == -1:
            ans[x] = _q + 1
            q.append(x)

if -1 in ans:
    print('No')
else:
    ans[0] = 'Yes'
    for _ans in ans:
        print(_ans)

Submission status: Accepted

Solution code:
print("Yes")
N, M = map(int,input().split())
path = [[] for _ in range(N)]
ind = [0 for _ in range(N)]
lis = [0] + [1 for _ in range(N-1)]
for i in range(M):
    A, B = map(int, input().split())
    path[A-1].append(B-1)
    path[B-1].append(A-1)

for p in path[0]:
    lis[p] = 0
for l in path[0]:
    for m in path[l]:
        if lis[m] ==1:
            ind[m] = l
            lis[m] = 0
            path[0].append(m)

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

Submission status: Accepted

Solution code:
import numpy as np
import functools
import math
import collections
import scipy
import fractions
import itertools

def solve():
  n, m = map(int, input().split())
  l = [list(map(int, input().split())) for i in range(m)]
  ways = [[] for i in range(n+1)]
  for i in l:
    ways[i[0]].append(i[1])
    ways[i[1]].append(i[0])
  que = collections.deque()
  ans = [-1]*n
  que.append(1)
  ans[0] = 0
  while(len(que)!=0):
    item = que.popleft()
    for i in ways[item]:
      if ans[i-1] == -1:
        ans[i-1] = item
        que.append(i)
  if -1 in ans:
    print("No")
  else:
    print("Yes")
    for i in range(1,n):
      print(ans[i])
  return 0
 
if __name__ == "__main__":
  solve()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(nodes, src):
    from collections import deque

    N = len(nodes)
    que = deque([src])
    res = [-1] * N
    res[src] = 0
    while que:
        u = que.popleft()
        for v in nodes[u]:
            if res[v] != -1:
                continue
            res[v] = u
            que.append((v))
    return res

N, M = MAP()
nodes = [[] for i in range(N)]
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

res = bfs(nodes, 0)
Yes()
for a in res[1:]:
    print(a+1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().strip().split())
to = [[] for _ in range(n)]
 
for _ in range(m):
    a,b = map(int, input().strip().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
 
q=deque([0,])
ans=[None]*n
while q:
    cur=q.popleft()
    for nxt in to[cur]:
        if ans[nxt] is not None: # visited
            continue
        ans[nxt]=cur+1
        q.append(nxt)
 
print("Yes")
print(*ans[1:])

Submission status: Accepted

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

set_A = {1}
ans = [pow(10, 10)]*n
q = deque([1])
while True:
    if len(q) == 0:
        break
    num = q.popleft()
    l = list_MAP[num-1]
    for i in l:
        if i not in set_A:
            ans[i-1] = num
            set_A.add(i)
            q.append(i)


if ans.count(pow(10, 10)) > 1 :
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(ans[i])

Submission status: Accepted

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

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

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

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

    q = deque([0])

    ans = [-1]*n
    ans[0] = 0
    count = 1

    while q:
        l = q.popleft()
        for i in edges[l]:
            if ans[i] == -1:
                ans[i] = l
                count += 1
                q.append(i)
        if count == n:
            break

    if count == n:
        print('Yes')
        for i in ans[1:]:
            print(i+1)
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

next_queue = deque()
sign = [-1] * n
sign[0] = 999

next_queue.append(0)

while next_queue:
    current_number = next_queue.popleft()
    for room in route[current_number]:
        if sign[room] == -1:
            sign[room] = current_number
            next_queue.append(room)
print("Yes")
for i in range(1, n):
    print(sign[i] + 1)

Submission status: Accepted

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

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

next_queue = deque()
sign = [-1 for i in range(n)]
sign[0] = 999

next_queue.append(0)

while next_queue:
    current_number = next_queue.popleft()
    for room in route[current_number]:
        if sign[room] == -1:
            sign[room] = current_number
            next_queue.append(room)
print("Yes")
for i in range(1, n):
    print(sign[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(graph):
    visited = set()
    queue = deque()
    queue.append(1)
    ans = [0] * (N+1)
    while queue:
        cur = queue.popleft()
        visited.add(cur)
        for n in graph[cur]:
            if ans[n] == 0:
                ans[n] = cur
                queue.append(n)
    return ans

ans = bfs(graph)
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())

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

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

    q = deque([0])

    ans = [-1]*n
    ans[0] = 0
    count = 1

    while q:
        l = q.popleft()
        for i in edges[l]:
            if ans[i] == -1:
                ans[i] = l
                count += 1
                q.append(i)
        if count == n:
            break

    if count == n:
        print('Yes')
        for i in ans[1:]:
            print(i+1)
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
 
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
 
N, M = lr()
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)
 
def bfs():
    que = deque([1])
    dir = [None] * (N+1)    
    while que:
        cur = que.popleft()
        for n in graph[cur]:
            if dir[n] != None:
                continue
            dir[n] = str(cur)
            que.append(n)
    return dir
 
dir = bfs()
print('Yes')
print('\n'.join(dir[2:]))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
dist = [-1] * N
dist[0] = 0
G = [[] for i in range(N)]
prev = [0] * N

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

que = deque([0])

while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
        prev[w] = v
print("Yes")
for i in range(1, len(prev)):
    print(prev[i]+1)