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):
N, M = map(int, input().split())
from collections import defaultdict
AB_dict = defaultdict(list)
dist_list = [-1] * N
dist_list[0] = 0
pre_list = []
for _ in range(M):
    a, b = [int(i)-1 for i in input().split()]
    AB_dict[a].append(b)
    AB_dict[b].append(a)
    if a == 0:
        pre_list.append(b)
        dist_list[b] = 0
    if b == 0:
        pre_list.append(a)
        dist_list[a] = 0


    
while True:
    tmp = []
    
    for p in pre_list:
        
        for node in AB_dict[p]:
            
            if dist_list[node] == -1:
                
                dist_list[node] = p
                tmp.append(node)
    if tmp == []:
        break
    pre_list = tmp
    
if -1 in dist_list:
    print('No')
    exit()
    
print('Yes')
for dist in dist_list[1:]:
    print(dist+1)

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read


sys.setrecursionlimit(10**7)





from collections import deque
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    queue = deque([])
    seen[1] = True
    queue.append((1, 0))
    mark = [0] * (N+1)

    while queue:
        current, prev = queue.popleft()
        for next in to[current]:
            if not seen[next]:
                queue.append((next, current))
                mark[next] = current
                seen[next] = True

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

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

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

ans = [-1 for _ in range(n+1)]
ans[0]=1
ans[1]=1
check_list = [1]

while check_list:
  n = check_list.pop(0)
  for g_i in G[n]:
    if ans[g_i]==-1:
      ans[g_i]=n
      check_list.append(g_i)

flg = 'Yes'
if -1 in ans:
  flg = 'No'

if flg=='Yes':
  print('Yes')
  for ans_i in ans[2:]:
    print(ans_i)
else:
  print('No')

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

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

ans_list = [-1] * N

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

while queue:
    qi = queue.pop(0)
    
    for gi in g[qi]:
        if seen[gi] == False:
            queue.append(gi)
            if ans_list[gi] == -1:
                ans_list[gi] = qi
                seen[gi] = True

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

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

def main():
    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 ans[i] != 0:
                continue
            ans[i] = x
            que.append(i)
    for a in ans[2:]:
        if a == 0:
            print('No')
            break
    else:
        print('Yes')
        print('\n'.join(map(str, ans[2:])))

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)

def main():
    n,m=map(int,input().split())
    graph=[[] for _ in range(n)]
    seen=[False]*n

    for _ in range(m):
        a,b=map(int,input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=[-1]*n
    q=deque([0])
    seen[0]=True
    while len(q):
        now=q.popleft()
        for i in graph[now]:
            if seen[i]:
                continue
            seen[i]=True
            q.append(i)
            if ans[i]==-1:
                ans[i]=now
    print("Yes")
    for i in range(1,n):
        print(ans[i]+1)

if __name__=="__main__":
    main()

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

ans = [-1]*n
ans[0] = 0
from collections import deque
q = deque([0])
while q:
    u = q.popleft()
    for v in d[u]:
        if ans[v]==-1:
            ans[v] = u
            q.append(v)
print('Yes')
for i in ans[1:]:
    print(i+1)

Solution (Python):
import collections
def solve(a, b, ab_list):

    route = {}

    for a, b in ab_list:
        if a not in route:
            route[a] = []
        if b not in route:
            route[b] = []

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

    deque = collections.deque()
    deque.extend(route[1])
    route_memo = {i:1 for i in route[1]}
    while len(deque) > 0:
        room = deque.popleft()
        for i in route[room]:
            if i != 1 and i not in route_memo:
                route_memo[i] = room
                deque.append(i)

    if len(route_memo.keys()) == n-1:
        print("Yes")
        tmp = sorted(route_memo.items())
        for i in tmp:
            print(i[1])
    else:
        print("No")

if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    ab_list = [[int(i) for i in input().split()] for j in range(m)]
    solve(n, m, ab_list)

Solution (Python):
import queue

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

parent = [-1] * (n-1)
visit = ["yet"]*(n)
visit[0] = "done"
q = queue.Queue()
q.put(1)
while not q.empty():
    temp = q.get()
    for i in routs[temp]:
        if visit[i-1] == "yet":
            q.put(i)
            if parent[i-2] == -1:
                parent[i-2] = temp
            visit[i-1] = "done"

print("Yes")
for i in parent:
    print(i)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
way = [[] for i in range(n + 1)]
ans = [-1 for i in range(n + 1)]
reached = [0 for i in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    way[a].append(b)
    way[b].append(a)
    
D = deque([1])
while D:
    go = D.popleft()
    for i in way[go]:
        if reached[i] == 0:
            D.append(i)
            reached[i] = 1
            ans[i] = go
print("Yes")
for i in range(2, n + 1):
    print(ans[i])

Solution (Python):
from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = [set() for _ in range(N+1)]
    for _ in range(M):
        x = list(map(int, input().split()))
        R[x[0]].add(x[1])
        R[x[1]].add(x[0])
    
    q = deque()
    
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        
        ro = R[x]
        for i in ro:
            
            if r[i] == 0: 
                r[i] = x
                q.append(i)
    
    print("Yes")
    print("\n".join(map(str, r[2:])))
    
    

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict as d, deque

def bfs(adj, start, n):
	visited = [0] * (n + 1)
	tab = [0] * n
	q = deque([start])
	visited[start] = 1
	while q:
		s = q.popleft()
		for i in adj[s]:
			if visited[i] == 0:
				q.append(i)
				visited[i] = 1
				tab[i - 1] = s
	return tab

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

t = bfs(adj, 1, n)
if 0 in t[1:]:
	print('No')
else:
	print('Yes')
	for i in range(1, n):
		print(t[i])

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

ans = defaultdict(int)
next_list = []
for j in graph[1]:
    ans[j] = 1
    next_list.append(j)

target_list = next_list[:]
while True:
    next_list = []
    if len(target_list) == 0:
        break

    for i in target_list:
        for j in graph[i]:
            if j not in ans:
                ans[j] = i
                next_list.append(j)
    target_list = next_list[:]


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

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

for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])

seen = [-1]*n
seen[0] = 1
que = deque([1])
while que:
    v = que.popleft()
    for i in b[v-1]:
        if seen[i-1] != -1:
            continue
        que.append(i)
        seen[i-1] = v

for i in range(n):
    if seen[i] == -1:
        print("No")
else:
    del seen[0]
    print("Yes")
    for i in range(n-1):
        print(seen[i])

Solution (Python):
from collections import deque
n, m = map(int, input().split())
way = [[] for i in range(n + 1)]
ans = [-1 for i in range(n + 1)]
reached = [0 for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    way[a].append(b)
    way[b].append(a)
D = deque([1])
while D:
    go = D.popleft()
    for i in way[go]:
        if reached[i] == 0:
            D.append(i)
            reached[i] = 1
            ans[i] = go
print('Yes')
for i in range(2, n + 1):
    print(ans[i])

Solution (Python):
N,M=map(int,input().split())
from heapq import heappop,heappush 

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)

mark=[-1]*(N-1)

inf=float("inf")

di=[inf]*N
di[0]=0
hq=[(0,0)]

while hq:
    t,r=heappop(hq) 
    if t>di[r]:
        continue
    for x in graph[r]:
        t_new=t+1
        r_new=x
        if t_new<di[r_new]:
            di[r_new]=t_new
            heappush(hq,(t_new,r_new))
            if mark[r_new-1]==-1:
                mark[r_new-1]=r
    
print("Yes")
for i in mark:
    print(i+1)

Solution (Python):
from collections import defaultdict, deque
n, m = map(int, input().split())
li = [[] for _ in range(n)]
check = [-1] * (n)
check[0] = 0
que = deque([1])
memo = defaultdict(int)
for i in range(m):
    a, b = map(int, input().split())
    li[a-1].append(b)
    li[b-1].append(a)
while que:
    now = que.popleft()
    for l in li[now-1]:
        if check[l-1] != -1: continue
        check[l-1] = now
        que.append(l)

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

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


def bfs(si):
    q = deque()
    lights = [None for _ in range(N)]
    q.append(si)
    lights[si] = 0

    while len(q) > 0:
        prv_i = q.popleft()
        for i in g[prv_i]:
            if lights[i] is not None:
                continue
            else:
                lights[i] = prv_i
                q.append(i)
    return lights


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

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

lights = bfs(0)
if None in lights:
    print('No')
else:
    print('Yes')
    [print(val + 1) for val in lights[1:]]

Solution (Python):
import heapq

max_v,m = input().split()
max_v = int(max_v)
m = int(m)

class Edge(object):
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


edges = [[] for j in range(max_v)]
for i in range(m):
  a, b = input().split()
  a = int(a)
  b = int(b)
  edges[a-1].append(Edge(b-1,1))
  edges[b-1].append(Edge(a-1,1))

d = [float("inf")]*max_v
fire = [-1]*max_v

def dijkstra(s):
	h = []
	d[s] = 0
	heapq.heappush(h, [0,0])
	while(len(h) != 0):
		p = heapq.heappop(h)
		v = p[1]
		if d[v] < p[0]:continue
		for i in range(len(edges[v])):
			e = edges[v][i]
			if d[e.to] > d[v] + e.cost:
				d[e.to] = d[v] + e.cost
				heapq.heappush(h, [d[e.to], e.to])
				fire[e.to] = v
dijkstra(0)
if 2 <= fire.count(-1):
  print("No")
else:
  print("Yes")
  for i in range(1, max_v):
    print(fire[i]+1)

Solution (Python):
def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
    n,m=LI()
    edge=[[] for i in range(n)]
    for i in range(m):
        a,b=LI()
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)
    
    ans=[-1]*(n)
    goal=deque([0])
    while goal:
        g=goal.popleft()
        for i in edge[g]:
            if ans[i]==-1:
                ans[i]=g+1
                goal.append(i)
    yes()
    print(*ans[1:])
main()

Solution (Python):
import sys
import heapq

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

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


INF = float('inf')
reach = [INF for _ in range(N)] 
reach[0] = 0
par = [-1 for _ in range(N)] 

Q =[]
heapq.heappush(Q, (0,0)) 

while Q:
  d,v = heapq.heappop(Q)
  for i in range(len(g[v])): 
    u = g[v][i] 
    
    if u == 0: 
      continue
    if reach[u] != INF: 
      continue
    reach[u] = d + 1 
    par[u] = v
    heapq.heappush(Q, (reach[u],u))


if INF not in reach[1:]:
  print("Yes")
  for i in range(1,N):
    ans = par[i]+1
    print(ans)
else:
  print("No")

Solution (Python):
def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
    n,m=LI()
    edge=[[]*n for i in range(n)]
    for i in range(m):
        a,b=LI()
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)
    
    ans=[-1]*(n)
    goal=deque([0])
    while goal:
        g=goal.popleft()
        for i in edge[g]:
            if ans[i]==-1:
                ans[i]=g+1
                goal.append(i)
    yes()
    print(*ans[1:])
main()

Solution (Python):


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

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

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

parent = [1]


while len(parent) > 0:
    child = []
    for p in parent:
        for c in D[p]:
            if T[c] != 0: continue
            T[c] = p
            child.append(c)
    parent = child

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

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

Solution (Python):
import collections,copy,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
AB = [LI() for _ in range(M)]
graph = {i:collections.deque() for i in range(1,N+1)} 
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
for i in range(1,N+1):
    if not graph[i]:
        print('No')
        exit()
else:
    print('Yes')
seen = [0]*(N+1) 
min_dist = [-1]*(N+1) 
queue = collections.deque() 
def bfs():
    c_graph = copy.deepcopy(graph)
    seen[1] = 1
    queue.append(1)
    min_dist[1] = 0
    while queue:
        q_NO = queue.popleft()
        q_dist = min_dist[q_NO]
        if not c_graph[q_NO]:
            continue
        g = c_graph[q_NO]
        for _ in range(len(g)):
            g_NO = g.popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            queue.append(g_NO)
            min_dist[g_NO] = q_dist+1
bfs()
for j in range(2,N+1):
    ans,dist = 0,float('INF')
    for x in graph[j]:
        if dist>=min_dist[x]:
            ans = x
            dist = min_dist[x]
    print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    
    
    '''
    A=[]
    B=[]
    for i in range():
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)'''

    n,m = map(int, input().split())
    r=[[]for i in range(n)]
    start = [0, 0]
    
    for i in range(m):
        a,b=map(int, input().split())
        r[a-1].append(b-1)
        r[b-1].append(a-1)
    
    
    from collections import deque
    d = [0 for i in range(n)]
    visited=[False for i in range(n)]
    flg = True
    queue=deque([0])
    dd=0
    while queue:
        now=queue.popleft()
        visited[now]=True
        
        for i in r[now]:
            if visited[i]:
                continue
            queue.append(i)
            visited[i]=True
            d[i]=now

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


if __name__ == "__main__":
     main()

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**18

def bfs(start):
    d = [INF]*n
    d[start] = 0
    q = collections.deque([])
    q.append(start)
    pre = [0]*(n)
    while q:
        c = q.popleft()
        next_v = edge[c]
        for v in next_v:
            if v == 0 and start != 0:
                d[v] = d[c]+1
                pre[v] = c
                return [pre,d]
            if d[v] == INF and v != c:
                q.append(v)
                d[v] = d[c]+1
                pre[v] = c
    
    return [pre,d]
n,m = map(int,input().split())
edge =[[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
ans = bfs(0)
judge = ans[1]
for i in judge:
    if i == INF:
        print("No")
        sys.exit()
print("Yes")
for i in range(1,n):
    print(ans[0][i]+1)

Solution (Python):


import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, M = LI()
AB = LRI(M)

visited = [False] * N


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

ret = [-1] * N
Q = collections.deque([[0,0]])
while Q:
    qs = Q.popleft()
    b = qs[0]
    q = qs[1]

    if visited[q]:
        continue
    else:
        visited[q] = True
    
    ret[q] = b

    for r in root[q]:
        Q.append([q, r])

if -1 in ret:
    print("No")
else:
    print("Yes")
    for i, r in enumerate(ret):
        if i == 0:
            continue

        print(r+1)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


def dijkstra(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素は(ノード, エッジ長)
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    P ... 最短経路木における親
    '''
    pq = PriorityQueue([])
    P = [None] * N
    D = [float('inf')] * N
    D[s] = 0
    pq.push((D[s], s))  
    while pq:
        d, v = pq.pop()
        if D[v] < d:  
            continue  
        for to, cost in graph[v]:
            if D[to] > D[v] + cost:  
                D[to] = D[v] + cost
                pq.push((D[to], to))
                P[to] = v
    return D, P


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  

N, M = read_ints()



graph = defaultdict(lambda: [])
for _ in range(M):
    a, b = read_ints()
    a -= 1
    b -= 1
    graph[a].append((b, 1))
    graph[b].append((a, 1))

D, P = dijkstra(graph, 0, N)
ans = []
for p in P[1:]:
    ans.append(p + 1)
print('Yes')
print(*ans, sep='\n')

Solution (Python):
def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
    n,m=LI()
    edge=[[] for i in range(n)]
    for i in range(m):
        a,b=LI()
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)    
    ans=[-1]*(n)
    goal=deque([0])
    while goal:
        g=goal.popleft()
        for i in edge[g]:
            if ans[i]==-1:
                ans[i]=g+1
                goal.append(i)
    yes()
    print(*ans[1:])
main()

Solution (Python):
import sys
from collections import deque


input = sys.stdin.readline


def main():
    while que:
        nn = que.popleft()
        for n in edges[nn-1]:
            if D[n-1] == INF or D[n-1] > D[nn-1] + 1:
                D[n-1] = D[nn-1] + 1
                que.append(n)
                if n > 1:
                    B[n-2] = nn
    print("Yes")
    for b in B:
        print(b)


if __name__ == "__main__":
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        edges[a-1].append(b)
        edges[b-1].append(a)
    B = [0]*(N-1)
    que = deque([1])
    INF = 10**10
    D = [INF]*N
    D[0] = 0
    main()

Solution (Python):
N,M=list(map(int,input().split()))
g=[[] for _ in range(N+1)]
for m in range(M):
    a,b=list(map(int,input().split()))
    if a<=N and b<=N:
        g[a].append(b)
        g[b].append(a)
queue=[1]
d=[None]*(N+1)
d[0]=0
d[1]=0
while queue:
    v=queue.pop(0)
    for i in g[v]:
        if d[i] is None:
            d[i]=v
            queue.append(i)
for i in range(N+1):
    if d[i] is None:
        print('No')
        exit()
print('Yes')
for i in range(2,N+1):
    print(d[i])

Solution (Python):
from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0
    q = deque([0])
    cnt = 0
    while q:
        now = q.popleft()
        for next in g[now]:
            if prev[next] < 0:
                if prev[next] < 0:
                    q.append(next)
                    cnt += 1
                prev[next] = now + 1
                dist[next] = dist[now] + 1
    if cnt == n:
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


if __name__ == '__main__':
    main()

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

from collections import deque

N,M=map(int,input().split())
AL=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    AL[A-1].append(B-1)
    AL[B-1].append(A-1)
Q=deque([[0,-1]]) 
ANS=[-1 for _ in range(N)] 
ANS[0]=1
TF=[0 for _ in range(N)]
while Q:
    i,c=Q.popleft()
    if TF[i]:
        continue
    TF[i]=1
    ANS[i]=c
    for j in AL[i]:
        if not TF[j]:
            Q.append([j,i])

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

Solution (Python):

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


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

def bfs(graph, n, start):
    visited = [False] * n
    visited[start] = True
    que = deque([start])
    count = 1
    ans = [None] * n
    while que:
        root = que.popleft()
        for node in graph[root]:
            if not visited[node]:
                visited[node] = True
                que.append(node)
                if not ans[node]:
                    ans[node] = root
    result = all(visited)
    return result, ans

r, ans = bfs(graph, n, 0)
if r:
    print('Yes')
    for a in ans[1:]:
        print(a + 1)
else:
    print('No')

Solution (Python):
from collections import deque
def main():
    N,M= map(int, input().split())
    ans = [-1]*(N+1)
    ans2 = [-1]*(N+1)
    ans[1] = 0

    L=[]
    [L.append([])for _ in range(N+1)]

    for i in range(M):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    
    q = deque()
    qq = deque()


    for i in range(len(L[1])):
        q.append(L[1][i])
        qq.append(1)

    while len(q) !=0:
        temp = q.popleft()
        tempq = qq.popleft()
        if ans[temp]==-1:
            ans[temp] = tempq + 1
            ans2[temp] = tempq

            for i in range(len(L[temp])):
                q.append(L[temp][i])
                qq.append(temp)

    for i in range(2,N+1):
        if ans[i]==-1:
            print('No')
            return

    print('Yes')

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





if __name__ == '__main__':
    main()

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

def abc168_d():
    N, _ = map(int, readline().split())
    adj = [[] for _ in range(N+1)]
    for ln in readlines():
        a, b = map(int, ln.split())
        adj[a].append(b)
        adj[b].append(a)

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

    from collections import deque
    que = deque([1])

    while que:
        k = que.popleft()
        for x in adj[k]:
            if label[x] != -1: continue  
            label[x] = k  
            que.append(x)  

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

abc168_d()

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

def main():
    n,m=map(int,input().split())
    Edges=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x: int(x)-1,input().split())
        Edges[a].append(b)
        Edges[b].append(a)
    Ans=[0]*n
    Ans[0]=-1
    q=deque()
    q.append(0)
    while q:
        fr=q.popleft()
        for to in Edges[fr]:
            if Ans[to]==0:
                Ans[to]=fr+1
                q.append(to)
    print('Yes')
    print(*Ans[1:],sep='\n')
    
if __name__=='__main__':
    main()

Solution (Python):
from collections import deque

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

route = deque([ [0] for i in range(n)])

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

mi = deque([10**6] * n)
mi[0] = 0
check = deque([n] * n)
end = deque([0] * n)
end[0] = 1

que = deque([0])
while len(que) != 0:
    t = que.popleft()
    for j in route[t]:
        if mi[j] > mi[t] + 1:
            que.append(j)
            mi[j] = mi[t] + 1
            check[j] = t

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

Solution (Python):
n, m = map(int,input().split())
li = [[] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    li[a-1].append(b-1)
    li[b-1].append(a-1)
sign = {0: 0}
step = {0: 0}
now = {0}
 
while len(now) > 0:
    next = set()
    for i in now:
        for j in li[i]:
            if not j in sign:
                sign[j] = i
                step[j] = step[i] + 1
                next.add(j)
    now.clear()
    now = next
 
print('Yes')
for i in range(n - 1):
    print(sign[i + 1] + 1)

Solution (Python):
from collections import deque

N,M = map(int,input().split())
V=[[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
state=[0]*N
q=deque()
ans=[0]*(N)

state[0]=1
q.append(0)
while len(q) > 0:
    v=q.popleft()
    for u in V[v]:
        if state[u]==0:
            state[u]=1
            ans[u]=v+1
            q.append(u)
print('Yes')
print(*ans[1:],sep='\n')