Problem:
 Score: 400 points    Problem Statement  There is a cave.  The cave has N rooms and M passages. The rooms are numbered 1 to N , and the passages are numbered 1 to M . Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.  It is dark in the cave, so we have decided to place a signpost in each room except Room 1 . The signpost in each room will point to one of the rooms directly connected to that room with a passage.  Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1 .   If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.   Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.      Constraints   All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 2 \times 10^5  1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)  A_i \neq B_i\ (1 \leq i \leq M)  One can travel between any two rooms by traversing passages.         Input  Input is given from Standard Input in the following format:  N  M  A_1  B_1  :  A_M  B_M       Output  If there is no way to place signposts satisfying the objective, print No .  Otherwise, print N lines. The first line should contain Yes , and the i -th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i .        Sample Input 1 4 4
1 2
2 3
3 4
4 2      Sample Output 1 Yes
1
2
2  If we place the signposts as described in the sample output, the following happens:   Starting in Room 2 , you will reach Room 1 after traversing one passage: (2) \to 1 . This is the minimum number of passages possible.  Starting in Room 3 , you will reach Room 1 after traversing two passages: (3) \to 2 \to 1 . This is the minimum number of passages possible.  Starting in Room 4 , you will reach Room 1 after traversing two passages: (4) \to 2 \to 1 . This is the minimum number of passages possible.   Thus, the objective is satisfied.       Sample Input 2 6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6      Sample Output 2 Yes
6
5
5
1
1  If there are multiple solutions, any of them will be accepted.

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

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

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

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

if 0 in ans[2:]:
    print('No')
    exit()
print('Yes')
print('\n'.join(map(str, ans[2:])))

Solution (Python):
from collections import deque

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

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

ans=[None]*n
ans[0]=0


queue = deque([1])
while queue:
    v = queue.popleft()
    for i in path[v-1]:
        if ans[i-1] is None:
            ans[i-1] = v
            queue.append(i)

if None in ans:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(ans[i])

Solution (Python):

import sys

N, M, *AB = map(int, sys.stdin.buffer.read().split())

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

for i in range(M):
  A,B = AB[2*i:2*i+2]
  dict_path[A].append(B)
  dict_path[B].append(A)

list_bfs = [1]
list_flg = [0 for _ in range(N+1)]
list_flg[1] = 1

while len(list_bfs)>0:
  list_tmp = []
  for i in list_bfs:
    for j in dict_path[i]:
      if list_flg[j]==0:
        list_tmp.append(j)
        list_flg[j] = i
  list_bfs = list_tmp

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

Solution (Python):
from collections import deque

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

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

queue = deque([1])
while queue:
    now = queue.popleft()
    for i in S[now]:
        if ans[i] == 0:
            ans[i] = now
            queue.append(i)
            
if 0 in ans[2:]:
    print('No')
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

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

for _ in range(m):
  a,b = map(int, input().split())
  a,b = a-1, b-1
  g[a].append(b)
  g[b].append(a)
stack = deque([0])
dist = [-1]*n
dist[0] = 0

while stack:
  v = stack.popleft()
  for nv in g[v]:
    if dist[nv] == -1:
      dist[nv] = v+1
      stack.append(nv)

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

Solution (Python):
import sys
from operator import itemgetter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n, m = _ia()
    edge = [[] for _ in range(n)]
    for _ in range(m):
        ai, bi = map(lambda x: x-1, _ia())
        edge[ai].append(bi)
        edge[bi].append(ai)

    now = []
    nxt = [0]
    idx = {0: 0}
    while len(idx) < n:
        now = nxt
        nxt = []
        for ai in now:
            for bi in edge[ai]:
                if idx.get(bi, -1) >= 0:
                    continue
                idx[bi] = ai
                nxt.append(bi)

    print("Yes")
    return "\n".join(map(str, [v+1 for k, v in sorted(idx.items(), key=itemgetter(0)) if k > 0]))


if __name__ == "__main__":
    print(main())

Solution (Python):
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())
    
    l = [[] for _ in range(n+1)]
    for i, j in zip(*[iter(ab)] * 2):
        l[i].append(j)
        l[j].append(i)

    ll = [0 for _ in range(n+1)]
    vis = [0 for _ in range(n+1)]
    que = deque()
    que.append(1)
    vis[1] = 1
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if vis[i]:
                continue
            vis[i] = 1
            ll[i] = now
            que.append(i)
    if all(vis[1:]):
        print("Yes")
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print("No")



if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N, M = map(int, input().split())
AB = [[] for _ in range(N+1)]
for i in range(M):
    A_tmp , B_tmp = map(int, input().split())
    AB[A_tmp].append(B_tmp)
    AB[B_tmp].append(A_tmp)

ans = [0]*(N+1)
visited = [False] * (N + 1)

q = deque()
q.append((1, -1))
while len(q) > 0:
    node, past = q.popleft()
    if visited[node]:
      continue
    ans[node] = past
    visited[node] = True
    for t in AB[node]:
        if visited[t]:
            continue
        q.append((t, node))
print("Yes")
for i in range(2, N+1):
    print(ans[i])

Solution (Python):
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())
    r = range(n+1)
    l = [[] for _ in r]
    for i, j in zip(*[iter(ab)] * 2):
        l[i].append(j)
        l[j].append(i)

    ll = [0 for _ in r]
    vis = [False for _ in r]
    que = deque()
    que.append(1)
    vis[1] = True
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if vis[i]:
                continue
            vis[i] = True
            ll[i] = now
            que.append(i)
    if all(vis[1:]):
        print("Yes")
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print("No")



if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
A, B = [], []
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    graph[a].append(b)
    graph[b].append(a)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = set()
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.update(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = set()
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.add(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    r.append(R(i+1, set(graph[i+1])))

l = r.search()
print("Yes")
for room in l:
    print(room)

Solution (Python):


from collections import deque

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N, M = MII()
    l = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = MII()
        l[a].append(b)
        l[b].append(a)

    ll = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]

    que = deque()
    que.append(1)
    visited[1] = True
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if not visited[i]:
                visited[i] = True
                ll[i] = now
                que.append(i)


    if all(visited[1:]):
        print('Yes')
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print('No')

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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


for i in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
 
ans = [0]*(n+1)
 
stk = deque([1])
 

while stk:
    v = stk.pop()
    for s in G[v]:
        
        if ans[s] == 0:
            ans[s] = v
            stk.appendleft(s)
ans = ans[2:]
 
if 0 in ans:
    print("No")
else:
    print("Yes")
    for i in ans:
        print(i)

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
g = [[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
p = [0]*n
from collections import deque
q = deque([0])

while q:
  v = q.popleft()
  for c in g[v]:
    if p[c]<1:p[c]=v+1;q.append(c)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')

Solution (Python):
import collections
n,m = [int(x) for x in input().split()]
ab = [[] for _ in range(n)]
for _ in range(m):
    u,v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    ab[u].append(v)
    ab[v].append(u)

D = collections.deque([0])
visited = [False]*n
visited[0] = True
ans = [0] * n

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

Solution (Python):
from collections import deque

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

q = deque([0])
b = [0] * n
while q:
    x = q.popleft()
    for i in g[x]:
        if b[i] != 0:
            continue
        b[i] = x + 1
        q.append(i)

if 0 in b[1:]:
    print("No")
else:
    print("Yes")
    print(*b[1:], sep="\n")

Solution (Python):
from collections import deque
def main():
  n,m=map(int,input().split())
  e=[[] for _ in range(n)]
  for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    e[a].append(b)
    e[b].append(a)
  ans=[-1]*n
  dq=deque([0])
  while dq:
    g=dq.popleft()
    for v in e[g]:
      if ans[v]==-1:
        ans[v]=g+1
        dq.append(v)
  ans[0]="Yes"
  print(*ans)
main()

Solution (Python):
n, m = map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
L=[set() for i in range(n)]
for i in range(m):
    a, b =  map(int, input().split())
    L[a-1] |= {b}
    L[b-1] |= {a}
Y = {range(1, n+1)}
Z = [0]*(n-1) 
S = {1}
def f(X):
    global S, Z
    X_next = set()
    for j in X:
        R = L[j-1]-S
        S |= L[j-1]
        X_next |= R
        for k in R:
            Z[k-2] += j
    if X_next == set():
        print("Yes")
        print('\n'.join(map(str, Z)))
    else:
        return  f(X_next)
f({1})

Solution (Python):
import collections

if __name__ == '__main__':
    n, m = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(m)]

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

    for i in l:
        ways[i[0]].append(i[1])
        ways[i[1]].append(i[0])

    

    q = collections.deque()

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

    q.append(1)

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

    if -1 in ans:
        print("No")
    else:
        print("Yes")
        for i in range(1,n):
            print(ans[i])

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

from collections import defaultdict, deque

G = defaultdict(set)


results = [-1]*N
flags   = [False]*N

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

seen    = [False]*N
partner = [0]*N

q = deque([0])
seen[0] = True


while q:
    now = q.popleft()
    for i in G[now]:
        if seen[i]:
            continue
        seen[i] = True
        partner[i] = now
        q.append(i)

if len(seen) != N:
    print('No')
else:
    print('Yes')
    for i in partner[1:]:
        print(i+1)

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

q = deque()
q.append(0)
ans = [-1]*n
while q:
    x = q.popleft()
    for child in edges[x]:
        if ans[child] == -1:
            ans[child] = x+1
            q.append(child)
        
        
print("Yes")
for i in range(1, n):
    print(ans[i])

Solution (Python):
from collections import deque

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

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

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

q = deque()

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

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

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

Solution (Python):
from queue import Queue


n, m = list(map(int, input().split()))
g = {i: [] for i in range(1, n + 1)}
for i in range(m):
    ai, bi = list(map(int, input().split()))
    if min(ai, bi) == 1:
        g[1].append(max(ai, bi))
    else:
        g[ai].append(bi)
        g[bi].append(ai)

q = Queue()
q.put(1)
m = {}
while not q.empty():
    x = q.get()
    for t in g[x]:
        if t not in m:
            m[t] = x
            q.put(t)

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

Solution (Python):
import sys 
from collections import defaultdict 
 
class Graph: 
 
    def __init__(self): 
        global n
        self.graph = defaultdict(list) 
        self.parent = [None for i in range(0,n+1)]
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
    def BFS(self, s): 
        visited = [False] * (len(self.graph)+1) 
        queue = [] 
        queue.append(s)   
        while queue: 
            s = queue.pop(0) 
            
            
            for i in self.graph[s]: 
                
                if visited[i] == False: 
                    self.parent[i]=s
                    queue.append(i) 
                    visited[i]=True
            

[n,m]=[int(i) for i in input().split(' ')]
g = Graph() 
for i in range(0,m):
    [a,b]=[int(i) for i in input().split(' ')]
    g.addEdge(a,b)
    g.addEdge(b,a)

g.BFS(1)
flag=0
for i in range(2,n+1):
    if g.parent[i]==None:
        print('No')
        flag=1
        break

if flag==0:
    print('Yes')
    for i in range(2,n+1):
        print(g.parent[i])
        9

Solution (Python):
from collections import deque
q = deque([0])
Dequeue = lambda: q.popleft()
Enqueue = lambda x: q.append(x)

n, m = map(int, input().split())
g = [[] for _ in [0]*n]

for _ in [0]*m:
    a, b = map(int, input().split())
    a -= 1;b -= 1
    g[a] += [b]
    g[b] += [a]

p = [0]*n
while q:
    v = Dequeue()
    for c in g[v]:
        if p[c] < 1:
            p[c] = v+1
            Enqueue(c)
if 0 in p:
    print("No")
else:
    print("Yes")
    for i in p[1:]:
        print(i)

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):
from collections import deque
n, m = map(int, input().split())
rinsetsu_lis = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    rinsetsu_lis[a].append(b)
    rinsetsu_lis[b].append(a)
l= deque([1])
unvisit= [True]*(n+1)
unvisit[1] = False
anslis = [0]*(n+1)
while len(l) != 0:
    now = l.popleft()
    for r in rinsetsu_lis[now]:
        if unvisit[r]:
            unvisit[r] = False
            l.append(r)
            anslis[r] = now
print("Yes")
for i in range(2,len(anslis)):
    print(anslis[i])

Solution (Python):
(r, p)=[int(n) for n in input().split()]
route_list=[[] for i in range(r)]
for i in range(p):
  (x, y)=[int(n)-1 for n in input().split()]
  route_list[x].append(y)
  route_list[y].append(x)

upstair=[0]
ans=[-1]*r
while upstair:
  tmp=[]
  for i in upstair:
    for j in route_list[i]:
      if ans[j] == -1:
        ans[j] = i + 1
        tmp.append(j)
  upstair=tmp

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

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

N, M = map(int, readline().split())
ans = [0] * (N+1)
graph = [[] for _ in range(N+1)]

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

root = 1
q = [root]
checked = [0] * (N + 1)
checked[root] = 1

while q:
    x = q.pop(0)
    for y in graph[x]:
        if checked[y]:
            continue
        ans[y] = x
        checked[y] = 1
        q.append(y)

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

Solution (Python):






"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[Tuple[int, int]], n: int) -> List[int]:
    passages = defaultdict(set)
    for a, b in values:
        passages[a].add(b)
        passages[b].add(a)
    if len(passages) < n:
        return []
    to_visit = [(0, 1, 0)]
    visited = set()
    
    signs = [1] * (n + 1)
    while to_visit:
        min_dist, cur, prev = heapq.heappop(to_visit)
        if cur in visited:
            continue
        signs[cur] = prev
        for neighbour in passages[cur]:
            if neighbour in visited:
                continue
            heapq.heappush(to_visit, (min_dist + 1, neighbour, cur))
        visited.add(cur)
    LOG.debug((visited))
    LOG.debug((signs))
    if len(visited) < n:
        return []
    return signs[2:]


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    N, M = map(int, stdin.readline().split())
    if M < N - 1:
        print("No", file=stdout)
        return
    values = []
    for _ in range(M):
        a, b = map(int, stdin.readline().split())
        values.append((a, b))
    result = solve(values, N)
    if not result:
        print("No", file=stdout)
    else:
        print("Yes", file=stdout)
        print("\n".join(map(str, result)), file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 
    
    


BUFSIZE = 8192


class FastIO(IOBase):
    
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None

if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Solution (Python):
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)
from heapq import *
pq=[]
heapify(pq)
heappush(pq,(0,0))
vis=[0]*n
inf=float('inf')
dist=[inf]*n
dist[0]=0
par=[-1]*n
while pq:
    cur=heappop(pq)
    u=cur[1]
    if vis[u]==1:continue
    vis[u]=1
    for v in g[u]:
        if vis[v]==1:continue
        dist[v]=min(dist[v],1+dist[u])
        if dist[u]+1==dist[v]:
            par[v]=u
        heappush(pq,(dist[v],v))
flag=True
for i in range(1,n):
    if par[i]==-1:
        print('No')
        exit()
print('Yes')
for i in range(1,n):
    print(1+par[i])

Solution (Python):

import sys
import collections

sys.setrecursionlimit(10 ** 7)


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


A = list(tuple(map(int, input().rstrip().split())) for _ in range(M))

array = [[] for _ in range(N)]
for x, y in A:
    array[x - 1].append(y - 1)
    array[y - 1].append(x - 1)

before = [None] * N
before[0] = -1
q = collections.deque([0])

while len(q):
    node = q.popleft()
    for nxt in array[node]:
        if before[nxt] is not None:
            continue
        q.append(nxt)
        before[nxt] = node

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

Solution (Python):
import queue
N,M = map(int, input().split())
r = [[] for _ in range(N)]
for i in range(M):
    A,B=map(int, input().split())
    r[A-1].append(B)
    r[B-1].append(A)
ans =[0]*(N+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    qg = q.get()
    for ri in r[qg-1]:
        if ans[ri] == 0:
            ans[ri] = qg
            q.put(ri)
print("Yes")
for i in range(2,N+1):
    print(ans[i])

Solution (Python):
n, m = map(int, input().split())
edge_list = [[] for i in range(n)]
prev_list = [1]
ans = [0] * n

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

while len(prev_list) > 0:
    next = []
    for prev in prev_list:
        for edge in edge_list[prev - 1]:
            if ans[edge - 1] == 0:
                next.append(edge)
                ans[edge - 1] = prev
    prev_list = next

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

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):
n,m=map(int,input().split())
r=[[] for x in range(n)]
for c in range(m):
    a,b=map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
s=[-1]*n
u=[0]
v=[]
k=1
while k<n:
    for d in u:
        for e in r[d]:
            if s[e]==-1:
                s[e]=d
                k+=1
                v.append(e)
    u=v
print('Yes')
for c in range(n-1):
    print(s[c+1]+1)

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

V = [[] for _ in range(N)]

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

from collections import deque

q = deque([0])

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

while q:
    v = q.popleft()
    for nv in V[v]:
        if ans[nv] == -1:
            ans[nv] = v + 1
            q.append(nv)

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

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
g=[[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
p=[0]*n
from collections import*
q=deque([0])
while q:
  v=q.popleft()
  for c in g[v]:
    if p[c]<1: p[c]=v+1; q.append(c)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')

Solution (Python):
from collections import deque
N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
ans = [0] * (N+1)
for i in range(M):
    f, t = map(int, input().split())
    graph[f].append(t)
    graph[t].append(f)

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

if 0 in checked:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(ans[i])

Solution (Python):
n,m = map(int, input().split())
d = {}
for i in range(m):
  a,b = map(int, input().split())
  if a in d:
    l = d[a]
    l.append(b)
    d[a] = l
  else:
    d[a] = [b]
  if b in d:
    l = d[b]
    l.append(a)
    d[b] = l
  else:
    d[b] = [a]
dpth = {}
dpth[1] = 0
l = [1]
ans = [0]*(n-1)
while(len(l)>0):
  l_ = []
  for i in l:
    dpth_ = dpth[i]
    for j in d[i]:
      if j not in dpth:
        ans[j-2] = i
        dpth[j] = dpth_+1
        l_.append(j)
  l = l_
print("Yes")
for i in ans:
  print(i)

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

adj = [[] for i in range(N)]
signs = [-1 for i in range(N)]


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

queue = deque([0])

while len(queue) > 0:
  cur = queue.popleft()
  for i in adj[cur]:
    if signs[i] == -1:
      queue.append(i)
      signs[i] = cur
      

if all([sign != -1 for sign in signs[1:]]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")

Solution (Python):
from collections import deque
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n,m=nii()

tree=[[] for i in range(n)]
for i in range(m):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

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

dq=deque()
dq.append(0)
while dq:
  x=dq.popleft()
  for i in tree[x]:
    if ans[i]==-1:
      ans[i]=x
      dq.append(i)

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

Solution (Python):
from collections import deque

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

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

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

while q:
  v = q.popleft()
  for nv in G[v]:
    if dist[nv] == -1:
      dist[nv] = v+1
      q.append(nv)

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

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



def main():
    N, M = [int(i) for i in input().strip().split()]
    graph = [[] for _ in range(N)]
    sign = [0] * N
    for _ in range(M):
        a, b = [int(i) for i in input().strip().split()]
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    candidates = deque([0])
    visited = [False] * N
    visited[0] = True
    while len(candidates) > 0:
        v = candidates.popleft()
        for i in graph[v]:
            if visited[i]:
                continue
            visited[i] = True
            sign[i] = v
            candidates.append(i)
    print("Yes")
    for i in sign[1:]:
        print(i+1)

    return


if __name__ == "__main__":
    main()