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

def bfs(s):
    ans = [-1] * (n + 1)
    ans[s] = 0
    q = deque()
    q.append(s)
    while q:
        p = q.popleft()
        for i in G[p]:
            if ans[i] == -1:
                ans[i] = p
                q.append(i)
    return ans

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)
a = bfs(1)
print("Yes")
for i in range(2, n + 1):
    print(a[i])

Solution (Python):
import sys
from collections import deque


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, read().split())
    al = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, read().split())
        al[a - 1].append(b - 1)
        al[b - 1].append(a - 1)
    ne = deque([(0, 0)])
    s = set()
    t = [(0, 10**6) for _ in range(n)]
    t[0] = (0, 0)
    while ne:
        p, f = ne.popleft()
        if p in s:
            continue
        s.add(p)
        if t[f][1] + 1 < t[p][1]:
            t[p] = (f, t[f][1] + 1)
        for ni in al[p]:
            ne.append((ni, p))
    print("Yes")
    for ti, _ in t[1:]:
        print(ti + 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, sys.stdin.readline().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, **kwargs):
	return np.fromiter(inputs(type, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, **kwargs)
	return data

from collections import deque
import numpy as np

N, M = inputs(int)
rooms_from = [[] for _ in range(N)]
for i in range(M):
	A, B = inputs(int)
	A -= 1
	B -= 1
	rooms_from[A].append(B)
	rooms_from[B].append(A)

INF = N

nexts = deque()
distance = np.full(N, INF, dtype=int)
direction = np.full(N, -1, dtype=int)

nexts.append((0, 0, -1))

while nexts:
	here, d, to = nexts.popleft()
	if distance[here] == INF:
		distance[here] = d
		direction[here] = to
		for room in rooms_from[here]:
			nexts.append((room, d + 1, here))

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

Solution (Python):
from collections import deque

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

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


dist = [-1] * (N + 1)
dist[1] = 0
ans = [-1] * (N + 1)
q = deque([1])
while q:
    u = q.popleft()
    for v in graph[u]:
        if dist[v] >= 0:
            continue
            
        dist[v] = dist[u] + 1
        ans[v] = u
        q.append(v)

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

Solution (Python):

from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                arrow[child] = v + 1
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

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

graph = [[] for _ in range(n)]
arrow = [0] * n

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))
    
dijkstra(n, graph, 0)

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

    node = [INF] * (N+1)
    ans = [-1] * (N+1)

    q = collections.deque()
    node[1] = 0
    q.append((0,1,-1))

    while q:
        d,v,f = q.popleft()
        node[v] = d
        ans[v] = f
        for u in root[v]:
            if node[u] <= d+1: continue
            node[u] = d+1
            q.append((d+1,u,v))

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

if __name__ == '__main__':
    main()

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

import heapq
def dijkstra_heap(s):
  
  dist=[float("inf")]*size_v
  used=[False]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w,i in graph[s]:
    heapq.heappush(hq_edge,(w,v,i))

  while hq_edge:
    min_w,min_v,i=heapq.heappop(hq_edge)
    
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    prev[min_v]=i
    for v,w,i2 in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,i2))

  return dist

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


size_v=N+1
prev=[None]*size_v
dist=dijkstra_heap(1)



print("Yes")
for i in range(2,N+1):
  prev_e=ablist[prev[i]]
  if i==prev_e[0]:
    print(prev_e[1])
  else:
    print(prev_e[0])

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

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

minv = [-1] * n
minv[0] = 0
length = [-1] * n
length[0] = 0


def dfs():
    global neighbor, length
    queue = deque([[0, 0]])
    while len(queue) > 0:
        v = queue.popleft()

        for nv in neighbor[v[0]]:
            if length[nv] == -1:
                length[nv] = v[1] + 1
                minv[nv] = v[0] + 1
                queue.append([nv, v[1] + 1])


dfs()

f = True
for i in minv:
    f &= i != -1

if not f:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(minv[i])

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

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

q=deque([0,])
ans=[None]*n
while q:
    cur=q.popleft()
    for nxt in to[cur]:
        if ans[nxt] is not None: 
            continue
        ans[nxt]=cur+1
        q.append(nxt)

if None in ans:
    print("No")
else:
    print("Yes")
    print(*ans[1:])

Solution (Python):
from collections import deque

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

infi = 10 ** 20
que = deque([(1, 0, -1)])
par = [-1] * (n + 1)
dist = [infi] * (n + 1)

while que:
    v, d, p = que.popleft()
    if dist[v] <= d:
        continue
    dist[v] = d
    par[v] = p
    for u in graph[v]:
        if par[u] == v:
            continue
        que.append((u, d + 1, v))

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

Solution (Python):
N,M = [int(x) for x in input().split()]
from collections import deque
l = [[] for i in range(N+1)]
d = deque()
for i in range(M):
    p,q = [int(x) for x in input().split()]
    l[p].append(q)
    l[q].append(p)
dist = [-1] * (N+1)
dist[1] = 0
d.append(1)
ans = [0]*(N+1)
while d:
    v = d.popleft()
    for i in l[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        ans[i] = v
        d.append(i)
if dist.count(-1) != 1:
    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())

path = [[] for i in range(N)]
indicator = [None] * N
indicator[0] = (0, 0)
for i in range(M):
    a, b = map(int, input().split())
    a-=1
    b-=1
    path[a].append(b)
    path[b].append(a)

def solve(N, path, indicator):
    visit = [False]*N
    visit[0] = True
    p = 0
    l = 0
    q = deque()
    q.append((0, 0))

    while q:
        (p, l) = q.popleft()
        for room in path[p]:
            if visit[room]:
                continue
            if indicator[room] is None:
                indicator[room] = (p, l+1)
                q.append((room, l+1))
                visit[room] = True
            elif indicator[room][1] > l+1:
                return []

L = solve(N, path, indicator)
if L == []:
    print("No")
else:
    print("Yes")
    for p, l in indicator[1:]:
        print(p+1)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
data = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    data[a-1].append(b)
    data[b-1].append(a)

que = deque([1])
ans = [0 for i in range(N)]
while True:
    cur = que.popleft()
    for item in data[cur-1]:
        if ans[item-1] == 0:
            que.append(item)
            ans[item-1] = cur
    if len(que) == 0: break

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

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 1000000007


INF = float("inf")
import heapq


ans = []
def dijkstra_heap(G, s, n):
    d = [INF] * n           
    used = [False] * n
    d[s] = 0
    used[s] = False

    edgelist = []
    for edge in G[s]:
        heapq.heappush(edgelist, [edge[0], edge[1], s])

    while len(edgelist) > 0:
        minedge = heapq.heappop(edgelist)       
        dist, v, pv = minedge[0], minedge[1], minedge[2]
        
        if used[v]:
            continue
        ans[v] = pv
        d[v] = dist
        used[v] = True

        
        for edge in G[v]:
            cost, nv = edge[0], edge[1]
            if used[nv]:
                continue
            heapq.heappush(edgelist, [d[v] + cost, nv, v])
    
    return d


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

    for _ in range(N):
        ans.append(-1)
    dijkstra_heap(G, 0, N)

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
A=[]
B=[]
road=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  road[a-1].append(b-1)
  road[b-1].append(a-1)
visit=[0]*N

q=deque([0])
ans=[0]*N
visit[0]=1
def bfs(q):
  while(q):
    v=q.popleft()
    
    for x in road[v]:
      if(visit[x]==0):
        q.append(x)
        
        visit[x]=1
        ans[x]=v+1
        
bfs(q)
print("Yes")
for i in range(N-1):
  print(ans[i+1])

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

from collections import deque
vis=[0]*(1+n)

q=deque([1])
while q:
    now=q.popleft()
    for next in G[now]:
        if vis[next]==0:
            vis[next]=now
            q.append(next)
print('Yes')
for i in range(2,n+1):
    print(vis[i])

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


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)

todo = deque([[0, 0]])
seen = [-1] * n
seen[0] = 0
while todo:
    node, parent = todo.popleft()

    for to in edges[node]:
        if seen[to] != -1:
            continue

        todo.append([to, node])
        seen[to] = node

print('Yes')
for parent in seen[1:]:
    print(parent+1)

Solution (Python):
import queue
n,m=map(int, input().split())
q = queue.Queue()
edgelist = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    edgelist[a-1].append(b-1)
    edgelist[b-1].append(a-1)
res = [-1]*n
visited = [-1]*n
for v in edgelist[0]:
    q.put([v,0])
res[0]=1
while not q.empty():
    x = q.get()
    
    if visited[x[0]]==1:
        continue
    else:
        visited[x[0]]=1
        res[x[0]]=x[1]+1
        for i in edgelist[x[0]]:
            if visited[i]==-1:
                q.put([i, x[0]])
print("Yes")
for i in range(1,n):
    print(res[i])

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m=MI()
tree=[[] for i in range(n)]
for i in range(m):
    a,b=MI()
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
q=deque([0])
ind=[-1 for i in range(n)]

ind[0]=0
while q:
    u=q.popleft()
    
    for j in tree[u]:
        if ind[j]<0:
            ind[j]=u
            q.append(j)

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

Solution (Python):
from collections import deque

n, m = map(int, input().split())
mark = [-1] * n
mark[0] = 0
graph = [[] for _ in range(n)]

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

que = deque([0])
while len(que) != 0:
    i = que.popleft()
    for j in graph[i]:
        if mark[j] == -1:
            mark[j] = i + 1
            que.append(j)

if -1 in mark:
    print('No')
else:
    print('Yes')
    for i in mark[1:]:
        print(i)

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

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

for i in range(m):
    routes[ab[i][0]-1].append(ab[i][1]-1)
    routes[ab[i][1]-1].append(ab[i][0]-1)


signs = [-1 for _ in range(n)]
seen = [False for _ in range(n)]
seen[0] = True

todo = deque()
todo.append(0)

while len(todo) > 0:
    looking = todo.popleft()
    for i in range(len(routes[looking])):
        if seen[routes[looking][i]] == False:
            seen[routes[looking][i]] = True
            todo.append(routes[looking][i])
            signs[routes[looking][i]] = looking

print("Yes")
for i in range(n-1):
    print(signs[i+1] + 1)

Solution (Python):
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline



def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


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

    g[0].append(1)

    ans = [-1] * (N + 1)
    que = deque()
    que.appendleft(0)

    while len(que) > 0:
        parent = que.pop()
        for child in g[parent]:
            if ans[child] == -1:
                ans[child] = parent
                que.appendleft(child)

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


if __name__ == "__main__":
    main()

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def bfs(graph, start=0):
    used = [False] * len(graph)
    used[start] = True
    q = [start]

    depth = [-1] * len(graph)
    post = [-1] * len(graph)

    depth[0] = 0

    for v in q:
        for w in graph[v]:
            if depth[w] != -1 and (depth[w] < depth[v] or depth[v] == -1):
                depth[v] = depth[w] + 1
                post[v] = w

            if not used[w]:
                used[w] = True
                q.append(w)

    return post


def main():
    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)

    post = bfs(graph)[1:]

    if -1 in post:
        print("No")
        return

    print("Yes")
    for i in post:
        print(i + 1)




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 print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):



import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect




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


class Dijkstra(object):
    """ ある特定の点からそのほかの頂点への最小距離を求める
    最短区間を実現するルートについては、prevに格納していく
    """
    def __init__(self, n:int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = {}

    def add_edge(self, v1: int, v2: int, w: float, undirected=False):
        self.adjacency_dict[v1][v2] = w
        if undirected:
            self.adjacency_dict[v2][v1] = w

    def run(self, start: int) -> (list, list):
        """ startから初めてそれ以外のノードへの最短距離をダイクストラ法で求める """
        
        dist = [float('inf')] * self.n
        prev = [None] * self.n
        heap_q = []

        dist[start] = 0

        
        heappush(heap_q, (0, start))

        while len(heap_q) > 0:
            
            d, l = heappop(heap_q)

            
            for node in self.adjacency_dict[l].keys():
                new_dist = dist[l] + self.adjacency_dict[l][node]
                if dist[node] > new_dist:
                    dist[node] = new_dist
                    heappush(heap_q, (new_dist, node))
                    prev[node] = l

        return dist, prev


g = Dijkstra(N)
for _ in range(M):
    v1, v2 = map(int, input().split())
    g.add_edge(v1 - 1, v2 - 1, 1, undirected=True)



dist, prev = g.run(start=0)


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

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import collections

N, M = rl()
edges = collections.defaultdict(list)
for i in range(M):
	a, b = rl()
	edges[a-1].append(b-1)
	edges[b-1].append(a-1)

queue = collections.deque()
queue.append(0)

visited = {}
while queue:
	n = queue.popleft()
	for e in edges[n]:
		if e in visited: continue
		visited[e] = n
		queue.append(e)

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

Solution (Python):
from collections import deque

N,M = map(int,input().split())
rol = [[] for _ in range(N)]
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  rol[a].append(b)
  rol[b].append(a)
  
q = deque()
q.append([0,0,0])
minr = [[10**10,0] for _ in range(N)]

while len(q)>0:
  el = q.popleft()
  room = el[0]
  step = el[1]
  oya = el[2]
  if minr[room][0] <= step:
    continue
  minr[room] = [step,oya]
  for el in rol[room]:
    q.append([el,step+1,room])
  
for i in range(1,N):
  if minr[i] == [10**10,0]:
    print("No")
    exit()
    
print("Yes")
for i in range(1,N):
  print(minr[i][1]+1)

Solution (Python):
import sys
import math  
import bisect  
import queue  


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


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

    prev = [-1 for _ in range(N)]
    prev[0] = 0
    que = queue.Queue()
    que.put(0)
    while not que.empty():
        cn = que.get()
        for e in edges[cn]:
            if prev[e] == -1:
                prev[e] = cn
                que.put(e)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n, e =MAP()  
G = [[]for i in range(n)]
for i in range(e):
    fr, to = MAP()
    G[fr-1].append([1,to -1])
    G[to-1].append([1,fr -1])

def djkstra(s,G):
    visited = [False]*n
    d = [INF]*n
    former = [INF]*n
    que = []
    heapq.heappush(que, (0,s,-1))
    while(len(que)>0):
        vs = heapq.heappop(que)
        distance = vs[0]
        vertex = vs[1]
        f = vs[2]
        if visited[vertex]:
            continue
        d[vertex] = distance
        visited[vertex] = True
        former[vertex] = f
        for Gs in G[vertex]:
            if d[Gs[1]] <= distance+Gs[0]:
                continue
            heapq.heappush(que,(distance+Gs[0], Gs[1], vertex))

    return d,former

d, former = djkstra(0,G)
print('Yes')
for i in range(n-1):
    print(former[i+1]+1)

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 = "Yes"
ansl = [0 for i in range(N+1)]
l = deque([1])
seen = [False for i in range(N+1)]
seen[1] = True
while len(l)>0:
  v = l.popleft()
  for i in G[v]:
    if seen[i] == False:
      seen[i] = True
      ansl[i] = v
      l.append(i)

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

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
連結無向グラフ
道標をおいた時に、全ての部屋からの最短路となる必要がある。
"""
n,m = map(int,readline().split())

g = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    g[x].append(y)
    g[y].append(x)
ans = [-1]*n

deq = deque([0])
while deq:
    fr = deq.popleft()
    for go in g[fr]:
        if ans[go] == -1:
            ans[go] = fr
            deq.append(go)
        

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

Solution (Python):
import queue

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

dic = {}

for ab in AB:
    ab[0]-=1
    ab[1]-=1
    if ab[0] in dic:
        dic[ab[0]].append(ab[1])
    else:
        dic[ab[0]] = [ab[1]]

    if ab[1] in dic:
        dic[ab[1]].append(ab[0])
    else:
        dic[ab[1]] = [ab[0]]



mm = [-1 for i in range(N)]
mm2 = [-1 for i in range(N)]
q = queue.Queue()
q.put(0)



while not(q.empty()):
    a = q.get()
    
    mm2[a] = 1

    for plc in dic[a]:
        if mm[plc] != -1:
            continue
        
        mm[plc] = a+1
        
        q.put(plc)

print("Yes")

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

Solution (Python):
from collections import deque
from typing import List, Union


class Dijkstra:
  """Dijkstra Algorithm returns the shortest path at graph.

  Args:
    edge (List[List[int]]): adjacent list
  """
  def __init__(self, edge):
    self.edge = edge
    n = len(edge)
    self.prev = list(range(n))
    self.dist = [n] * n

  def fit(self):
    self.dist[0] = 0
    queue = deque([0])
    while queue:
      vertex = queue.popleft()
      for destination in self.edge[vertex]:
        tmp = self.dist[vertex] + 1
        if self.dist[destination] > tmp:
          self.dist[destination] = tmp
          self.prev[destination] = vertex
          queue.append(destination)

  def get_path(self, vertex: int) -> List[int]:
    previous = self.prev[vertex]
    path = [vertex]
    while vertex != previous:
      vertex = previous
      previous = self.prev[vertex]
      path.append(vertex)
    return path[::-1]
  

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)
dijkstra = Dijkstra(edge)
dijkstra.fit()
print('Yes')
for previous in dijkstra.prev[1:]:
  print(previous + 1)

Solution (Python):
from collections import deque
import sys

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

D = [float('inf')] * n
P = [None] * n
D[0] = 0
qt = deque()
qt.append(0)
while qt:
    v = qt.popleft()
    for n_v in adj[v]:
        if D[n_v] > D[v] + 1:
            P[n_v] = v + 1
            D[n_v] = D[v] + 1
            qt.append(n_v)

for i in range(n):
    if D[i] == float('inf'):
        print('No')
        sys.exit(0)
print('Yes')        
print('\n'.join(list(map(str, P[1:]))))

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)
mark = [-1]*N
INF = float('inf')
dist = [-1] * N

mark[0] = 0
from collections import deque
q = deque()
q.append((0,0))

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

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

Solution (Python):
from collections import defaultdict
import heapq


def main():
    N, M = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    for _ in range(M):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    
    INF = N + 1
    prevs = [i for i in range(N)]
    dist = [INF for _ in range(N)]
    dist[0] = 0
    frontier = [(0, 0)]  
    while len(frontier) > 0:
        d, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if dist[next_node] > d + 1:
                dist[next_node] = d + 1
                prevs[next_node] = node
                frontier.append((d + 1, next_node))
    print('Yes')
    for i in range(1, N):
        print(prevs[i] + 1)


if __name__ == '__main__':
    main()