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
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

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

root = 1
q = [root]
checked = [0] * (N + 1)
checked[root] = 1
order = []
D = [0 for _ in range(N+1)]
d = 0
while q:
    x = q.pop(0)
    d = D[x]
    for y in graph[x]:
        if checked[y]:
            continue
        D[y] = d + 1
        checked[y] = 1
        q.append(y)

ans = [0 for _ in range(N+1)]
for a, b in AB:
    d_a, d_b = D[a], D[b]
    if d_a < d_b:
        ans[b] = a
    elif d_a > d_b:
        ans[a] = b

print('Yes')
print('\n'.join(map(str, ans[2:])))

Solution (Python):
from collections import deque
N,M = map(int,input().split())

adj = [list() for _ in range(N)]

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

parent = [None]*N
queue = deque([0])
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if parent[v] is None:
            parent[v] = u
            queue.append(v)

print('Yes')
print(*(x+1 for x in parent[1:]), sep='\n')

Solution (Python):
N, M= [int(i) for i in input().split(' ')]
graph = {}
 
for i in range(1,N+1):
  graph[i] = []
 
for j in range(M):
  a, b= [int(i) for i in input().split(' ')]
  graph[a].append(b)
  graph[b].append(a)
    
 
def bfs(graph, start):
  queue = [start]
  miti = [-1 for _ in range(N)]

  while queue:
    label = queue.pop(0)
    for i in graph[label]:
      if miti[i-1] < 0:
        queue.append(i)
        miti[i-1] = label
  return miti
 
miti = bfs(graph, 1)
if miti:
  print('Yes')
  for i in range(2,N+1):
    print(miti[i-1])
else:
  print('No')

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]

def to_bin(x: int) -> str: return format(x,'b') 
def to_oct(x: int) -> str: return format(x,'o') 
def to_hex(x: int) -> str: return format(x,'x') 
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(n=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res

MOD=10**9+7

import itertools as it
import functools as ft
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

def main():
    n, m = MII()
    ab = [MIIZ() for _ in range(m)]
    g = [[] for _ in range(n)]
    for a,b in ab:
        g[a].append(b)
        g[b].append(a)
    dist = [-1]*n
    dq = deque()
    dist[0] = 0
    dq.append(0)
    res = [0]*n
    while dq:
        v = dq.popleft()
        for nv in g[v]:
            if dist[nv] != -1: continue
            res[nv] = v
            dist[nv] = dist[v] + 1
            dq.append(nv)
    res = [i+1 for i in res[1:]]
    print('Yes')
    print(*res,sep='\n')


if __name__ == '__main__':
    main()

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

ans_list=[-1]*n

queue=[0]

while queue:
    qi=queue.pop(0)
    for gi in g[qi]:
        if ans_list[gi]==-1:
            queue.append(gi)
            ans_list[gi]=qi

print("Yes")
for ans in ans_list[1:]:
    print(ans+1)

Solution (Python):
from collections import deque

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

before=[None] * n
before[0] = -1
q=deque([0])
while len(q):
  node=q.popleft()
  for nxt in adj[node]:
    if before[nxt] is not None:
      continue
    q.append(nxt)
    before[nxt] = node
print("Yes")
for i in range(1, n):
  print(before[i] + 1)

Solution (Python):
import sys
sys.setrecursionlimit(2*100000)
n, m = map(int,input().split())
mark = [-2] * (n-1)
dist = [0] * (n-1)
path = [[] for _ in range(n-1)]
path0 = []

for _ in range(m):
    a, b = map(lambda x: int(x)-2, input().split())
    if a == -1:
        path0.append(b)
        dist[b] = 1
        mark[b] = -1
    elif b == -1:
        path0.append(a)
        dist[a] = 1
        mark[a] = -1
    else:
        path[a].append(b)
        path[b].append(a)

while len(path0) > 0:
    i = path0.pop(0)
    d = dist[i]
    for p in path[i]:
        if dist[p] > d + 1 or dist[p] == 0:
            dist[p] = d + 1
            mark[p] = i
            path0.append(p)

print("Yes")
for i in mark: print(i+2)

Solution (Python):
import queue
N, E = map(int, input().split(" "))
adj = [ [] for _ in range(N) ]  
for _ in range(E) :
    u,v = map(int, input().split(" "))
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)
ans = [""]*N
q = queue.Queue() 
q.put( (0, -1 ) )

visited = [False]*N
visited[0] = True
while not q.empty() :
    u, p = q.get()
    ans[u] = p+1
    for v in adj[u] :
        if visited[v] :
            continue
        q.put( (v, u) ) 
        visited[v] = True

for a in ans :
    if a==0 :
        print("Yes")
    else :
        print(a)

Solution (Python):
import sys
import itertools
import numpy as np
from collections import Counter
import math

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
while count < N:
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
print('Yes')
for i in ans[2:]:
    print(i)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque as d

N, M = map(int, readline().split())
m = map(int, read().split())
AB = zip(m, m)
graph = [[] for _ in range(N + 1)]

for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
que = d([1])
ans = [0]*(N+1)
while que:
  x = d.popleft(que)
  for i in graph[x]:
    if ans[i] != 0:
        continue
    ans[i] = x
    que.append(i)
if 0 in ans[2:]:
    print('No')
    exit()
print('Yes')
print('\n'.join(map(str, ans[2:])))

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

INF = float('inf')

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


def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    prevs = [None] * numV
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2 in adjList[vNow]:
            c2 = cNow + 1
            if c2 < costs[v2]:
                costs[v2] = c2
                prevs[v2] = vNow
                heappush(PQ, (c2, v2))
    return (costs, prevs)

costs, prevs = Dijkstra(adjL, 0)




print('Yes')
print('\n'.join(map(lambda x: str(x+1), prevs[1:])))

Solution (Python):
import collections
n,m = list(map(int,input().split()))
ans = [0]*n
graph = [[] for _ in range(n)]
for i in range(m):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
D = collections.deque([0])
visited = [False]*n
visited[0]=True

while D:
    v = D.popleft()
    for i in graph[v]:
        if visited[i]:continue
        visited[i]=True
        ans[i]=v
        D.append(i)
print("Yes")
for i in ans[1:]:
    print(i+1)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    
dist = [-1] * N
dist[0] = 0
    
queue = deque([0])

while queue:
    v = queue.popleft()
    for nv in graph[v]:
        if (dist[nv] != -1):
            continue
        dist[nv] = v
        queue.append(nv)
        
print("Yes")
for i in dist[1:]:
    print(i+1)

Solution (Python):
import queue

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

q = queue.Queue()
q.put(1)
shirube = [0] * (n+1)
shirube[1] = 1

while not q.empty():
    v = q.get()
    for i in cave[v]:
        if shirube[i] == 0:
            shirube[i] = v
            q.put(i)

cnt = 0
for i in range(2, n+1):
    if shirube[i] == 0:
        cnt += 1
if cnt > 0:
    print("No")
else:
    print("Yes")
    for i in range(2, n+1):
        print(shirube[i])

Solution (Python):


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

ans = [0]*(N+1)
now = [1]

next = []
 
while len(now):
    
    for x in now:
        for y in L[x]:
            if (ans[y] == 0):
                ans[y] = x
                next.append(y)
    now = next.copy()
    
    next = []
 
print("Yes")
for x in range(2, N+1):
    print(ans[x])

Solution (Python):
import sys
import itertools
import numpy as np
from collections import Counter
import math

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne




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

Solution (Python):
def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque
def main():
  n,m=LI()
  edge=[[]for i in range(n)]
  for i in range(m):
    a,b=LI()
    edge[a-1]+=b-1,
    edge[b-1]+=a-1,    
  dq=deque([0])
  ans=[-1]*n
  while dq:
    g=dq.popleft()
    for i in edge[g]:
      if ans[i]==-1:
        ans[i]=g+1
        dq.append(i)
  yes()
  print(*ans[1:])
main()

Solution (Python):
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=[0]
visited = [False]*n

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

Solution (Python):
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[[0,10**18] for _ in range(n+1)]
q=collections.deque()
q.append((1,0))
check=[0]*(n+1)
check[1]=1
while len(q)!=0:
  v,d=q.popleft()
  for u in g[v]:
    if ans[u][1]>d:
      ans[u][0]=v
      ans[u][1]=d
    if check[u]==0:
      check[u]=1
      q.append((u,d+1))
print('Yes')
for i in range(2,n+1):
  print(ans[i][0])

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 1000000007


INF = float("inf")
import heapq


ans = []
def dijkstra_heap(G, s, n):
    d = [INF] * n           
    used = [False] * n
    d[s] = 0
    used[s] = False

    edgelist = []
    for edge in G[s]:
        heapq.heappush(edgelist, [edge[0], edge[1], s])

    while len(edgelist) > 0:
        minedge = heapq.heappop(edgelist)       
        dist, v, pv = minedge[0], minedge[1], minedge[2]
        
        if used[v]:
            continue
        ans[v] = pv
        d[v] = dist
        used[v] = True

        
        for edge in G[v]:
            cost, nv = edge[0], edge[1]
            if used[nv]:
                continue
            heapq.heappush(edgelist, [d[v] + cost, nv, v])
    
    return d


def main():
    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([1, b])
        G[b].append([1, a])

    for _ in range(N):
        ans.append(-1)
    dijkstra_heap(G, 0, N)

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


if __name__ == '__main__':
    main()

Solution (Python):

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

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

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

def make_shirube(n):
    target_list = N_list[n]
    next_list = []
    for room in target_list:
        if ans_list[room] == -1:
            ans_list[room] = n
            next_list.append(room)
    return next_list

next_loop_list = make_shirube(1)
while len(next_loop_list) > 0:
    temp_list = []
    for room in next_loop_list:
        temp_list.append(make_shirube(room))
    next_loop_list = [flatten for inner in temp_list for flatten in inner]
if ans_list[1:].count(-1) == 0:
    print("Yes")
    print("\n".join(map(str, ans_list[2:])))
else:
    print("No")

Solution (Python):

"""
@author: H_Hoshigi
"""

import queue

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

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

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

    next_rooms_queue = queue.Queue()
    next_rooms_queue.put(0)
    now_room = int()
    while not next_rooms_queue.empty():
        now_room = next_rooms_queue.get()
        for i in connedted_room_list[now_room]:
            if answer_list[i] == -1:
                answer_list[i] = now_room
                next_rooms_queue.put(i)

    
    is_escapable = True
    '''
    for i in range(1, N):
        if answer_list[i] == -1:
            is_escapable = False
            break
    '''

    if is_escapable:
        print("Yes")
        for i in range(1, N):
            print(answer_list[i]+1)
    else:
        print("No")

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

queue=deque([1])
vs = set([1])
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)
print("Yes")
for x in parents[2:]:
    print(x)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    
dist = [-1] * N
dist[0] = 0
    
queue = deque([0])

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

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

Solution (Python):

n,m=map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
maze = []
inf = 9999999
dist = [inf]* n
dist[0] = 0
queue = []
answer = [0]*n

goto = [[] * 1 for i in range(n)]
for i in range(len(ab)):
    goto[ab[i][0]-1].append(ab[i][1]-1)
    goto[ab[i][1]-1].append(ab[i][0]-1)

queue.extend([0])

while queue != []:
    go = queue.pop(0)
    for h in goto[go]:
        if dist[h] == inf:
            queue.append(h)
            dist[h] = dist[go]+1
            answer[h] =go+1
            

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

Solution (Python):
import sys
import numpy as np




from collections import deque

input = sys.stdin.readline
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    n, m = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(m)]
    graph = [[] for _ in range(n)]
    for a, b in AB:
        graph[a-1].append(b)
        graph[b-1].append(a)
    dist = np.ones(n)
    dist *= -1
    dist[0] = 0
    queue = deque([1])
    while queue:
        p = queue.popleft()
        for next in graph[p-1]:
            if dist[next-1] == -1:
                dist[next-1] = p
                queue.append(next)

    if np.count_nonzero(dist == -1) > 0:
        print('No')
    else:
        print('Yes')
        for d in dist[1:]:
            print(int(d))


if __name__ == '__main__':
    main()

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



ans = [-1] * (N + 1)
ans[1] = 0
ans[0] = 0
stack = deque([1])
def dfs():
    while len(stack) > 0:
        now = stack.popleft()
        for r in road[now]:
            if ans[r] == -1:
                ans[r] = now
                stack.append(r)
dfs()

temp = set(ans)

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

Solution (Python):
from heapq import heappop, heappush

def dijkstra(s):
    used = [1] * N
    dp = [INF] * N
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

INF = 10 ** 18
N, M = map(int, input().split())
cost = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    cost[a].append([1, b])
    cost[b].append([1, a])
dp1 = dijkstra(0)
for i in dp1:
    if i == INF:
        print('No')
        exit()
print('Yes')
for i in range(1, N):
    tmp = dp1[i] - 1
    for j in cost[i]:
        if dp1[j[1]] == tmp:
            print(j[1] + 1)
            break

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

queue = deque([1])
visited = {1: 1}

while len(queue) != 0:
    curr = queue.popleft()
    for _next in load[curr]:
        if visited.get(_next, -1) == -1:
            visited[_next] = curr
            queue.append(_next)

if len(visited) == n:
    print("Yes")
    for i in range(2, n+1):
        print(visited[i])
else:
    print("No")

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
from collections import Counter,deque,defaultdict





n,m=n1()
ab=n3(m)

node=defaultdict(list)
for a,b in ab:
    node[a].append(b)
    node[b].append(a)
    
p=deque([1])
d=[0]*(n+1)
while len(p)>0:
    c=p.popleft()
    for i in node[c]:
        if d[i]==0:
            d[i]=c
            p.append(i)
            
print("Yes")
for i in range(2,n+1):
    print(d[i])

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
from collections import Counter,deque,defaultdict





n,m=n1()
ab=n3(m)

node=defaultdict(list)
for a,b in ab:
    node[a].append(b)
    node[b].append(a)
    
p=deque([1])
d=[0]*(n+1)
while len(p)>0:
    c=p.popleft()
    for i in node[c]:
        if d[i]==0:
            d[i]=c
            p.append(i)
            
print("Yes")
for i in range(2,n+1):
    print(d[i])

Solution (Python):
import math

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

hist= []
visited_pos = [-1] * n



ts = {}
for el in ab:
  wk = ts.get(el[0]) 
  if wk is None:
    sss  = set()
    ts[el[0]] = sss
  ts[el[0]].add(el[1])
  wk = ts.get(el[1]) 
  if wk is None:
    sss  = set()
    ts[el[1]] = sss
  ts[el[1]].add(el[0])




def tsk(pos):
  wk = ts.get(pos)
  if ts.get(pos) is None:
    return
  else:
    
    for e in wk:
      if visited_pos[e-1] < 0:
        visited_pos[e-1] = pos 
        hist.append(e) 

idx = 0
hist.append(1) 
while True:
  if idx >= len(hist):
    break
  else:
    tsk(hist[idx])
    idx += 1


ans = 'Yes'
for i in range(n):
  if visited_pos[i] == -1:
    ans = 'No'
    break

print(ans)
if ans == 'Yes':
  for i in range(1,n):
    print(visited_pos[i])

Solution (Python):
from collections import deque, defaultdict
N, M = map(int, input().split())
D = defaultdict(list)
for i in range(M):
    s, t = map(int, input().split())
    D[s].append(t)
    D[t].append(s)

q = deque()
q.append(1)
d = defaultdict(lambda : float("inf"))
d[1] = 0
while q:
    u = q.popleft()
    for v in D[u]:
        if d[v] == float("inf"):
            d[v] = u
            q.append(v)

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

Solution (Python):
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 = [0]

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

while q:
    l = q.pop(0)
    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')

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M = map(int, rl().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    ans = [0] * N
    que = deque([0])
    while que:
        cur = que.popleft()
        for child in graph[cur]:
            if ans[child] == 0:
                ans[child] = cur + 1
                que.append(child)
    
    if any(ansi == 0 for ansi in ans[1:]):
        print('No')
    else:
        print('Yes')
        print(*ans[1:], sep='\n')


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import itertools
import numpy as np
from collections import Counter
import math

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, input().split(' '))
G = [[] for _ in range(N+1)]
ans = [0]*(N+1)
count = 0
for i in range(M):
    A, B = map(int, input().split(' '))
    G[A].append(B)
    G[B].append(A)

s = [1]
for i in range(N):
    ne = []
    for i in s:
        for j in G[i]:
            if ans[j] == 0:
                ans[j] = i
                count += 1
                ne.append(j)
    s = ne
if 0 in ans[1:]:
    print('No')
    exit()
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Solution (Python):
def main():
  from collections import deque
  n,m=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  
  l=deque([1])
  ans=[-1]*n
  while l:
    x=l.popleft()
    for i in ab[x]:
      if ans[i-1]==-1:
        ans[i-1]=x
        l.append(i)
  print('Yes')
  for i in ans[1:]:
    print(i) 
    
if __name__=='__main__':
  main()

Solution (Python):
import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}
results[0] = (0, 0)
used = set()

while queue:
    cost, cur = queue.pop()
    if cur in used:
        continue
    used.add(cur)
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.appendleft((next_cost, next_cur))

is_no = False
for k, result in results.items():
    if k == 0:
        continue
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for k, result in results.items():
        if k == 0:
            continue
        print(result[1] + 1)

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

dist = [1000000] * n
ans = [None]*n
not_visited = set(range(n))
not_visited.remove(0)
vs = deque([0])
dist[0] = 0
while vs:
    v = vs.popleft()
    for other_side in e[v]:
        if other_side in not_visited:
            vs.append(other_side)
            not_visited.remove(other_side)
            if dist[other_side] > dist[v] + 1:
                dist[other_side] = dist[v] + 1
                ans[other_side] = v

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

Solution (Python):
import collections,copy,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
AB = [LI() for _ in range(M)]
graph = {i:collections.deque() for i in range(1,N+1)} 
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
seen = [0]*(N+1) 
min_dist = [-1]*(N+1) 
queue = collections.deque() 
def bfs():
    c_graph = copy.deepcopy(graph)
    seen[1] = 1
    queue.append(1)
    min_dist[1] = 0
    while queue:
        q_NO = queue.popleft()
        q_dist = min_dist[q_NO]
        if not c_graph[q_NO]:
            continue
        g = c_graph[q_NO]
        for _ in range(len(g)):
            g_NO = g.popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            queue.append(g_NO)
            min_dist[g_NO] = q_dist+1
bfs()
if not all(seen[2:]):
    print('No')
    exit()
print('Yes')
for j in range(2,N+1):
    ans,dist = 0,float('INF')
    for x in graph[j]:
        if dist>=min_dist[x]:
            ans = x
            dist = min_dist[x]
    print(ans)

Solution (Python):
from collections import deque


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

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

ab_count = {key:[] for key in range(1,n+1)}

for i in range(m):
    ab_count[ab_list[i][0]].append(ab_list[i][1])
    ab_count[ab_list[i][1]].append(ab_list[i][0])




que = deque()


que.append([1,0])

checked_dict = {key:[] for key in range(1,n+1)}

where = 0

while que:
    x_pop = que.popleft()
    x = x_pop[0]
    if where != x_pop[1]:
        pass
        
        
        
        
        
        
        
        

    where = x_pop[1]

    for j in ab_count[x]:
        if len(checked_dict[j]) == 0:
            
            
            checked_dict[j].append(x)
            que.append([j,where+1])
        else:
            continue

    

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