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):
N, M = map(int, raw_input().split())
paths = {}
for m in range(M):
	path = map(int, raw_input().split())
	a_p = paths.get(path[0],[])
	b_p = paths.get(path[1],[])
	a_p.append(path[1])
	b_p.append(path[0])
	paths[path[0]] = a_p
	paths[path[1]] = b_p

visited = [False] * (N+1)

visited[0] = True
to_visit = [1]
signposts = [None] * (N+1)
i = 0
while len(to_visit) > i:
	curr = to_visit[i]
	if visited[curr]:
		i += 1
	else:
		path = paths[curr]
		for p in path:
			if signposts[p] == None:
				signposts[p] = curr
				to_visit.append(p)
		visited[curr] = True
		i += 1
all_visited = all(visited)

if all_visited:
	print 'Yes'
	for s in range(2,len(signposts)):
		print signposts[s]
else:
	print 'No'

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

roads = [[] for _ in range(N)]
for _ in range(M):
    _from, _to = map(int, input().split())
    roads[_from-1].append(_to-1)
    roads[_to-1].append(_from-1)

visited = [False] * N
ans = [None] * N
visited[0] = True
prevs = [0]
for _ in range(N):
    next_prevs = []
    for prev in prevs:
        for to in roads[prev]:
            if not visited[to]:
                visited[to] = True
                ans[to] = prev
                next_prevs.append(to)
    prevs = next_prevs

if not all(visited):
    print("No")
    exit(0)
print("Yes")
for i in range(1, N):
    print(ans[i]+1)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
path=[[] for i in range(n)]
start=[]
visited=[0]*n
visited[0]=1
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    start.append(b-1)
    visited[b-1]=1
  if b==1:
    start.append(a-1)
    visited[a-1]=1
  path[a-1].append(b-1)
  path[b-1].append(a-1)
que=deque(start)
while que:
  x=que.popleft()
  for i in path[x]:
    if visited[i]==0:
      visited[i]=x+1
      que.append(i)
print('Yes')
for i in range(n-1):
  print(visited[i+1])

Solution (Python):
n,m = map(int,input().split())
li = []
for _ in range(m):
    tmp = list(map(int,input().split()))
    li.append(tmp)

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

for l in li:
    a = l[0]-1
    b = l[1]-1
    ma[a].append(b)
    ma[b].append(a)


ans = [-1]*(n) 
q = [0]
while q:
    
    que = q.pop(0)
    for e in ma[que]:
        if ans[e]== -1:
            ans[e] = que
            q.append(e)
ans.pop(0)
if -1 in ans:
    print('No')
else:
    print('Yes')
    for aaa in ans:
        print(aaa+1)

Solution (Python):


import queue

N, M = map(int, input().split())
G = [[] for _ 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)

INF = 10 ** 5 + 1
ans = [INF] * N
Q = queue.Queue()
Q.put(0)
ans[0] = 0
while not Q.empty():
    u = Q.get()
    for g in G[u]:
        if ans[g] == INF:
            ans[g] = u + 1
            Q.put(g)

if max(ans) == INF:
    print('No')
else:
    print('Yes')
    for i in range(1, len(ans)):
        print(ans[i])

Solution (Python):
input_list = lambda : list(map(int,input().split()))



def bfs(s,n,node):
    c=[-1 for _ in range(n)]
    c[0]=0
    
    side_num_arr=list(map(lambda x :len(x),node))
    
    queue=[-1 for _ in range(n)]
    now=0
    queue[now]=s
    ans=[-1 for _ in range(n)]
    ans[0]=[0]
    last_ind=1
    while last_ind<n:
        
        if now>=n:
            return []
        c[queue[now]]=True
        if side_num_arr[queue[now]]<=0:
            now+=1
            continue
        for edge in node[queue[now]]:
            
            if side_num_arr[edge]<=0 or c[edge]==True:
                continue
            side_num_arr[edge]-=1
            
            queue[last_ind]=edge
            last_ind+=1
            c[edge]=True
            ans[edge]=queue[now]

        side_num_arr[queue[now]]=0
        now+=1
    return ans



n,m=input_list()
node=[[] for _ in range(n)]

for i in range(m):
    u,v=input_list()
    u-=1
    v-=1
    node[u].append(v)
    node[v].append(u)



ans=bfs(0,n,node)
if len(ans)==0:
    print("No")
    exit()

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

Solution (Python):
from collections import deque, defaultdict
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)
if len(set(graph.keys())) != N:
    print('No')
    exit()

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v]:
        if nv in visited:
            continue
        if tokens[nv] < 0:
            tokens[nv] = v
            q.append(nv)

print('Yes')
[print(t + 1) for t in tokens[1:]]

Solution (Python):
import collections


def bfs(dq, g, current, before, seen: {}):
    
    while len(dq) > 0:
        base = dq.popleft()
        _crt = base[0]
        _cnt = base[1]
        _cnt2 = _cnt + 1
        _nxt = g[_crt]
        for x in _nxt:
            
            if x == before:
                continue
            
            seen.setdefault(x, (-1, -1))
            if seen[x][0] != -1:
                continue
            
            seen[x] = (_crt, _cnt2)
            dq.append((x, _cnt2))


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

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

    dq = collections.deque()
    
    dq.append((1, 1))

    seen = {1: (-1, 0)}

    bfs(dq, g, 1, -1, seen)

    if len(seen.keys()) != n:
        print("No")
    else:
        print("Yes")
        for i in range(2, n + 1):
            print(seen[i][0])


main()

Solution (Python):
def bfs(G,start):
    from collections import deque
    dist = [-1] * n
    dist[start] = 0
    parent = [-1] * n
    parent[start] = 0
    q = deque([start])
    add,pop=q.append,q.popleft
    while q:
        v = pop()
        for nv in G[v]:
            if dist[nv] < 0:
                dist[nv] = dist[v]+1
                parent[nv] = v+1
                add(nv)
            
            
            
            
    return dist,parent

import numpy as np
import math
n,m = map(int,input().split())
roads = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    roads[a-1].append(b-1)
    roads[b-1].append(a-1)
dist, parent = bfs(roads,0)
if -1 in dist:
    print('No')
else:
    print('Yes')
    for i in parent[1:]:
        print(i)

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
AB = []
d = defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    
    A, B = min(A, B), max(A, B)
    AB.append((A, B))
    d[A].append(B)
    d[B].append(A)



V = [-1] * (N + 1)
R = [-1] * (N + 1)
V[1] = 0

q = d[1]
for i in d[1]:
    R[i] = 1
cnt = 0
while True:
    cnt += 1
    qq = []
    for i in q:
        if V[i] != -1:
            continue
        V[i] = cnt
        for j in d[i]:
            if R[j] == -1:
                qq.append(j)
                R[j] = i
    
    if qq:
        q = qq
    else:
        break



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

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

inf = float('inf')
distance = [[-1, inf] for i in range(n)] 
queue = deque([])

distance[0] = [0, 0]
queue.appendleft(0)

while len(queue) > 0:
  v = queue.popleft() 
  for next_v in graph[v]:
    judge = False
    if distance[next_v][0] == -1 or distance[v][1]+1 < distance[next_v][1]:
      distance[next_v] = [v, distance[v][1]+1]
      judge = True
    if judge:    
      queue.append(next_v)

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

Solution (Python):
n,m = map(int,input().split())
from collections import defaultdict,deque
l = defaultdict(list)

for i in range(m):
    ta,tb = map(int,input().split())
    ta-=1
    tb -=1
    l[ta].append(tb)
    l[tb].append(ta)
Q = deque()
Q.append([0,0])
dp = [-1]*n
dp[0] = 0
while Q:
    q,p = Q.popleft()
    
    
    for i in l[q]:
        
        
        if dp[i]==-1:
            dp[i] = q
            Q.append([i,p+1])
if -1 in dp:
    print('No')
else:
    print('Yes')
    for i in dp[1:]:
        print(i+1)

Solution (Python):
N, M = [int(i) for i in input().split()]

Mark = [0 for _ in range(N+1)]
path = {k: [] for k in range(1, N+1)}
for i in range(M):
    A, B = [int(i) for i in input().split()]
    path[A].append(B)
    path[B].append(A)
next = [1]
while True:
    n = next.pop(0)
    for x in path[n]:
        
        if Mark[x] == 0:
            Mark[x] = n
            next.append(x)
    if not next: break
if 0 in Mark[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join([str(i) for i in Mark[2:]]))

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

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


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


ans = [10**9] * (N+1)
ans[0] = 0
ans[1] = 0





from collections import deque
q = deque([1])

while q:
    p = q.popleft()
    for i in root[p]:
        if ans[i] == 10**9:
            
            ans[i] = p
            q.append(i)
            
            



if 10**9 in set(ans):
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(ans[i])

Solution (Python):
import heapq

inf = 10 ** 9


def dijkstra(a):
    color = ["white" for _ in range(n + 1)]
    D = [inf for _ in range(n + 1)]
    P =[-1 for _ in range(n+1)]

    P[a]=-1
    D[a] = 0
    color[a] = "gray"
    queue = [[0, a]]
    heapq.heapify(queue)

    while len(queue) > 0:
        u = heapq.heappop(queue)[1]
        if color[u] == "black": continue
        color[u] = "black"

        V = [[i, j] for i, j in M[u] if color[j] != "black"]
        if len(V) > 0:
            for i, j in V:
                if D[u] + i < D[j]:
                    D[j] = D[u] + i
                    color[j] = "gray"
                    P[j]=u
                    heapq.heappush(queue, [D[j], j])

    return P,D


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
M=[[] for _ in range(n+1)]
for a,b in AB:
    M[a].append([1,b])
    M[b].append([1,a])
P,D=dijkstra(1)
if inf not in D[1:]:
    print("Yes")
    for i in P[2:]:
        print(i)
else:print("No")

Solution (Python):
from collections import deque

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

roots = [0] * N
visited = set([])
table = [[] for i in range(N)]

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

visited.add(0)
que = deque([0])

while que:
    cur = que.popleft()
    for target in table[cur]:
        if target in visited:
            continue
        visited.add(target)
        que.append(target)
        roots[target] = cur

print('Yes')
for r in roots[1:]:
    print(r+1)

Solution (Python):
import queue


n, m = map(int, input().split())
to_room = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    to_room[a].append(b)
    to_room[b].append(a)
visited = [False for i in range(n+1)]
visited[0] = True
ans = [0 for i in range(n+1)]

q = queue.Queue()

def putting(t):
    global q
    for i in to_room[t]:
        if visited[i] == False:
            q.put((t, i))
            visited[i] = True

putting(1)
visited[1] == True
while not q.empty():
    prog = q.get()
    ans[prog[1]] = prog[0]
    putting(prog[1])


if all(visited):
    print("Yes")
    for i in range(n+1):
        if not (i == 0 or i == 1):
            print(ans[i])
else:
    print("No")

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
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 print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False


def bfs(graph, initial):
    n = len(graph) - 1
    dist = [-1] * (n + 1)
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]

        for i, e in enumerate(nxt):
            if visited[e] is False:
                q.append(e)
                dist[e] = edge
                visited[e] = True

    return dist


def main():
    N, M = MI()
    graph = [[] for i in range(N+1)]

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

    ret = bfs(graph, 1)

    for i in range(2, len(ret)):
        if ret[i] == -1:
            print('No')
            return

    print('Yes')
    for i in range(2, len(ret)):
        print(ret[i])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n,m = map(int,input().split())
tree=[[] for _ in range(n+1)]
ans=[0]*n 
for _ in range(m):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
checked=[False]*(n+1)
checked[1]=True
stack=deque([1])
while stack:
    p=stack.popleft()
    for i in tree[p]:
        if checked[i]:
            continue
        ans[i-1]=p
        checked[i]=True
        stack.append(i)

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

Solution (Python):
import sys
import heapq
from typing import Callable, List, NoReturn, Set


def dijkstra(n, path) -> List[int]:
    total_cost: List[int] = [10**5] * (n + 1)
    total_cost[1] = 0

    pointers: List[int] = [-1] * (n + 1)
    pointers[1] = 0

    not_checked: Set[int] = set(range(1, n + 1))
    checked: Set[int] = set()
    cur_node: int = 1
    h: List = []

    while not_checked:
        checked.add(cur_node)
        not_checked -= {cur_node}

        for next_node in path[cur_node]:
            if next_node in not_checked:
                heapq.heappush(h, (total_cost[cur_node] + 1, next_node, cur_node))

        if not_checked:
            cost, next_node, prev_node = heapq.heappop(h)  

            while next_node in checked:
                cost, next_node, prev_node = heapq.heappop(h)

            cur_node = next_node
            total_cost[cur_node] = cost
            pointers[cur_node] = prev_node

    return pointers


def main() -> NoReturn:
    readline: Callable[[], str] = sys.stdin.readline

    n, m = map(int, readline().rstrip().split())  
    path: List[List[int]] = []
    for _ in range(n + 1):
        path.append([])
    for _ in range(m):
        a, b = map(int, readline().rstrip().split())  
        (path[a]).append(b)
        (path[b]).append(a)

    print("Yes")
    pointers: List[int] = dijkstra(n, path)
    for i in range(2, n + 1):
        print(pointers[i])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N,M=map(int,input().split(' '))
chk = [0 for i in range(N+1)]
chk[0]=chk[1]=1
maze = [[] for i in range(N+1)]
for i in range(M):
    a,b=list(map(int,list(input().split(' '))))
    maze[a].append(b)
    maze[b].append(a)
l = deque([1])
while l:
    n = deque.popleft(l)
    for i in maze[n]:
        if not chk[i]:
            chk[i]=n
            l.append(i)
if 0 in chk:
    print('No')
    exit()
print('Yes')
for i in chk[2:]:
    print(i)

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    path_list = [[int(item) for item in input().split()] for _ in range(M)]

    to_list = [[] for _ in range(N+1)]
    from_list = [[] for _ in range(N+1)]
    order_list = [[] for _ in range(N+1)]

    for path in path_list:
        to_list[path[0]] += [path[1]]
        to_list[path[1]] += [path[0]]

    

    que = collections.deque([1])
    cnt = 0

    while que:
        temp = que.popleft()
        cnt += 1

        order_list[temp] = 1

        if len(to_list[temp])>=1:
            for to in to_list[temp]:
                if from_list[to] == []:
                    from_list[to] = temp
                    que.append(to)

    print('Yes')
    for item in from_list[2:]:
        print(item)



if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from collections import defaultdict
N, M = [int(x) for x in sys.stdin.readline().split()]
edges = defaultdict(list)
for i in range(M):
    A, B = [int(x) for x in sys.stdin.readline().split()]
    edges[A].append(B)
    edges[B].append(A)

answer = [None] * (N + 1)
visited = [1]
while True:
    new_visited = []
    for v in visited:
        for w in edges[v]:
            if answer[w] == None:
                answer[w] = v
                new_visited.append(w)
    visited = new_visited
    if not visited:
        break

answer = answer[2:]
if None in answer:
    print("No")
else:
    print("Yes")
    for a in answer:
        print(a)

Solution (Python):
from collections import defaultdict

n,m=map(int,input().split(' '))
paths=defaultdict(list)
for _ in range(m):
    a,b=map(int,input().split(' '))
    paths[a].append(b)
    paths[b].append(a)

parents=[1]
visited=[0]*(n+1)
visited[1]=1

def children(parents):
    children=[]
    for p in parents:
        for c in paths[p]:
            if visited[c]==0:
                children.append(c)
                visited[c]=p
    return children

while True:
    parents=children(parents)
    if parents==[]:
        break
print('Yes')
for i in range(2,n+1):
    print(visited[i])

Solution (Python):
N,M = map(int,input().split(" "))
pathway = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split(" "))
    pathway[A-1].append(B-1)
    pathway[B-1].append(A-1)
visit = [0 for i in range(N)]
guide = [-1 for i in range(N)]
point = [0]
while True:
    next_point = []
    for i in point:
        for j in pathway[i]:
            if visit[j]==0:
                guide[j] = i
                visit[j] = 1
                next_point.append(j)
    point = next_point
    if len(point) == 0:
        break
print("Yes")
for i in range(1,N):
    print(guide[i]+1)

Solution (Python):
n,m,*ab=map(int,open(0).read().split())
path={}
for i in range(n):
  path[i]=[]
for i in range(m):
  a,b=ab[i*2]-1,ab[i*2+1]-1
  path[a].append(b)
  path[b].append(a)
direction=[i for i in range(n)]
fin=[False for i in range(n)]
fin[0]=True
i=0
queue=[0]
while i<n:
  i+=1
  queue2=queue.copy()
  queue.clear()
  if len(queue2)==0:
    break
  for j in queue2:
    fin[j]=True
    for k in path[j]:
      if not fin[k]:
        direction[k]=j
        fin[k]=True
        queue.append(k)
print('Yes')
for i in range(1,n):
  print(direction[i]+1)

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

graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)
    
r = [-1 for i in range(N+1)] 
Q = deque([1])
r[1] = 0
while Q:
    x = Q.popleft()
    for to in graph[x]:
        if r[to] == -1:
            r[to] = x 
            Q.append(to)

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

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

n, m = na()
ab = nan(m)

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

ans = [-1 for _ in range(n)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        p, l = q.popleft()
        if ans[p] != -1:
            continue
        ans[p] = l
        for v in g[p]:
            q.append((v, p))

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

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

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

    que = deque([0])
    while True:
        fr = que.popleft()
        for to in graph[fr]:
            if trace[to] != -1:
                continue
            trace[to] = fr
            que.append(to)
        if len(que) == 0:
            break

    if -1 in trace:
        print('No')
        return

    print('Yes')
    for t in trace[1:]:
        print(t+1)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
N,M=map(int,input().split())
d=dict()
for i in range(M):
  a,b=map(int,input().split())
  d.setdefault(a,set()).add(b)
  d.setdefault(b,set()).add(a)
s=set()
label=dict()
A=deque()
A.append(1)
while A:
  a=A.popleft()
  b=d[a]
  b-=s
  for i in b:
    if i not in label:
      label[i]=a
      A.append(i)
k=deque(sorted(label.keys()))
a=k.popleft()
print("Yes")
for i in k:
  print(label[i])

Solution (Python):
import sys
def input():
    return sys.stdin.readline().rstrip('\n')

def calc(N, M, G):
    d = {i: [] for i in range(1, N + 1)}
    for a, b in G:
        m = min(a, b)
        n = max(a, b)
        d[m] += [n]
        d[n] += [m]
    s = d[1]
    ans = {i: 1 for i in s}
    ans[1] = 0
    while s:
        new_s = set()
        for t in s:
            for k in d[t]:
                if not k in ans:
                    ans[k] = t
                    new_s.add(k)
        s = new_s
    return 'Yes\n' + '\n'.join([str(ans[i]) for i in range(2, N + 1)])

    

(N, M) = tuple([int(s) for s in input().split()])
G = [tuple([int(s) for s in input().split()]) for _ in range(M)]
print(calc(N, M, G))

Solution (Python):


from collections import deque

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

ans_arr = [-1] * (N)
q = deque()
ans_arr[0] = 0 
q.append(0)

while len(q)>0:
    n = q.popleft()
    for i in tree[n]:
        if ans_arr[i] == -1:
            ans_arr[i] = n+1
            q.append(i)

ans = 'Yes'
for i in ans_arr[1:]:
    if i == -1:
        ans = 'No'
        break

if ans == 'No':
    print(ans)
else:
    print(ans)
    for i in ans_arr[1:]:
        print(i)

Solution (Python):
import heapq

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

def getAdjListFromEdgePairs(list_EdgePairs, nodenum):
    
    list1 = sorted(list_EdgePairs)
    list_Adjlist = [[] for _ in range(nodenum)] 
    
    for list2 in list1:
        list_Adjlist[list2[0]-1].append(list2[1])
        list_Adjlist[list2[1]-1].append(list2[0])

    return list_Adjlist

adj = getAdjListFromEdgePairs(list_EdgePairs, n)


T = [0 for _ in range(n)]
D = [n for _ in range(n)]
D[0] =0
S = [(0, 1)]
heapq.heapify(S)
check = [False for _ in range(n)]


while len(S) > 0:
    u = heapq.heappop(S)
    if check[u[1]-1] == False:
        check[u[1]-1] == True
        for i in adj[u[1]-1]:
            if D[i-1] > D[u[1]-1] + 1:
                D[i-1] = D[u[1]-1] + 1
                T[i-1] = u[1]
                heapq.heappush(S, (D[i-1], i))

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

Solution (Python):
from collections import deque

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

mapping = {}
for n in range(N):
    mapping[n+1] = []

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

dest = {}
distance = {}
for n in range(N):
    distance[n+1] = -1
    dest[n+1] = -1

stack = deque()
stack.append(1)
distance[1] = 0

while len(stack) != 0:
    number = stack.popleft()
    next_distance = distance[number]+1

    for m in mapping[number]:
        if distance[m] >= 0:
            continue
        else:
            dest[m] = number
            distance[m] = next_distance
            stack.append(m)

for n in range(N):
    if distance[n+1] < 0:
        print("No")
        exit()

print("Yes")
for n in range(1, N):
    print(dest[n+1])

Solution (Python):
import math

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] += [b-1]
    path[b-1] += [a-1]

length = [-1]*N
last = [-1]*N

Q = [0]
while Q:
    n = Q.pop(0)
    for x in path[n]:
        if length[x] == -1:
            length[x] = length[n] + 1
            last[x] = n
            Q += [x]
        elif length[x] > (length[n] + 1):
            length[x] = length[n] + 1
            last[x] = n

print("Yes")
print("\n".join([str(n+1) for n in last[1:]]))

Solution (Python):
import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    next_n = [0] * n
    used[s] = False
    edgelist = []
    for e in edge[s]:
        e.append(s)
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        next_n[v] = minedge[2]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1],v])
    return d, next_n


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

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

for i in range(w):
    a,b = map(int,input().split())
    edge[b-1].append([1,a-1])
    edge[a-1].append([1,b-1]) 
res_list, next_list = dijkstra_heap(0)
if float('inf') in res_list:
  print("No")
else:
  print("Yes")
  for res in next_list[1:]:
    print(res+1)

Solution (Python):
from collections import deque

n, m = [0] * 2
a = []
b = []

def format_input(filename = None):
	global n, m
	global a, b
	if filename == None:
		n, m = list(map(int, input().split()))
		ab = [list(map(int, input().split())) for i in range(m)]
		for i in ab:
			a.append(i[0])
			b.append(i[1])

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 10**5)
		m = rng(1, 2 * 10**5)
		a = [rng(1, n) for i in range(m)]
		b = [rng(1, n) for i in range(m)]
		print(n, m)
		[print(a[i], b[i]) for i in range(m)]

def get_answer():
	answer = 'No'
	parent = [0] * (n+1)
	child = [[] for i in range(n+1)]
	for i in range(m):
		child[a[i]].append(b[i])
		child[b[i]].append(a[i])

	visited = [False] * (n+1)
	q = deque()
	q.append(1)
	visited[1] = True
	while len(q) > 0:
		node = q.popleft()
		for i in child[node]:
			if not visited[i]:
				visited[i] = True
				q.append(i)
				parent[i] = node

	if parent.count(0) == 2:
		answer = 'Yes'

	print(answer)
	if answer == 'Yes':
		for i in range(n-1):
			print(parent[i+2])
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()

Solution (Python):
n, m = map(int, input().split())
ab = []
import numpy as np
par = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  par[a-1].append(b-1)
  par[b-1].append(a-1)
d = [-1 for i in range(n)]
d[0] = 0

import queue
q = queue.Queue()
q.put(0)
while not q.empty():
  current = q.get()
  
  for p in par[current]:
    if d[p] == -1:
      q.put(p)
      d[p] = current
if -1 in d:
  print("No")
else:
  print("Yes")
  for p in d[1:]:
    print(p+1)

Solution (Python):
from collections import defaultdict, deque

n,m = map(int, input().split())
path = defaultdict(set)
for _ in range(m):
   a, b = map(int, input().split())
   path[a] |= {b}
   path[b] |= {a}

queue = deque([(1, 0)])

visited = set()
res = {1: 0}
while queue != deque([]):
   pos, depth = queue.popleft()
   for p in path[pos]:
      if p in res:
         continue
      res[p] = pos
      queue.append((p, depth+1))
   
print('Yes')
for k,v in sorted(res.items(), key=lambda x: x[0]):
   if k != 1:
      print(v)