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.

Solution (Python):
import sys
input = sys.stdin.readline

print("Yes");
n, m = [int(x) for x in input().split()] 
g = [[] for _ in range(n)] 

for _ in range(m):
    aa, bb = [int(x) for x in input().split()]
    a = aa-1;
    b = bb-1;
    g[a].append(b)
    g[b].append(a)

from collections import deque

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


baka = 1;

while baka <= n-1:
    aho = len(g[baka]); 
    manuke = 0;
    while manuke <= aho-1:
        xx = d[g[baka][manuke]];
        if xx == d[baka] - 1:
            print(g[baka][manuke]+1);
            break;
        manuke = manuke + 1;
    
    baka = baka + 1;

Solution (Python):
from collections import deque

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

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

ans = [-1]*(n+1)
que = deque([1])

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

print("Yes")

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

Solution (Python):
n, m = map(int, input().split())
ways = [list(map(int, input().split())) for _ in range(m)]
graph = [[] for _ in range(n)]
for way in ways:
    graph[way[0]-1].append(way[1]-1)
    graph[way[1]-1].append(way[0]-1)
dist = [-1 for _ in range(n)]
dist[0] = 0
que = []
que.append(0)
while (len(que) > 0):
    v = que.pop(0)
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        que.append(i)
print('Yes')
for i in range(1, n):
    for j in graph[i]:
        if dist[j] == dist[i] - 1:
            print(j+1)
            break

Solution (Python):
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())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


res = [-1] * (N)
que = deque()
que.append(0)

while que:
    i = que.popleft()
    for j in graph[i]:
        if res[j] == -1:
            res[j] = i
            que.append(j)

print("Yes")
for i in res[1:]:
    print(i+1)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
edge = [[]for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

ans = [0]*(n+1)


def bfs(x):
    q = deque([])
    q.append(x)
    ans[1]=1
    while len(q)>0:
        pos = q.popleft()
        
        for i in edge[pos]:
            if ans[i] == 0:
                q.append(i)
                ans[i] = pos
    return ans

ans = bfs(1)

ans.pop(0)
if 0 in ans:
  print("No")
else:
  print("Yes")
  for i in range(1,len(ans)):
    print(ans[i])

Solution (Python):
from collections import deque

tmp = input().split()
N = int(tmp[0])
M = int(tmp[1])
ve = [deque() for _ in range(N)]
todo = deque()

s = 0
for m in range(M):
    S, T  = map(int,input().split())
    ve[S-1].append(T)
    ve[T-1].append(S)

visited = [False]*N
dist = [0]*N
todo.append(1)
   
while len(todo)>0:
    now = todo.popleft()   
    while len(ve[now-1])>0:
        sr = ve[now-1].pop()
        if  visited[sr-1]: continue
        dist[sr-1] = now
        visited[sr-1] = True
        todo.append(sr)

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

Solution (Python):
N, M = map(int, input().split())
A, B = [0]*M, [0]*M

to = {i: [] for i in range(N)}

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

q = []
dist = [-1]*N
dist[0] = 0
pre = [-1]*N
q.append(0)
while len(q)>0:
    v = q.pop(0)
    for u in to[v]:
        if dist[u]==-1:
            dist[u] = dist[v]+1
            pre[u] = v
            q.append(u)
print("Yes")
print(*map(lambda x:x+1, pre[1:]), sep="\n")

Solution (Python):
from collections import deque

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

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

while len(que) != 0:
    q = que.popleft()
    for i in S[q]:
        if ans[i] == -1: 
            que.append(i)
            ans[i] = q

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

Solution (Python):
from collections import deque

n,m = map(int, input().split())
c = [[] for i in range(n)]
d = [-1 for i in range(n)]
d[0] = 0

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


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

while que:
    
    p = que.popleft()
    
    for i in c[p]:
        
        if d[i] != -1:
            continue
            
        que.append(i)
        d[i] = p

print("Yes")
for i in d[1:]:
    print(i+1)

Solution (Python):
import queue
N,M=map(int,input().split())
adj=[[] for i in range(N+1)]
parent=[-1] * (N+1)
for m in range(M):
    a,b=map(int,input().split())
    adj[a].append(b)
    adj[b].append(a)
q=queue.Queue()
q.put((1,0))
while(not q.empty()):
    x,p=q.get()
    if parent[x]!=-1:
        continue
    parent[x]=p
    for next in adj[x]:
        if parent[next]==-1:
            q.put((next,x))
print('Yes')
for p in parent[2:]:
    print(p)

Solution (Python):
import queue

n, m = map(int, input().split())
table = [[] for i in range(n+1)]
ans = [(1e9, 0) for i in range(n+1)]
seen = [False for _ in range(n+1)]
seen[1] = True

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

q = queue.Queue()

q.put((1, table[1]))
while(not q.empty()):
    element = q.get()
    for i in element[1]:
        if seen[i]:
            continue
        ans[i] = element[0]
        seen[i] = True
        q.put((i, table[i]))


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

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]


n,m = imap()
g = [[] for i in range(n+1)]
for i in range(m):
    a,b = imap()
    g[a].append(b)
    g[b].append(a)

q = col.deque([1])
know = barr(n+1); know[1] = True
anss = iarr(n+1)
while q:
    now = q.popleft()
    for next in g[now]:
        if know[next]: continue
        else: know[next] = True; q.append(next); anss[next] = now

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

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]


n,m = imap()
g = [[] for i in range(n+1)]
for i in range(m):
    a,b = imap()
    g[a].append(b)
    g[b].append(a)

q = col.deque([1])
know = barr(n+1); know[1] = True
anss = iarr(n+1)
while q:
    now = q.popleft()
    for next in g[now]:
        if know[next]: continue
        else: know[next] = True; q.append(next); anss[next] = now

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

Solution (Python):
from collections import deque
import copy
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)


Visited = [False for i in range(n)]
depth = [0 for i in range(n)]
q = deque()
q.append(0)
while q:
    st = q.popleft()
    for i in Map[st]:
        if Visited[i]==True:
            continue
        depth[i] = depth[st]+1
        Visited[i] = True
        q.append(i)
ans = []
depth[0] = 0
for i in range(1,n):
    for j in Map[i]:
        if depth[i]-1==depth[j]:
            ans.append(j+1)
            break

if len(ans)==0:
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()


n,m = imap()
ab = np.array([iarr() for i in range(m)])
a,b = ab.T[0]-1, ab.T[1]-1


g = [[] for i in range(n)]
for aa,bb in zip(a,b):
    g[aa].append(bb)
    g[bb].append(aa)


anss = [0]*n
know = [0]*n; know[0] = 1
q = col.deque([0])
while q:
    now = q.popleft()
    for next in g[now]:
        if know[next]: continue
        else: know[next] = 1; anss[next] = now; q.append(next)

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

Solution (Python):
import collections

N, M = map(int, input().split(' '))
edges = {i: [] for i in range(N)}
depth = [-1 for i in range(N)]
ans = []

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

depth[0] = 0
que = collections.deque()
que.append((0, -1))
while que:
    now, par = que.popleft()
    for edge in edges[now]:
        if edge == par or depth[edge] != -1:
            continue
        depth[edge] = depth[now] + 1
        que.append((edge, now))

for i in range(1, N):
    for edge in edges[i]:
        if depth[edge] < depth[i]:
            ans.append(edge + 1)
            break

print('Yes')
print('\n'.join([str(a) for a in ans]))

Solution (Python):
from collections import deque
N, M = map(int, input().split())
graph = [[] * N 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)


reach = [False] * N
prev_v = [-1] * N
que = deque()

reach[0] = True
que.append(0)
while que:
    v = que[0]
    que.popleft()
    for new_v in graph[v]:
        if reach[new_v]:
            continue
        que.append(new_v)
        reach[new_v] = True
        prev_v[new_v] = v

for i in range(N):
    if not reach[i]:
        print("No")
        exit()
print("Yes")
for i in range(1, N, 1):
    print(prev_v[i]+1)

Solution (Python):
if __name__ == '__main__':
    n, m = map(int, input().split())
    paths = [[] for i in range(n)]
    dist = [-1] * n

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

    next = []
    
    for i in paths[0]:
        next.append((0, i))

    for prev, to in next:
        if dist[to] == -1:
            dist[to] = prev
            for i in paths[to]:
                next.append((to, i))

    if dist.count(-1) != 0:
        print("No")
    else:
        print("Yes")
        for i in range(1, n):
            print(dist[i] + 1)

Solution (Python):
from collections import deque

N,M = map(int,input().split())
G = [[] for _ in range(N+1)]
dist = [-1] * (N+1)
pre = [1] * (N+1)
dist[0:2] = [0,0]
q = deque()

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

q.append(1)
while q:
    v = q.popleft()
    for i in G[v]:
        if dist[i] != -1:
            continue
        dist[i] = pre[v] + 1
        pre[i] = v
        q.append(i)
print("Yes")
for i in range(2,N+1):
    print(pre[i])

Solution (Python):

from collections import deque

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


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


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

que = deque()
que.append(0)

while que:
    p = que.popleft()
    for v in G[p]:
        if d[v] < 0:
            d[v] = p+1
            que.append(v)


if min(d[1:]) < 0:
    print('No')
else:
    print('Yes')
    for g in d[1:]:
        print(g)

Solution (Python):
import math

def solve():
    ans = [-1 for i in range(n+1)]
    remaining = set(range(1, n+1))
    remaining.remove(1)
    last_visited = [1]
    last_visited2 = []
    while remaining:
        c = len(remaining)
        for r in last_visited:
            for ad in adj[r]:
                if ad in remaining:
                    last_visited2.append(ad)
                    remaining.remove(ad)
                    ans[ad] = r
        last_visited = last_visited2
        last_visited2 = []
        if len(remaining) == c:
            print("No")
            return
    print("Yes")
    for i in ans[2:]:
        print(i)
    return

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

Solution (Python):
import sys
input = sys.stdin.readline

from collections import deque


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

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

ANS = [0] * (n + 1)
SEARCHED = [False] * (n + 1)

SEARCHED[1] = True
QUEUE = deque([1])
while QUEUE:
    v = QUEUE.popleft()
    for w in GRAPH[v]:
        if SEARCHED[w]:
            continue
        ANS[w] = v
        SEARCHED[w] = True
        QUEUE.append(w)

print("Yes")
for ans in ANS[2:]:
    print(ans)

Solution (Python):
import math
import re
import copy

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

q = [0]
pre = [None] * n
while len(q) != 0:
    for x in to[q[0]]:
        if pre[x] != None:
            continue
        pre[x] = q[0]
        q.append(x)
    q.pop(0)

if all(pre[i] != None for i in range(n)):
    print("Yes")
    for i in range(1,n):
        print(pre[i]+1)
else:
    print('No')

Solution (Python):
n,m=map(int,input().split())
w={}
for i in range(m):
    a,b=map(int,input().split())
    if a in w: w[a].add(b)
    else: w[a]=set([b])
    if b in w: w[b].add(a)
    else: w[b]=set([a])

d=[-1]*(n+1)
p=[set([]),set([1])]
d[1]=0
f=1
while 1:
    x=f%2
    y=(x+1)%2
    for i in p[x]:
        for j in w[i]:
            if d[j]==-1 or f<d[j]:
                d[j]=f
                p[y].add(j)
    p[x]=set([])
    if len(p[y])==0: break
    f+=1
print("Yes")
for i in range(2,n+1):
    for j in w[i]:
        if d[j]+1==d[i]:
            print(j)
            break

Solution (Python):
from typing import List
N, M = map(int, input().split())
graph:List[List[int]] = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(lambda x : int(x) -1 , input().split())
    graph[a].append(b)
    graph[b].append(a)
prev = [-1]*N
prev[0] = 0
import queue
qu = queue.Queue()
qu.put(0)
while not qu.empty():
    top = qu.get()
    for nxt in graph[top]:
        if prev[nxt] == -1:
            prev[nxt] = top
            qu.put(nxt)
if all(x != -1 for x in prev[1:]):
    print("Yes")
    print("\n".join(map(lambda x : str(x+1), prev[1:])))
else :
    print("No")

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

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

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

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

const_vary=list()


while 1:
  const_vary=const
  const=[]
  
  while len(const_vary):
    get=const_vary.pop()
    
    for n in list_tonari[get]:
      if ans[n] ==0:
        ans[n]=get
        list_tonari[n].remove(get)
        const.append(n)
        
  if len(const)==0:
    break
    
print("Yes")
for n in ans[2:]:
  print(n)

Solution (Python):
N,M = map(int,input().split())
 
from heapq import heappush, heappop
INF = float("inf")
miti = [-1]*N
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                miti[t] = v+1
                heappush(que, (dist[t], t))
    return dist
 
edge = [[] for _ in range(N)]
 
for _ in range(M):
    a,b = map(int,input().split())
    edge[a-1].append((b-1,1))
    edge[b-1].append((a-1,1))
 
dist = dijkstra(N,edge,0)
 
if -1 in miti[1:]:
    print("No")
else:
    print("Yes")
    for t in miti[1:]:
        print(t)

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

G = [[] for _ in range(N+1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

parents = [0] * (N+1)
visited = [0] * (N+1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        parents[w] = v
        q.append(w)

print('Yes')
print(*parents[2:], sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline

n, m = [int(x) for x in 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)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0
    pre = [-1] * n
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                pre[i] = v + 1 
                
    return pre

d = bfs(0)
if all([i != None for i in d]):
    print("Yes")
    for i in range(1,n):
        print(d[i])
else:
    print("No")

Solution (Python):
import numpy as np
n,m = map(int,input().split())

p = [0 for i in range(n+1)]
q = list()
q2 = list()

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

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


q2.append(1)

while 1:
    q=q2
    q2=[]

    while len(q):
        v = q.pop()
        
        for nv in g[v]:
            if p[nv] == 0:
                p[nv]=v
                g[nv].remove(v)
                q2.append(nv)
    if len(q2)==0:
        break

if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)

Solution (Python):
from collections import deque
 
N,M = map(int, input().split())
nl = {i:[] for i in range(1,N+1)}
rlt = [-1]*(N+1)
 
for _ in range(M):
  a,b = map(int, input().split())
  nl[a].append(b)
  nl[b].append(a)

ds = [float('inf')]*(N+1)
ds[1] = 0
h = deque()
h.append(1)
 
while(len(h) > 0):
  v = h.popleft()
  for j in nl[v]:
    if ds[j] == float('inf'):
      ds[j] = ds[v] + 1
      rlt[j] = v
      h.append(j)

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

Solution (Python):
from collections import deque

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

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

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

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

d = deque()
d.append(1)

ans = [0] * (N+1)
while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v]+1
        d.append(i)
        ans[i] = v

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

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

room = [-1]*n
seen = [-1]*n
import queue
q = queue.Queue()
q.put(0)
while not q.empty():
    x = q.get()
    
    seen[x] =  -2
    for i in g[x]:
        if room[i] == -1:
            room[i] = x
            
        if seen[i] == -1:
            q.put(i)
            seen[i] = -2
        
print('Yes')
for i in range(1,n):
    print(room[i]+1)

Solution (Python):
from collections import deque

def main():
    N, M, *AB = map(int, open(0).read().split())
    C = {}
    for i in range(M):
        a = AB[2 * i + 0] - 1
        b = AB[2 * i + 1] - 1
        if a not in C:
            C[a] = []
        C[a].append(b)
        if b not in C:
            C[b] = []
        C[b].append(a)
    ANS = {i:-1 for i in range(N)}
    D = deque()
    D.append((0, C[0]))
    
    while len(D) != 0:
        d = D.popleft()
        v = d[0]
        L = d[1]
        for l in L:
            if ANS[l] == -1:
                ANS[l] = v
                D.append((l, C[l]))
    print('Yes')
    for i in range(1, N):
        print(ANS[i] + 1)


if __name__ == '__main__':
    main()

Solution (Python):
import networkx as nx

N,M = map(int,input().split())
G = nx.Graph()
for i in range(M):
    A,B = map(int,input().split())
    G.add_edge(A,B)
print("Yes")
pre = nx.predecessor(G,1)
for i in range(2,N+1):
    print(pre[i][0])

Solution (Python):
from networkx import Graph,predecessor

G = Graph() 
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
G.add_edges_from(ab) 
preds = predecessor(G,source=1)  
print("Yes")
for i in range(2,n+1):
    print(preds[i][0])

Solution (Python):
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)

T = [-1]*N
que = deque()
que.append(0)
while que:
    v = que.popleft()
    for e in G[v]:
        if T[e] == -1:
            T[e] = v+1
            que.append(e)
print("Yes")
print(*T[1:], sep="\n")

Solution (Python):
import queue
def readInt():
    return list(map(int, input().split()))

N, M = readInt()

graph = [[] for i in range(N)] 
v = [-1 for i in range(N)] 
v[0] = [0]

for i in range(M):
    x, y = readInt()
    graph[x-1].append(y-1) 
    graph[y-1].append(x-1)


q = queue.Queue()
q.put(0)

while not q.empty():
    n = q.get()
   
    for j in graph[n]:
        if v[j]!=(-1):
            continue
        q.put(j)
        v[j] = n
        
print("Yes")
for i in range(1, N):
    print(v[i] + 1)

Solution (Python):
from collections import deque

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

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

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

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

d = deque()
d.append(1)

ans = [0] * (n+1)
while d:
 v = d.popleft()
 for i in graph[v]:
   if dist[i] != -1:
     continue
   dist[i] = dist[v] + 1
   d.append(i)
   ans[i] = v
print('Yes')
print(*ans[2:], sep='\n')

Solution (Python):
def main():
    input1 = input()
    input1 = input1.split()
    N = int(input1[0])
    M = int(input1[1])

    aisle = {}
    result = [0]*(N-1)
    record = [1]
    count = N-1
    in1 = 0
    in2 = 0

    for i in range(M):
        input2 = input()
        input2 = input2.split()
        in1 = int(input2[0])
        in2 = int(input2[1])
        aisle.setdefault(in1,[]).append(in2)
        aisle.setdefault(in2,[]).append(in1)

    while count != 0 and len(record) != 0:
        pop1 = record.pop(0)
        if pop1 in aisle:
            for i in aisle[pop1]:
                if result[i-2] == 0 and i >= 2:
                    result[i-2] = pop1
                    record.append(i)
                    count = count -1

    if count == 0:
        print("Yes")
        for i in range(len(result)):
            print(result[i])
    else:
        print("No")


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

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

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

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


d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if prev[i] == -1:
            prev[i] = v
            d.append(i)

prev.pop(0)
prev.pop(0)
if len(prev) > 0:
    print("Yes")
    for y in prev:
        print(y)
else:
    print("No")

Solution (Python):

def main():
    n, m = map(int, input().split())
    ab = (map(int, input().split()) for _ in range(m))

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

    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    from collections import deque

    q = deque()
    q.append(1)

    p = [0] * (n+1)

    while q:
        a = q.popleft()
        for b in graph[a]:
            if not p[b]:
                p[b] = a
                q.append(b)

    result = p[2:]

    is_yes = all(result)

    print('Yes' if is_yes else 'No')

    if is_yes:
        for r in result:
            print(r)


if __name__ == "__main__":
    main()

Solution (Python):
import collections
import itertools
N, M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

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

for AB in ABs:
    loads[AB[0]].append(AB[1])
    loads[AB[1]].append(AB[0])


dq = collections.deque()

dq.append(1)
ans_list = [0 for _ in range(N+1)]


print("Yes")
while len(dq) != 0:
    i = dq.popleft()

    for vec in loads[i]:

        if(ans_list[vec] == 0):
            ans_list[vec] = i
            dq.append(vec)




for ans in ans_list[2:]:
    print(ans)

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

import heapq
def dijkstra_heap(s):
  
  dist=[float("inf")]*size_v
  used=[False]*size_v
  prev=[-1]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    prev[min_v]=u
    for v,w in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

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


size_v=N+1
dist,prev=dijkstra_heap(1)



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

Solution (Python):
from networkx import Graph,predecessor
G = Graph()

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

G.add_edges_from(rows)

preds = predecessor(G,source=1)

if len(preds) != N:
    print("No")
    exit()

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

Solution (Python):
from collections import deque
N,M = list(map(int,input().split()))
map1 = [[] for i in range(N+1)]

sirusi = [0]*(N+1)

for i in range(M):
    a,b = list(map(int,input().split()))
    
    map1[a].append(b)
    map1[b].append(a)
    
d = deque([1]+map1[1])
visited = [0]*(N+1)
visited[1] = 1

while d:
    D = d.popleft()
    for i in map1[D]:
        if visited[i] == 1:
            continue
        visited[i] = 1
        d.append(i)
        sirusi[i] = D
        
print("Yes")
for i in range(2,N+1):
    print(sirusi[i])

Solution (Python):
from collections import deque 

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

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

q = deque([1])
ans = [0]*(n+1)
while q:
    p = q.popleft()
    for i in to[p]:
        if ans[i]==0:
            ans[i]=p
            q.append(i)
print('Yes')
print(*ans[2:], sep='\n')

Solution (Python):
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) 

visited = [False]*N
visited[0] = True
ans = [0]*N
D = deque([0])
while D:
    v = D.popleft()
    for i in graph[v]:
        if visited[i]:
            continue
        visited[i] = True 
        ans[i] = v+1
        D.append(i)

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

Solution (Python):




import sys
input = sys.stdin.readline

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

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

from collections import deque

def BFS(u): 
    queue = deque([u]) 
    dis = [None] * n 
    dis[u] = 0 
    ans = [-1] * n 
    while queue:
        v = queue.popleft() 
        for i in pic[v]: 
            if ans[i] == -1:
                ans[i] = v
            if dis[i] is None:
                dis[i] = dis[v] + 1
                queue.append(i)
    return ans

tmp = BFS(0) 
print('Yes')
for j in tmp[1:]:
    print(j+1)