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 math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right

t=1
graph=defaultdict(lambda:[])
for _ in range(t):
    n,m=map(int,stdin.readline().split())
    for _ in range(m):
        a,b=map(int,stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    root=1
    ans=defaultdict(lambda:0)
    visited=defaultdict(lambda:False)
    q=deque()
    q.append(1)
    visited[1]=True
    count=0
    while(len(q)>0):
        temp=q.popleft()
        for i in graph[temp]:
            if(not visited[i]):
                visited[i]=True
                ans[i]=temp
                q.append(i)
                count+=1
    if(count==n-1):
        print("Yes")
        for i in range(2,n+1):
            print(ans[i])
    else:
        print("No")

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

from collections import deque

d = deque()
d.append(0)
ans = [-1]*n
while d:
    u = d.popleft()
    for v in to[u]:
        if ans[v]==-1:
            ans[v]=u
            d.append(v)

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

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

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

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

queue=[0]
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if ans[e] is not None: continue
            ans[e]=q
            queue_new.append(e)

    queue = queue_new

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

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    edge = [[] for _ in range(N)]
    for i in range(M):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    queue = deque([0])
    dist = [inf]*N
    dist[0] = 0
    ans = [-1]*N
    while(queue):
        v = queue.popleft()
        for to in edge[v]:
            if(dist[to]==inf):
                ans[to] = v+1
                queue.append(to)
                dist[to] = dist[v] + 1

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

    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
N, M = map(int, input().split())
e = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
Q = dq([1])
d = [10 ** 6] * (N + 1)
d[1] = 0
res = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  for y in e[x]:
    if d[y] > d[x] + 1:
      d[y] = d[x] + 1
      Q.append(y)
      res[y] = x
if min(res[2: ]):
  print("Yes")
  for r in res[2: ]: print(r)
else: print("No")

Solution (Python):
import sys
input=sys.stdin.readline
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def YesNo(x):print("Yes")if x==True else print("No")
n,m=NM()
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    c=1
    edge[a].append((b,c))
    edge[b].append((a,c))
pre=[-1]*(n+1)
from heapq import *
def dijkstra(s,n):
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            pre[v]=u
            heappush(pq,(d[v],v))
    return d
dijkstra(1,n)
if -1 in pre[2:]:
    print("No")
else:
    print("Yes")
    for i in pre[2:]:
        print(i)

Solution (Python):
from heapq import heappush, heappop

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

q = [(0, 0)]
dist = [float('inf')] * N
dist[0] = 0
ret = [-1] * N
ret[0] = 0

while q :
  cc, cur = heappop(q)
  for nex in vec[cur] :
    if cc + 1 < dist[nex] :
      dist[nex] = cc + 1
      ret[nex] = cur
      heappush(q, (cc + 1, nex))
      
if -1 in ret :
  print('No')
else :
  print('Yes')
  for i in range(1, N) :
    print(ret[i] + 1)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    
    for i in range(M):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
    import queue
    q=queue.Queue()
    q.put((0,-1))
    ans=[-1]*N
    
    while not q.empty():
        v,p=q.get()
        for nv in adj[v]:
            if nv!=p:
                if ans[nv]==-1:
                    q.put((nv,v))
                    ans[nv]=v
                    
    print("Yes")
    for i in range(1,N):
        print(ans[i]+1)
                

main()

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

Ans=[0]*n

Chk=[False]*n
Dist=[float("inf")]*n
Chk[0]=True
Dist[0]=0
S=collections.deque()
S.append(0)
while S:
  s=S.popleft()
  for g in edge[s]:
    if not Chk[g]:
      S.append(g)
      Chk[g]=True
      Ans[g]=s+1



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

Solution (Python):

import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

YES = "Yes"  


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    adj = [[] for _ in range(N)]
    for i in range(M):
        a = A[i]
        b = B[i]
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    visited = set()
    q = collections.deque([(0, 0)])  
    ans = [-1] * N
    while q:
        index, _from = q.popleft()
        if index in visited:
            continue
        visited.add(index)
        ans[index] = _from
        for adj_v in adj[index]:
            q.append((adj_v, index))

    if len(visited) != N:
        print("No")
        return
    print("Yes")
    for i, a in enumerate(ans):
        if i == 0:
            continue
        print(a + 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
input = sys.stdin.readline
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 -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
T = [-1]*n
que = deque()
que.append(0)
while que:
    v = que.popleft()
    for nv in G[v]:
        if T[nv] == -1:
            T[nv] = v+1
            que.append(nv)
print("Yes")
print(*T[1:], sep="\n")

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.prev = [None] * N
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.put(i)
					self.visit[i] = "Yes"


def main():
	N, M = getlist()
	G = Graph()
	for i in range(M):
		A, B = getlist()
		A -= 1; B -= 1
		G.add_edge(A, B)
		G.add_edge(B, A)

	BF = BFS(G, 0, N)
	print("Yes")
	prev = BF.prev
	for i in range(1, N):
		print(prev[i] + 1)

if __name__ == '__main__':
	main()

Solution (Python):
def examA():
    S = {0:"pon",1:"pon",2:"hon",3:"bon",4:"hon",5:"hon",6:"pon",7:"hon",8:"pon",9:"hon"}
    N = SI()
    ans = S[int(N[-1])]
    print(ans)
    return

def examB():
    K = I()
    S = SI()
    N = len(S)
    if N<=K:
        ans = S
    else:
        ans = S[:K]+"..."
    print(ans)
    return

def examC():
    A, B, H, M = LI()
    a = abs(H*30 - M*5.5)
    deg = min(360-a,a)*math.pi/180
    
    ans = (A**2 + B**2 - 2*A*B*math.cos(deg))**(0.5)
    print(ans)
    return

def examD():

    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)

    ans = [-1]*N

    def bfs(n, e, fordfs):
        
        W = [-1] * n
        
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = now
                    que.append(ne)
        return W
    ans = bfs(N,0,V)
    for a in ans:
        if a==-1:
            print("No")
            return
    print("Yes")
    for v in ans[1:]:
        print(v+1)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
from collections import deque

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

adj = [[] for _ in range(n + 1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

s = 1
dq = deque([s])
d = [-1] * (n + 1)
d[s] = 0
p = [-1] * (n + 1)

while dq:
    u = dq.popleft()
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            p[v] = u
            dq.append(v)

print("Yes")
print(*p[2:], sep="\n")

Solution (Python):
from heapq import heapify, heappush, heappop

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


class Graph:
    def __init__(self, n, e, wv=None, we=None):
        self.n = n
        self.e = list(map(tuple, e))
        self.wv = wv
        self.we = we

        self.adjlist = self.__get_adjlist()
        self.wedict = self.__get_wedict()

    def __get_adjlist(self):
        adjlist = [[] for _ in range(self.n)]

        for v0, v1 in self.e:
            adjlist[v0].append(v1)

        return adjlist

    def __get_wedict(self):
        return dict(zip(self.e, self.we))


def dijkstra(graph, s):
    INF = float('inf')

    d = [INF for _ in range(graph.n)]
    d[s] = 0
    prev = [None for _ in range(graph.n)]

    queue = []
    heappush(queue, (0, s))

    while queue:
        di, v = heappop(queue)
        for neighbor in graph.adjlist[v]:
            dtmp = d[v] + graph.wedict[(v, neighbor)]
            if dtmp < d[neighbor]:
                d[neighbor] = dtmp
                prev[neighbor] = v
                heappush(queue, (dtmp, neighbor))

    return d, prev


graph = Graph(n=n, e=e, we=[1] * (2 * m))

_, prev = dijkstra(graph, 0)

print('Yes')
for p in prev[1:]:
    print(p + 1)

Solution (Python):
from heapq import heappush, heappop, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict

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

def dijkstra(s, n, cost):
    d = [float("inf")] * n
    d[s] = 0
    que = [[0, s]]
    prev = {}
    heapify(que)
    while len(que) > 0:
        u_dist, u = heappop(que)
        
        for v in edges[u].keys():
            alt = d[u] + cost[u][v]
            if d[v] > alt:
                prev[v] = u
                d[v] = alt
                heappush(que, [alt, v])
    return d, prev

_, prev = dijkstra(0, n, edges)
ans = []
ans.append("Yes")
for i in range(1, n):
    ans.append(str(prev[i]+1))
print("\n".join(ans))

Solution (Python):
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)

    Direc = [-1] * N
    q = []
    heapify(q)
    heappush(q, (0, 0, 0))
    while q:
        dist, now, pre = heappop(q)
        if Direc[now] == -1:
            Direc[now] = pre + 1
            for ne in Edge[now]:
                if ne != pre: heappush(q, (dist + 1, ne, now))
    print("Yes")
    print("\n".join(map(str, Direc[1:])))

    return 0

if __name__ == "__main__":
    solve()

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

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    dist = [-1] * N
    par = [-1] * N
    dist[0] = 0
    dq = deque([0])
    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = d + 1
            par[u] = v + 1
            dq.append(u)

    print('Yes')
    print(*par[1:], sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):


import sys








from collections import deque                





















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a, b = mi_0()
        adj[a].append(b)
        adj[b].append(a)
    
    visited = [None] * n
    def bfs_queue_traverse(u):
        queue = deque([])
        queue.append((u, 0))
        while queue:
            current, dist = queue.popleft()
            if visited[current] is None:
                visited[current] = dist
                for v in adj[current]:
                    if visited[v] is None:
                        queue.append((v, dist+1))
    bfs_queue_traverse(0)
    
    print('Yes')
    for u in range(1, n):
        min_ind, minimum_dist = None, inf
        for v in adj[u]:
            if visited[v] < minimum_dist:
                min_ind, minimum_dist = v, visited[v]
        print(min_ind + 1)



if __name__ == "__main__":
    main()

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    for _ in range(M):
        a,b=map(int1,input().split())
        edge[a].append(b)
        edge[b].append(a)
    que=deque([0])
    d=[INF]*N
    d[0]=0
    ans=[0]*N
    while que:
        v=que.popleft()
        for nv in edge[v]:
            if d[nv]==INF:
                d[nv]=d[v]+1
                ans[nv]=v
                que.append(nv)
    print('Yes')
    for i in range(1,N):
        print(ans[i]+1)

if __name__ == '__main__':
    main()

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

for _ in range(m):
    ai,bi=map(int, input().split( ))
    ai-=1;bi-=1
    e[ai].append(bi);e[bi].append(ai)

d=[-1]*n
p=[i for i in range(n)]
d[0]=0

q=deque()

q.append(0)

while q:
    v=q.popleft()
    for u in e[v]:
        if d[u]<0:
           d[u]=d[v]+1
           p[u]=v
           q.append(u)
        elif d[u]>d[v]+1:
            d[u]=d[v]+1
            p[u]=v
            q.append(u)
print("Yes")
for i in range(1,n):
    print(p[i]+1)

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)


def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


def bfs(N, L):
    P = [0] * N
    Q = queue.Queue()
    Q.put(0)
    close = {0}
    while not Q.empty():
        v = Q.get()

        close.add(v)
        for w in L[v]:
            if w in close:
                continue
            close.add(w)
            P[w] = v
            Q.put(w)
    return P


def main():
    N, M = read_values()
    L = {i: set() for i in range(N)} 
    
    for _ in range(M):
        i, j = read_index()
        L[i].add(j)
        L[j].add(i)

    P = bfs(N, L)

    if -1 in P[1:]:
        print("No")
        return
    
    print("Yes")
    
    for p in P[1:]:
        print(p + 1)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque

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

    queue = deque([0])
    visit = [-1] * N
    visit[0] = 0

    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = now
    if -1 in visit:
        print('No')
    else:
        print('Yes')
        [print(v+1) for v in visit[1:]]

if __name__ == "__main__":
    main()

Solution (Python):

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

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

for i in range(M):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append(B)
    lis[B].append(A)

from collections import deque

p = [i for i in range(N)]
d = [float("inf")] * N
d[0] = 0
q = deque([0])

while len(q) > 0:

    now = q.popleft()

    for nex in lis[now]:

        if d[nex] > d[now] + 1:
            d[nex] = d[now]
            p[nex] = now
            q.append(nex)

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

Solution (Python):
from collections import deque


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

graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


visited = [False] * n
ans = [0] * n
s = 0
visited[s] = True
q = deque([s])
while q:
    v = q.popleft()
    for nxt_v in graph[v]:
        if visited[nxt_v]:
            continue
        else:
            visited[nxt_v] = True
            ans[nxt_v] = v + 1
            q.append(nxt_v)
print("Yes")
for i in range(1, n):
    print(ans[i])

Solution (Python):
from collections import deque

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

d = deque([[1, 0]])
par = [0] * (N+1)
while d:
  node, p = d.popleft()
  children = graph[node]
  for child in children:
    if child == p or par[child] != 0:
      continue
    par[child] = node
    d.append([child, node])

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = [[] for _ in range(N)]
for _ in range(M):
	A, B = MAP()
	graph[A-1].append(B-1)
	graph[B-1].append(A-1)

q = deque()
q.append(0)
ans = [None]*N
ans[0] = 0
while q:
	n = q.popleft()
	for node in graph[n]:
		if ans[node] == None:
			q.append(node)
			ans[node] = n
print("Yes")
for i in range(1, N):
	print(ans[i]+1)

Solution (Python):
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
c=[[] for i in range(N)]
for i,j in AB:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
from collections import deque
def bfs(c,N,s):
    v=[0]*N
    v[s]=1
    pre=[-1]*N
    q=deque([s])
    while q:
        i=q.popleft()
        for j in c[i]:
            if v[j]==0:
                v[j]=1
                pre[j]=i
                q.append(j)
    return pre
p=bfs(c,N,0)
print('Yes',*[x+1 for x in p[1:]],sep='\n')

Solution (Python):
def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    C = [-1] * N
    C[0] = 0
    cur = set([0])
    while cur:
        nxt = set()
        for c in cur:
            for e in E[c]:
                if C[e] != -1:
                    continue
                C[e] = c
                nxt.add(e)
        cur = nxt
    print('Yes')
    print('\n'.join(str(i + 1) for i in C[1:]))
main()

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


q = [0]
par = [-1]*N
par[0] = 0
while q:
    qq = []
    for p in q:
        for np in graph[p]:
            if par[np] == -1:
                par[np] = p+1
                qq.append(np)
    q = qq

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

Solution (Python):


import sys
sys.setrecursionlimit(300000)

YES = "Yes"  

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(M):
        conns[A[i] - 1].append(B[i] - 1)
        conns[B[i] - 1].append(A[i] - 1)

    q = [0]
    ret = [-1] * N
    visited = [False] * N
    visited[0] = True
    while True:
        nex = []
        for i in q:
            for con in conns[i]:
                if not visited[con]:
                    nex.append(con)
                    ret[con] = i
                    visited[con] = True
        if len(nex) == 0:
            break
        q = nex
    for r in ret[1:]:
        if r < 0:
            print('No')
            return
    print('Yes')
    for r in ret[1:]:
        print(r + 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):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for a,b in AB:
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

d = dist_bfs(N,E,0)

ans = [None]*N

for i in range(1,N):
    di = d[i]
    for j in E[i]:
        if d[j] == di-1:
            ans[i] = j+1
            break
print("Yes")
for out in ans[1:]:
    print(out)

Solution (Python):
n, m = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)
ans = [-2] * n
ans[0] = -1
q = [0]
for i in q:
    for j in e[i]:
        if ans[j] == -2:
            q.append(j)
            ans[j] = i
if - 2 in ans:
    print("No")
else:
    print("Yes")
    for i in ans[1:]:
        print(i+1)

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

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

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

from collections import deque

vi = 0  
INF = float('inf')

Q = deque([vi])

checked_list = [False]*N
checked_list[vi]=True
parent_list = [-1]*N


while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            parent_list[v1] = v

print("Yes")

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

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

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

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

USE=[-1]*(N+1)
USE[0]=0
USE[1]=0

from collections import deque
Q=deque()
Q.append(1)
while Q:
    x=Q.pop()
    for to in E[x]:
        if USE[to]==-1:
            USE[to]=x
            Q.appendleft(to)

if -1 in USE:
    print("No")
else:
    print("Yes")
    print(*USE[2:])

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

X = [[] for i in range(N*3)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

Q = deque([0])
ANS = [-1] * N
ANS[0] = -2
while Q:
    x = Q.popleft()
    for c in X[x]:
        if ANS[c] == -1:
            ANS[c] = x
            Q.append(c)
print("Yes")
print("\n".join(map(str, [a + 1 for a in ANS[1:]])))

Solution (Python):
n,m = map(int,input().split())
peer = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
now = [0]
seen = [0 for _ in range(n)]
ans = [0 for _ in range(n)]
seen[0] = 1
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        now.append(y)
        ans[y] = x
ans = ans[1:]
print('Yes')
for x in ans:
  print(x+1)