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

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

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

next_queue.append(0)

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

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

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

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

next_queue.append(0)

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

Solution (Python):
from collections import deque

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

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

ans = bfs(graph)
print("Yes")
for i in range(2, len(ans)):
    print(ans[i])

Solution (Python):
from collections import deque

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

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

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

    q = deque([0])

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

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

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

if __name__ == '__main__':
    main()

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

Solution (Python):
from collections import deque

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

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

que = deque([0])

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

Solution (Python):
from collections import deque

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

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

que = deque([0])

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

Solution (Python):
from queue import Queue as que
q=que()
n,m=map(int,input().split())
e=[[] for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    e[a-1].append(s-1);e[s-1].append(a-1)
table=[0]*(n)
table[0]=1
ok=0
q.put(0)
while not q.empty():
    now=q.get()
    for to in e[now]:
        if table[to]==0:
            table[to]=now+1
            q.put(to)
            ok+=1
if n-1==ok:
    print("Yes",*table[1:],sep="\n")
else:print("No")

Solution (Python):
from collections import deque as que
q=que()
n,m=map(int,input().split())
e=[[] for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    e[a-1].append(s-1);e[s-1].append(a-1)
table=[0]*n
ok=0
table[0]=1
q.append(0)
while len(q):
    now=q.popleft()
    for to in e[now]:
        if table[to]==0:
            table[to]=now+1
            q.append(to)
            ok+=1
if n-1==ok:
    print("Yes",*table[1:],sep="\n")
else:print("No")

Solution (Python):

from collections import deque

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

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

q = deque([0])
while q:
    now = q.popleft()
    for v in path[now]:
        if ans[v] == -1:
            ans[v] = now
            q.append(v)
print('Yes')
for i in ans[1:]:
    print(i+1)

Solution (Python):
from sys import stdin, stdout
from collections import deque, defaultdict
from heapq import heappush, heappop, heapify

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	G = defaultdict(lambda: [])
	n, m = rli()
	for _ in range(m):
		u, v = rli()
		G[u].append(v)
		G[v].append(u)
	Q = deque([])
	seen = defaultdict(lambda: False)
	Q.appendleft((1, -1)) 
	posts = [-1 for _ in range(n + 1)]
	while Q:
		for _ in range(len(Q)):
			curr, prev = Q.pop()
			if seen[curr]: continue
			seen[curr] = True
			posts[curr] = prev
			for nbhr in G[curr]:
				if seen[nbhr]: continue
				Q.appendleft((nbhr, curr))
	print("Yes")
	for i in range(2, n+1):
		print(posts[i])
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
def resolve():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split()))for i in range(m)]
    ans = [0] * n
    edge = [[]for _ in range(n)]
    for a, b in ab:
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)
    visited = {0}
    stack = [0]
    for i in stack:
        for j in edge[i]:
            if j in visited:
                continue
            stack.append(j)
            visited.add(j)
            ans[j] = i + 1
    print("Yes")
    print('\n'.join(map(str, ans[1:])))


resolve()

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split()))for i in range(m)]
ans = [0] * n
edge = [[]for _ in range(n)]
for a, b in ab:
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
visited = {0}
stack = [0]
for i in stack:
    for j in edge[i]:
        if j in visited:
            continue
        stack.append(j)
        visited.add(j)
        ans[j] = i + 1
print("Yes")
print(*ans[1:])

Solution (Python):


from collections import deque

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

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

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print("Yes")
print("\n".join(str(i) for i in result[2:]))

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

queue = deque([1]) 
flag = [-1] * (N + 1)

while queue: 
    node = queue.popleft()
    children = graph[node] 
    for child in children:
        if flag[child] == -1:
            flag[child] = node
            queue.append(child)

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    edg[a].append(b)
    edg[b].append(a)
visited=[False for i in range(n)]
visited[0]=True
parent=[None for i in range(n)]
q=deque([0])
while len(q)>0:
    now=q.popleft()
    for i in edg[now]:
        if not visited[i]:
            q.append(i)
            visited[i]=True
            parent[i]=now
print("Yes")
for i in parent[1:]:
    print(i+1)

Solution (Python):
from collections import deque


N,M = (int(x) for x in input().split())
connected = [[] for _ in range(N+1)]
searched = [0] * (N+1)
signs = [0] * (N+1)
for i in range(M):
    A,B = (int(x) for x in input().split())
    connected[A].append(B)
    connected[B].append(A)
d = deque()
for edge in connected[1]:
    d.append(edge)
    signs[edge] = 1
    searched[edge] = 1
searched[1] = 1
while d:
    temp = d.popleft()
    for edge in connected[temp]:
        if searched[edge] == 0:
            d.append(edge)
            signs[edge] = temp
            searched[edge] = 1
    searched[temp] = 1
print('Yes')
for x in signs[2:]:
    print(x)

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)

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

if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    print('\n'.join(map(lambda x: str(x + 1), tokens[1:])))

Solution (Python):
from collections import deque
n, m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]

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


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

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
tokens[0] = N
q = deque([0])
while q:
    v = q.popleft()
    for nv in graph[v]:
        if tokens[nv] < 0:
            tokens[nv] = v
            q.append(nv)

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

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

lists = [False for i in range(N)]
lists[0] = True
a = N - 1
dicts = {i:[] for i in range(N)}
d = deque([0])

for i in range(M):
    tmpa, tmpb = map(lambda x: int(x) - 1, input().split()) 
    dicts[tmpa] += [tmpb]
    dicts[tmpb] += [tmpa]

print('Yes')
while a > 0:
    tmp = d.popleft()
    for i in dicts[tmp]:
        if not lists[i]:
            if tmp != 0:
                lists[i] = tmp
            else:
                lists[i] = -1
            d.append(i)
            a -= 1
    
for i in range(1, N):
    print(lists[i] + 1 if lists[i] != -1 else 1)

Solution (Python):
import queue

n,m = map(int,input().split())
hen = [[] for i in range(n)]
ans = [0 for i in range(n)]
a,b = 0,0



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

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

while q.empty() == False:
    head = q.get()
    for h in hen[head-1]:
        if h != 1 and ans[h-1] == 0:
            ans[h-1] = head
            q.put(h)

flag = 0

for i in range(n):
    if i != 0 and ans[i] == 0:
        flag = 1

if flag == 0:
    print('Yes')
    for i in range(n-1):
        print(ans[i+1])
else:
    print('No')

Solution (Python):
from collections import deque

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

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

q = deque()
q.append(1)

visited = set()
mark = [-1 for _ in range(n+1)]

while len(visited) < n:
    _from = q.popleft()
    if _from in visited:
        continue
    visited.add(_from)
    for i in adj[_from]:
        q.append(i)
        if mark[i] == -1:
            mark[i] = _from

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

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

Q = deque()
Q.append(1)

D = [-1]*(N+1)
D[0] = 0
D[1] = 0
while Q:
    v = Q.pop()
    for i in X[v]:
        if D[i] == -1:
            D[i] = v
            Q.appendleft(i)
if -1 in D:
    print('No')
else:
    print('Yes')
    print(*D[2:])

Solution (Python):
from queue import Queue

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

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

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


placas = [0] * (n)

def bfs(a):
    q = Queue(maxsize = n)
    placas[0] = 1
    q.put(a)
    while not q.empty():
        popado = q.get()
        for adj in grafo[popado-1]:
            if not placas[adj-1]:
                placas[adj-1] = popado
                q.put(adj)

    if placas.count(0) == 0:
        print("Yes")
        for x in placas[1::]:
            print(x)
    else:
        print("No")

bfs(1)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    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)
    queue=deque([0])
    visited=[False]*n
    visited[0]=True
    ans=[0]*n
    while queue:
        node=queue.popleft()
        for xnode in graph[node]:
            if visited[xnode]:continue
            ans[xnode]=node+1
            visited[xnode]=True
            queue.append(xnode)
    print("Yes")
    for a in ans[1:]:
        print(a)


if __name__=='__main__':
    main()

Solution (Python):
from collections import deque
 
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for i in range(M):
  A, B = map(int, input().split())
  G[A].append(B)
  G[B].append(A)
 
seen = [0 for _ in range(N+1)]
seen[1] = 1
shirube = [-1 for _ in range(N+1)]
 
stack = deque([1])
while stack:
  now = stack.popleft()
  
  for i in G[now]:
    if seen[i] == 0:
      seen[i] = 1
      stack.append(i)
      shirube[i] = now
      




for i in range(2,N+1):
  if seen[i] == 0:
    print('No')
    exit()
    
print('Yes')
for j in range(2,N+1):
  print(shirube[j])

Solution (Python):
n,m=list(map(int, input().split()))
root = [[] for _ in range(n)]
answer=[-1]*n
answer[0]=1
for i in range(m):
    c=list(map(int, input().split()))
    root[c[1]-1].append(c[0]-1)
    root[c[0]-1].append(c[1]-1)
count=1
queue=[0]

newqueue=[]
while(count<n and len(queue)!=0):
    for j in queue:
        for rootnum in root[j]:
            if(answer[rootnum]==-1):
                answer[rootnum]=j
                newqueue.append(rootnum)
                count+=1
    queue=newqueue
    
    newqueue=[]
if(count<n):
    print('No')
else:
    print('Yes')
    for l in range(n-1):
        print(answer[l+1]+1)

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

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

    net[a].append(b)
    net[b].append(a)

a = [-1] * (n+1)
d = deque()
d.append(1)
while d:
    u = d.popleft()
    for child in net[u]:
        if a[child] != -1:continue
        a[child] = u
        d.append(child)
print("Yes")
print(*a[2:], sep = " ")

Solution (Python):
from collections import deque

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

ans=[0]*(n+1)
ans[1]=1
check=[0]*(n+1)
check[1]=1
q = deque([1])

while q:
    now = q.popleft()
    for room in connection[now]:
        if check[room] == 0:
            ans[room]=now
            check[room]=1
            q.append(room)

if 0 in check[1:]:
    print('No')
    exit()
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Solution (Python):
import sys


from collections import deque, Counter, defaultdict



input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

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

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    visited[now]=1
    while len(q):
        now, p, d = q.popleft()
        dis[now] = d+1
        ans[now]=p+1
        
        for e in edge[now]:
            if visited[e]==1:
                continue
            q.append((e, now, dis[now]))
            visited[e]=1
        
        
        
        
bfs(0)
flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i])
else:
    print("No")

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    A = [[] for j in range(N + 1)]
    ans = [0] * (N + 1)

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

    q = collections.deque()
    v = set()

    q.append(1)
    v.add(1)
    while q:
        c = q.popleft()

        for n in A[c]:
            if n not in v:
                v.add(n)
                q.append(n)
                ans[n] = c

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys


from collections import deque, Counter, defaultdict




sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

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

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    while len(q):
        now, p, d = q.popleft()
        dis[now] = d+1
        visited[now]=1
        ans[now]=p+1
        
        for e in edge[now]:
            if visited[e]==1:
                continue
            if e==now:
                continue
            q.append((e, now, dis[now]))
            visited[e]=1
        
        
        
        
bfs(0)
flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i])
else:
    print("No")

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

from collections import deque

q = deque()
q.append(1) 

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

while len(q) != 0:
    now = q.popleft() 
    for to in adj[now]: 
        if dist[to] != -1: 
            continue
        dist[to] = dist[now] + 1
        q.append(to)
        res[to] = now

print('Yes')
for i in range(2, n + 1):
    print(res[i])

Solution (Python):
from collections import deque

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

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

stack=deque([0])
check = [-1]*n
check[0] = 0

while len(stack)>0:
    v = stack.popleft()
    for i in root[v]:
        if check[i] == -1:
            check[i]=v+1
            stack.append(i)
if -1 in check:
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(check[i])

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):
from collections import deque

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

seen = [0 for _ in range(N)]
seen[0] = 1
shirube = [-1 for _ in range(N-1)]

stack = deque([0])
while stack:
  now = stack.popleft()
  for i in G[now]:
    if seen[i] == 0:
      seen[i] = 1
      stack.append(i)
      shirube[i-1] = now
    
for i in range(N):
  if seen[i] == 0:
    print('No')
    exit()
    
print('Yes')
for j in range(N-1):
  print(shirube[j]+1)

Solution (Python):
import sys
from collections import deque
def main():
    input = sys.stdin.readline
    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] * (N + 1)
    ans[1] - 1
    cnt = 1
    q = deque([1])
    while q:
        v = q.popleft()
        for to in G[v]:
            if ans[to] > 0: continue
            ans[to] = v
            q.append(to)
            cnt += 1
    if cnt < N:
        print('No')
        return
    print('Yes')
    for i in range(2, N + 1):
        print(ans[i])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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

ans = [-1] * N
minDist = [10**18] * N
minDist[0] = 0
que = deque([0])

while que:
    now = que.popleft()
    dist = minDist[now] + 1
    for to in edges[now]:
        if minDist[to] > dist:
            minDist[to] = dist
            ans[to] = now
            que.append(to)

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

Solution (Python):

from collections import deque
N, M = map(int, input().split())
dd = {i:[] for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    dd[a-1].append(b-1)
    dd[b-1].append(a-1)
ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
queue = []
for i in range(len(dd[0])):
    queue.append([0, dd[0][i]])
queue = deque(queue)
while queue:
    q = queue.popleft()
    if visited[q[1]]:
        continue
    visited[q[1]] = True
    ans[q[1]] = q[0] + 1
    for v in dd[q[1]]:
        if not visited[v]:
            queue.append([q[1], v])
print("Yes")
print(*ans[1:], sep="\n")

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


graph = {node:set() for node in range(1,N+1)}

for _ in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].add(B)
    graph[B].add(A)

to_visit = set(range(2,N+1))
level = 0

posts = {}

while to_visit:
    
    if level == 0:
        levels = {0:{1:None}}
        current_level = {1}
    
    
    else:
        prevs = levels[level-1]
        levels[level] = {}
        for prev in prevs:
            for nbr in graph[prev]:
                if nbr in to_visit:
                    levels[level][nbr] = prev
                    posts[nbr] = prev
                    to_visit.remove(nbr) 
    
    level += 1

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

Solution (Python):
from collections import deque
def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while len(q) != 0:
        now = q.popleft()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.append(next)

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



if __name__=='__main__':
    main()

Solution (Python):
import queue
def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q =queue.Queue()
    q.put(0)
    ans = [-1] * n
    ans[0] = 0
    while not q.empty():
        now = q.get()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.put(next)
        
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

Solution (Python):
N, M = 6, 9
ARR = [
    [3, 4],
    [6, 1],
    [2, 4],
    [5, 3],
    [4, 6],
    [1, 5],
    [6, 2],
    [4, 5],
    [5, 6],
]

N, M = 4, 4
ARR = [
    [1, 2],
    [2, 3],
    [3, 4],
    [4, 2],
]

N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))

from collections import deque


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [-1 for i in range(n)]
    prevs = [-1 for i in range(n)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStates, prevs


nodes, nodeStates, prevs = prepare(N, M, ARR)


def bfs(nodes, nodeStates, prevs, n):
    q = deque()
    q.append({'prev': -1, 'to': 0})
    while len(q) > 0:
        first = q.popleft()
        currentNode = first['to']
        previousNode = first['prev']
        if nodeStates[currentNode] != -1:
            continue
        prevs[currentNode] = previousNode
        childNodes = nodes[currentNode]
        nodeStates[currentNode] = 1
        for childNode in childNodes:
            q.append({'prev': currentNode, 'to': childNode})

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


bfs(nodes, nodeStates, prevs, N)

Solution (Python):
def main():

    from collections import defaultdict
    from collections import deque
    N, M = map(int, input().split())

    dic = defaultdict(lambda :[])
    INF = 10 ** 6
    A = [INF] * N
    A[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        dic[a].append(b)
        dic[b].append(a)
        if a == 0 :
            A[b] = 0
        elif b == 0:
            A[a] = 0

    for i in range(1, N):
        l = len(dic[i])
        if l == 0:
            print('No')
            return
        elif l == 1:
            A[i] = dic[i][0]

    q = deque()
    for n in dic[0]:
        q.append((n, 1))
        A[n] = 0

    while len(q) > 0:
        n, d = q.popleft()
        for x in dic[n]:
            if A[x] == INF:
                A[x] = n
                q.append((x, d + 1))

    if any([v == 10 ** 6 for v in A]):
        print('No')
    else:
        print('Yes')
        for v in A[1:]:
            print(v + 1)


if __name__ == '__main__':
    main()

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

root = [set()for i in range(N+1)]
ans = [0 for i in range(N+1)]

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

task = deque([1])
itta = {1}

while len(task) > 0:
    now = task.popleft()
    additionanl = root[now] - itta 
    for i in additionanl: 
        ans[i] = now 
        itta.add(i)
    task.extend(list(additionanl)) 
print("Yes")
for i in range(2,N+1):
    print(ans[i])

Solution (Python):
N, M, *AB = map(int, open(0).read().split())

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

from collections import deque

queue = deque([1])
numsigns = [0] * (N + 1) 
numsigns[1] = 1

while queue:
    p = queue.popleft() 
    for nxt in graph[p]: 
        if not numsigns[nxt]: 
            numsigns[nxt] = p
            queue.append(nxt)

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