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

def main():
    N,M,*ab = map(int, read().split())

    E = [[] for _ in range(N+1)]
    for a, b in zip(*[iter(ab)]*2):
        E[a].append(b)
        E[b].append(a)

    par = [0] * (N+1)
    seen = [-1] * (N+1)
    seen[1] = 0
    queue = deque([1])

    while queue:
        v = queue.popleft()
        for e in E[v]:
            if seen[e] == -1:
                seen[e] = seen[v] + 1
                par[e] = v
                queue.append(e)
    
    for i in range(1, N+1):
        if seen[i] == -1:
            print("No")
            exit()
    
    print("Yes")
    print("\n".join(map(str, par[2:])))

    

if __name__ == "__main__":
    main()

Solution (Python):
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()


def resolve():
    N, M = LI()
    G = [[] for _ in range(N)]
    for _ in range(M):
        A, B = LI_()
        G[A].append(B)
        G[B].append(A)

    que = collections.deque()
    que.append(0)
    dist = [INF]*N
    dist[0] = 0
    ans = [-1]*N
    while que:
        room_c = que.popleft()
        for room_n in G[room_c]:
            if dist[room_n]>=INF:
                que.append(room_n)
                dist[room_n] = dist[room_c] + 1
                ans[room_n] = room_c
    
    
    if -1 in ans[1:]:
        print('No')
    else:
        print('Yes')
        for i in ans[1:]:
            print(i+1)

if __name__ == '__main__':
    resolve()

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

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

from collections import deque

d_list = [N + 1] * N
queue = deque()
queue.append(0)
d_list[0] = 0
while len(queue) > 0:
	cur = queue.popleft()
	d = d_list[cur] + 1
	for n in edges[cur]:
		d2 = d_list[n]
		if d2 > d:
			d_list[n] = d
			queue.append(n)

d_pair_list = [(d, i) for i, d in enumerate(d_list)]

def check():
	result = [None] * N
	result[0] = -1
	for d, cur in d_pair_list:
		for n in edges[cur]:
			if d_list[n] == d - 1:
				result[cur] = n
				break
		if result[cur] == None:
			return None
	return result

result = check()
if result != None:
	print("Yes")
	for i in range(1, N):
		print(result[i] + 1)
else:
	print("No")

Solution (Python):
import collections


def solve(N, M, ABs):
    nextrooms = []
    for _ in range(N):
        nextrooms.append(-1)

    ways = {}
    for a, b in ABs:
        ways.setdefault(a - 1, []).append(b - 1)
        ways.setdefault(b - 1, []).append(a - 1)

    queue = collections.deque()
    queue.append(0)
    while queue:
        room = queue.popleft()
        for nextroom in ways[room]:
            if nextrooms[nextroom] == -1:
                nextrooms[nextroom] = room + 1
                queue.append(nextroom)

    nextrooms[0] = "Yes"
    return "\n".join(str(r) for r in nextrooms)


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

Solution (Python):
from collections import deque

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

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

visited = [-1] * N
visited[0] = 0
que = deque([(0, -1)])

while que:
    ci, p = que.popleft()

    for ni in G[ci]:
        if visited[ni] == -1:
            que.append((ni, ci))
            visited[ni] = ci+1

if -1 in visited:
    print('No')
else:
    print('Yes')
    print(*visited[1:], sep='\n')

Solution (Python):


from collections import deque

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


parent = {}
queue = deque()
queue.append((1, 1))

while len(queue) > 0:
    p, q = queue.popleft()
    if q in parent: 
        continue
    parent[q] = p
    for v in adj[q]:
        queue.append((q, v))

if all(u in parent for u in range(2, n+1)):
    print('Yes')
    for u in range(2, n+1):
        print(parent[u])
else:
    print('No')

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic=defaultdict(list)
for i in range(m):
    a,b=ab[i]
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)

itta=[-1]*n

d=deque([0])
while d:
    tmp=d.popleft()
    for i in range(len(dic[tmp])):
        if itta[dic[tmp][i]]==-1:
            itta[dic[tmp][i]]=tmp
            d.append(dic[tmp][i])


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

Solution (Python):
from heapq import heappush, heappop
def dijkstra(n, graph, s):
    dist = [float('inf')] * n
    from_v = [-1] * n
    hq = [(0, s)]
    dist[s] = 0
    while hq:
        c, v = heappop(hq)
        if dist[v] < c:
            continue
        for t, cost in graph[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                from_v[t] = v
                heappush(hq, (dist[t], t))
    return dist, from_v

def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append((b,1))
        graph[b].append((a,1))
    dist, from_v = dijkstra(N, graph, 0)
    if float("inf") in dist:
        print("No")
        sys.exit()
    else:
        print("Yes")
        for ans in from_v[1:]:
            print(ans+1)

if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
graph={i:[] for i in range(1,N+1)}
for _ in range(M):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
visited=[False for i in range(N+1)]
par=[-1 for i in range(N+1)]
from collections import deque
d=deque()
visited[1]=True
d.append(1)
e=deque()
while d:
    while d:
        x=d.popleft()
        for node in graph[x]:
            if visited[node]==False:
                par[node]=x
                visited[node]=True
                e.append(node)
    if e:
        d=e
        e=deque()
    else:
        d=deque()
flag=True
for i in range(2,N+1):
    if par[i]<0:
        flag=False
        break
if flag:
    print("Yes")
    for i in range(2,N+1):
        print(par[i])
else:
    print("No")

Solution (Python):
import math
import collections

N, M = [int(s) for s in input().split()]
graph = {i:[] for i in range(1, N+1)}
for _ in range(M):
    v1, v2 = [int(s) for s in input().split()]
    graph[v1].append(v2)
    graph[v2].append(v1)

queue = collections.deque([1])
visited = set([1])
pre = dict()
while queue:
    v = queue.popleft()
    for w in graph[v]:
        if w not in visited:
            queue.append(w)
            visited.add(w)
            pre[w] = v
if len(visited) != N:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(pre[i])

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

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

d = [0]*(N+1)

def bfs(v):
    stack = deque([v])
    while stack:
        v = stack[0]
        if graph[v]:
            w = graph[v].popleft()
            if d[w] == 0:
                d[w] = v
                stack.append(w) 
        else:
            stack.popleft()        

bfs(1)

for i in range(2, N+1):
    if d[i] == 0:
        print("No")
        sys.exit()

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

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque

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

ans = [-2] * n
def bfs(p, v):
    dq = deque()
    dq.append((p, v))
    while dq:
        p, v = dq.popleft()
        if ans[v] == -1:
            ans[v] = p
        for nv in edge[v]:
            if nv == p:
                continue
            if ans[nv] == -2:
                dq.append((v, nv))
                ans[nv] = -1 

bfs(-1, 0)
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    for item in ans[1:]:
        print(item + 1)

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


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

    """
    幅優先探索
    """

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

    while q:
        u = q.popleft()
        for v in repn[u]:
            if parent[v] != -1:
                continue
            parent[v] = u
            q.append(v)
    print("Yes")
    for i in range(1, N):
        print(parent[i] + 1)



if __name__ == "__main__":
    main()

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):
n, m = map(int,input().split())

colist=[]
checks=[0]*n
kyori=[0]*n
mae=[0]*n

for i in range(n):
    colist.append([])

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





tugi=[0]
checks[0]=1
point=1
turn=1

while point<n and len(tugi)!=0:
    koho=[]
    for t in tugi:
        koho2=colist[t]
        for k2 in koho2:
            if checks[k2]==0:
                checks[k2]=1
                kyori[k2]=turn
                mae[k2]=t
                point+=1
                koho.append(k2)
    tugi=koho
    turn+=1

if point==n:
    print("Yes")
    for i in range(n-1):
        print(mae[1+i]+1)
else:
    print("No")

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

queue = deque()
queue.append(1)

guideposts = [-1]*(N+1)
guideposts[1] = 0
while queue:
    room = queue.popleft()
    for next_room in edges[room]:
        if guideposts[next_room] == -1:
            guideposts[next_room] = room
            queue.append(next_room)

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

Solution (Python):
from collections import deque
INF = float('inf')
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 = [INF] * (N+1)
dist[1] = 0
flag = [-1] * (N+1)
check = 1
q = deque([1])
while q:
  x = q.popleft()
  for nextx in graph[x]:
    if(dist[nextx] != INF):
      continue
    flag[nextx] = x
    dist[nextx] = dist[x] + 1
    q.append(nextx)
print('Yes')
for i in range(2, N+1):
  print(flag[i])

Solution (Python):
from collections import deque

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

q = deque([0])


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


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




color[0] = 0
while q:
  u = q.popleft()
  for v in E[u]:
    if color[v] == -1:
      q.append(v)
      color[v] = u


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

Solution (Python):
N,M = map(int,input().split())
es = [[] for _ in range(N)]

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


from collections import deque

q = deque()
INF = float("inf")
dist = [INF] * N
dist[0] = 0
come_by = [0] * N
q.append((0,0))
while q:
    cost, curr = q.popleft()
    for nxt in es[curr]:
        if cost + 1 < dist[nxt]:
            dist[nxt] = cost+1
            come_by[nxt] = curr+1
            q.append((dist[nxt], nxt))

print("Yes")
print(*come_by[1:], sep="\n")

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

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

for a,b in edges:
    adj[a].add(b)
    adj[b].add(a)

start=0
dst=[-1]*N
visited={0}

Q={start}

while Q:
    tmp=set()
    for cur in Q:
        for nex in adj[cur]:
            if nex in visited:
                continue
            dst[nex]=cur
            visited.add(nex)
            tmp.add(nex)
    Q=tmp

print("Yes")
print("\n".join(map(str,[v+1 for v in dst[1:]])))

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
graph = [[] for _ in range(N+1)]  
for _ in range(M):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist = dijkstra(1)
if INF in dist[1:]:
    print('No'); exit()

answer = [None] * (N+1)
for i in range(2, N+1):
    a = INF
    for c in graph[i]:
        if dist[c] < a:
            a = dist[c]
            answer[i] = str(c)

print('Yes')
print('\n'.join(answer[2:]))

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

ikeru = [[] for _ in range(n)]
for i,j in tuuro:
	ikeru[i].append(j)
	ikeru[j].append(i)

fukasa = [0 for _ in range(n)]
fukasamoto = [0 for _ in range(n)]
kaisuu = 0
settansaku = set([])
listmada = [0]
setmada = set([0])

while len(setmada) != 0:
	kaisuu += 1
	for i in listmada[:]:
		settansaku.add(i)
		listmada.remove(i)
		setmada.remove(i)
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					listmada.append(k)
					setmada.add(k)
					fukasa[k] = kaisuu
					fukasamoto[k] = i+1

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

Solution (Python):

import sys
from collections import deque

YES = "Yes"  

class Room:
    def __init__(self,index):
        self.index = index
        self.nPath = -1
        self.refs = []

    def connect(self,ref):
        self.refs.append(ref)
        ref.refs.append(self)

    def recSolve(self,queue):
        for r in self.refs:
            if r.nPath == -1:
                queue.append()

    def __str__(self):
        c = ""
        for r in self.refs:
            c += f"{r.index},"
        return f"{self.index}->{c} ({self.nPath})"

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    rooms = [Room(i) for i in range(N)]
    for j in range(M):
        rooms[A[j]-1].connect(rooms[B[j]-1])
    current = deque()
    current.append((rooms[0],0))
    while len(current) > 0:
        next = deque()
        for r in current:
            if r[0].nPath == -1:
                r[0].nPath = r[1]
                for k in r[0].refs:
                    if k.nPath == -1:
                        next.append((k,r[0].index))
        current = next
    
    
    print(YES)
    for r in rooms[1:]:
        print(r.nPath+1)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))
n,m=l_in()

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

for _ in range(m):
    a,b=l_in()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

from collections import deque    
vis = set()
vis.add(0)

marks = [-1]*n

q = deque()
q.append(0)

while len(q) > 0:
    u = q.popleft()

    for v in edges[u]:
        if v not in vis:
            q.append(v)
            marks[v] = u
            vis.add(v)


print("Yes")
[print(u+1) for u in marks[1:]]

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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

    root = [[] for _ in range(N + 1)]
    for a, b in AB:
        root[a].append(b)
        root[b].append(a)

    que = deque()
    que.append(1)
    front = [-1] * (N + 1)
    front[1] = 1
    while que:
        point = que.popleft()
        for i in root[point]:
            if front[i] > 0:
                continue
            front[i] = point
            que.append(i)

    if min(front[1:]) < 0:
        print('No')
    else:
        print('Yes')
        for i in range(2, N + 1):
            print(front[i])

if __name__ == '__main__':
    main()

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

A = {}
for i in range(1,N+1):
    A[i] = []

for a,b in data:
    A[a].append(b)
    A[b].append(a)

from collections import deque

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

while q:
    n = q.pop()
    for i in A[n]:
        if d[i] != -1:
            continue
        else:
            d[i] = n
            q.appendleft(i)
print('Yes')

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

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    E = defaultdict(list)
    michi = [-1] * (N+1)
    for _ in range(M):
        a, b = ZZ()
        E[a].append(b)
        E[b].append(a)

    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        if v == 1: michi[v] = 0
        for to in E[v]:
            if michi[to] != -1: continue
            michi[to] = v
            d.append(to)
    print('Yes')
    print(*michi[2:], sep='\n')

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import queue


n,m = readints()
path  =[[] for i in range(n)]

for i in range(m):
    a,b = readints()
    a-=1
    b-=1
    path[a].append(b)
    path[b].append(a)
d = [[] for i in range(n)]
d[0].append(0)

q = queue.Queue()
q.put(0)
visited = [-1]*n
visited[0]=0

ans = [0]*n

while not q.empty():
    p = q.get()
    for x in path[p]:
        if visited[x]==-1:
            visited[x]=visited[p]+1
            d[visited[x]].append(x)
            q.put(x)
            ans[x]=p+1

print('Yes')
printrows(ans[1:])

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

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

out = [None]*N

from collections import deque

dist = [None]*N
que = deque([0])
out[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] is not None:
            continue
        dist[w] = 1
        out[w] = v
        que.append(w)

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

Solution (Python):
from collections import deque

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

next_v = deque([0])
history = [-1]*n
INF = 10**18
dist = [INF]*n
dist[0] = 0
while next_v:
    v = next_v.popleft()

    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        history[v2] = v
        next_v.append(v2)


print('Yes')
for x in history[1:]:
    print(x+1)

Solution (Python):
from collections import deque

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

to = [[] for i in range(N)]

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

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

is_visited = [False] * N
pre_room = [-1] * N

while(len(q) != 0):
    tmp = q.popleft()
    is_visited[tmp] = True

    for i in to[tmp]:
        if is_visited[i]:
            continue
        q.append(i)
        is_visited[i] = True
        pre_room[i] = tmp

for i in range(1, N):
    if i == -1:
        print("No")
        exit()

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

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)

mae = [-1]*n
from collections import deque
def bfs(v):
    queue = deque([])
    d = [None]*n
    d[v] = 0
    queue.append(v)
    while queue:
        u = queue.popleft()
        for i in g[u]:
            if d[i] is None:
                d[i] = d[u] + 1
                mae[i] = u
                queue.append(i)
    return d
d = bfs(0)
print("Yes")
for i in mae[1:]:
    print(i + 1)

Solution (Python):
def main():

    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    import heapq
    h = [(0, 0)]
    heapq.heapify(h)
    d = [10**10]*n
    while h:
        dis, i = heapq.heappop(h)
        if d[i] == 10**10:
            d[i] = dis
            for j in g[i]:
                if d[j] == 10**10:
                    heapq.heappush(h, (dis+1, j))

    print("Yes")
    for i in range(1, n):
        minimum = 10**9
        dire = None
        for j in g[i]:
            if d[j] < minimum:
                minimum = d[j]
                dire = j
        print(dire+1)


main()

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

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(b)
        G[b].append(a)
    
    dist = [-1] * N
    before = [-1] * N
    dist[0] = 0
    q = deque([0])
    while q:
        v = q.popleft()
        for e in G[v]:
            if dist[e] >= 0:
                continue
            dist[e] = dist[v] + 1
            before[e] = v + 1
            q.append(e)
    flag = True
    for i in range(N):
        if dist[i] < 0:
            flag = False
            break

    if flag:
        print('Yes')
        print('\n'.join(map(str,before[1:])))
    else:
        print('No')
if __name__ == '__main__':
    main()

Solution (Python):
import heapq
n, M = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [[b, 1]]
  graph[b] += [[a, 1]]

def dijkstra(s):
  dist = [float('inf')]*n
  dist[s] = 0
  num = [0]*n
  num[s] = 1
  q = [[0, s]]
  pre = [0]*n
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
        pre[v] = u
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num, pre

dist, num, pre = dijkstra(0)
print('Yes')
for i in pre[1:]:
  print(i+1)

Solution (Python):
from collections import deque

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

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

answers = [0 for i in range(n)]

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

d = deque()
d.append(0)

seen = {}
will_seen = {}

while len(seen) < n:
    pos = d.popleft()
    if seen.get(pos, None) is not None:
        continue
    else:
        for next_pos in roads[pos]:
            if will_seen.get(next_pos, None) is None:
                d.append(next_pos)
                answers[next_pos] = pos + 1
                will_seen[next_pos] = 1
            seen[pos] = 1

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

Solution (Python):
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math



n, m = map(int, input().split())
E = [list(map(int, input().split())) for i in range(m)]
graph = [[] for _ in range(n)]
for e in E:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

s = [-1]*n
que = deque([0])
while que:
    node = que.popleft()
    for nxt in graph[node]:
        if s[nxt] == -1:
            s[nxt] = node+1
            que.append(nxt)

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

Solution (Python):
import collections
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)
q = collections.deque()
q.append(0)
dist = [-1]*N
dist[0] = 0
while len(q) != 0:
    v = q.popleft()
    for w in graph[v]:
        if dist[w] > -1:
            continue
        dist[w] = v + 1
        q.append(w)
print('Yes')
for i in range(1,N):
    print(dist[i])

Solution (Python):
n,m=list(map(int,input().split()))
r=[[]for i in range(n)]
for i in range(m):
  inp=list(map(lambda x:int(x)-1,input().split()))
  r[inp[0]].append(inp[1])
  r[inp[1]].append(inp[0])

w=[0 for i in range(n)]
w[0]=1
a=[0]
b=[]
while True:
  for i in a:
    for j in r[i]:
      if w[j]==0:
        w[j]=i+1
        b.append(j)
  if len(b)==0:
    break
  a=b
  b=[]
print("Yes")
for i in range(1,n):
  print(w[i])

Solution (Python):
n,m = map(int,input().split())
from collections import defaultdict
G = defaultdict(list)
for _ in range(m):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)





from collections import deque
dist = [-1]*n
que = deque([0])
dist[0] = 0
before = [0] * n
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        before[w] = v
        que.append(w)

if -1 in dist:
    print("No")
    exit()
else:
    print("Yes")
    for d in before[1:]:
        print(d+1)

Solution (Python):
import sys
import queue
import math

sys.setrecursionlimit(10**7)

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

sign = [None for _ in range(n)]
q = queue.Queue()
q.put(0)
while True:
    if q.empty():
        break
    rm = q.get()
    for to in edges[rm]:
        if sign[to] is None:
            sign[to] = rm
            q.put(to)
if None in sign[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(sign[i]+1)