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

Solution (Python):
from collections import deque
n, m = [int(x) for x in input().strip().split()]
graph = {}

for i in range(m):
    u, v = [int(x) for x in input().strip().split()]
    if u not in graph:
        graph[u] = []
    if v not in graph:
        graph[v] = []
    graph[u].append(v)
    graph[v].append(u)

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

def bfs(node):
    q = deque([])
    q.append(node)
    dp[node] = node
    while len(q)!=0:
        curr = q.popleft()
        for node in graph[curr]:
            if dp[node] is None:
                dp[node] = curr
                q.append(node)


bfs(1)

flag = True
for i in range(1,n+1):
    if dp[i] is None:
        flag = False
        break

if flag:
    print("Yes")
    for i in range(2,n+1):
        print(dp[i])
else:
    print("No")

Solution (Python):
n, m  = map(int, input().split())
edges = [[] for i in range(n)]

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

dp = [-1] * n
from collections import deque
q = deque([])
q.append(0)
dp[0] = 0
while len(q) > 0:
    u = q.popleft()
    for v in edges[u]:
        if dp[v] != -1:continue
        q.append(v)
        dp[v] = u

for d in dp[1:]:
    if d == -1:
        print("No")
        exit()
print("Yes")
for d in dp[1:]:
    print(d+1)

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

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

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

while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=now+1
        Q.append([nxt,cnt+1])

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

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N, M = Scanner.map_int()
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    q = []
    q.append(0)
    ans = [-1 for _ in range(N)]
    visited = [False for _ in range(N)]
    visited[0] = True
    while q != []:
        p = q.pop(0)
        for g in G[p]:
            if visited[g]:
                continue
            visited[g] = True
            ans[g] = p
            q.append(g)
    ans = [a + 1 for a in ans]
    print('Yes')
    print(*ans[1:], sep='\n')


def main():
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    roads = [[] for _ in range(n)]
    ans = [0]*n
    for i in range(m):
        a, b = map(int, input().split())
        roads[a-1].append(b-1)
        roads[b-1].append(a-1)
    
    already = [False]*n
    dist = [0]*n
    par = [0]*n
    not_yet = deque(roads[0])
    for v in roads[0]:
        dist[v] = 1
        par[v] = 1
        already[v] = True
    already[0] = True
    
    while not_yet:
        key = not_yet.popleft()
        for v in roads[key]:
            if already[v]:
                continue
            already[v] = True
            par[v] = key+1
            dist[v] = dist[key] + 1
            not_yet.append(v)
    
    if all(already):
        print("Yes")
        for i in range(1, n):
            print(par[i])
    else:
        print("No")
  


if __name__ == "__main__":
    main()

Solution (Python):
def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))


from collections import deque
n,m = mp()
path = []
for i in range(n+1):
    path.append([])
for i in range(m):
    a,b = mp()
    path[a].append(b)
    path[b].append(a)

ans = [0]*(n+1)
q = deque([1])
used = set()
used.add(1)
while q:
    here = q.popleft()
    for i in path[here]:
        if i not in used:
            ans[i] = here
            q.append(i)
            used.add(i)
print("Yes")
for i in range(2, n+1):
    print(ans[i])

Solution (Python):
import sys
from collections import deque
import copy
def main():
    N, M = map(int, input().split())
    dp = [[] for i in range(N)]
    color = [-1 for i in range(N)]
    distance = [10**5 for i in range(N)]
    color[0] = 0
    distance[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        dp[a].append(b)
        dp[b].append(a)
    queue = deque()
    queue.append((0, 0))
    while len(queue) != 0:
        now, d = queue.popleft()
        for i in range(len(dp[now])):
            if color[dp[now][i]] == -1 or distance[dp[now][i]] > d + 1:
                distance[dp[now][i]] = d + 1
                color[dp[now][i]] = now
                queue.append((dp[now][i], d + 1))
    for i in range(N):
        if color[i] == -1:
            print("No")
            sys.exit()
    print("Yes")
    for i in range(1, N):
        print(color[i] + 1)



if __name__ == '__main__':
    main()

Solution (Python):
def dijkstra_al(s, n, ALcost, start_index = 0):
    '''
    ダイクストラ法 O(|E|log|V|)
    グラフを隣接リストで表す場合
    始点sから各頂点への最短距離
    n: 頂点の数、s: 始点
    ALcost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    start_index: 0のときvertexは0, 1, ..., n-1
                 1のときvertexは1, 2, ..., n
    '''
    import heapq
    INF = float('inf')

    fixed = [False] * (n + 1) 
    nfixed = 0 
    vertex_cost = [INF] * (n + 1)  
    prev_vertex = [None] * (n + 1) 

    
    vertex_cost[s] = 0
    prev_vertex[s] = None
    H = []  
    heapq.heappush(H, (0, s))

    while(H): 
        
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  
        fixed[u] = True
        nfixed += 1

        
        
        for v, edge_cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + edge_cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))
                prev_vertex[v] = u

        
        if nfixed == n: break

    if start_index == 0:
        return vertex_cost[:n], prev_vertex[:n]
    else:
        return vertex_cost, prev_vertex 


N, M = [int(x) for x in input().split()]
ALcost = [[] for _ in range(N + 1)]
for i in range(M):
    u, v = [int(x) for x in input().split()]
    ALcost[u].append((v, 1))
    ALcost[v].append((u, 1))

print("Yes")
vertex_cost, prev_vertex = dijkstra_al(1, N, ALcost, 1)
for i in range(2, N + 1):
    print(prev_vertex[i])

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

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

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

from collections import deque

queue = deque([0])
d = [None] * N
d[0] = 0
while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] is None:
            d[i] = v+1
            queue.append(i)

if None in d:
    print('No')
else:
    print('Yes')
    for i in d[1:]:
        print(i)

Solution (Python):
from collections import deque

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

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

stack = deque()
stack.append(0)
while stack:
    x = stack.popleft()
    connected = v[x]
    for u in connected:
        if ans[u] == None:
            ans[u] = x + 1
            stack.append(u)
print('Yes')
print(*ans[1:], sep='\n')

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

stack = deque([0])
ans = [-1]*n
ans[0] = 0
flag = [True]*n
flag[0] = False
while stack:
    a = stack.pop()
    for i in way[a]:
        if (flag[i]):
            stack.appendleft(i)
            ans[i] = a
            flag[i] = False

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
d, check = [0]*n, [0]*n
check[0] = 1
for _ in range(m):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
que = deque([0])
count = 1
while que:
    count += 1
    for i in range(len(que)):
        to = que.popleft()
        for j in range(len(edge[to])):
            if check[edge[to][j]]: continue
            check[edge[to][j]] = 1
            d[edge[to][j]] = to+1
            que.append(edge[to][j])

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))
    g = {i: [] for i in range(1, n + 1)}

    for _ in range(m):
        a, b = list(map(int, readline().split()))
        g[a].append(b)
        g[b].append(a)

    from collections import deque

    que = deque()
    que.append(1)
    ans = [-1] * (n + 1)
    ans[1] = 0

    while que:
        cur = que.popleft()
        for nx in g[cur]:
            if ans[nx] == -1:
                ans[nx] = cur
                que.append(nx)

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


if __name__ == '__main__':
    main()

Solution (Python):

import sys

YES = "Yes"  

import collections
import heapq


class Dijkstra:
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    def prev_search(self, s):
        """
        
        
        
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))
        return d, prev

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = Dijkstra()
    for a, b in zip(A, B):
        G.add(a, b, 1)
    ans = G.prev_search(1)[1]
    if None in ans:
        print('No')
    else:
        print('Yes')
        for i in range(2, N+1):
            print(ans[i])
    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):
from collections import deque
N,M = map(int,input().split())
ans = [-1]*(N+1)
E = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)

q = deque([1])
while(q):
    v = q.popleft()
    for s in E[v]:
        if(ans[s] == -1):
            ans[s] = v
            q.append(s)
    
for s in ans[2:]:
    if(s == -1):
        print("No")
        exit()
print("Yes")
for s in ans[2:]:
    print(s)

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

from collections import deque
q = deque([0])
INF = float('inf')
dist = [INF] * N
dist[0] = 0
back = [-1] * N
while q:
    v = q.popleft()
    for to in es[v]:
        if dist[v] + 1 >= dist[to]: continue
        dist[to] = dist[v]
        back[to] = v+1
        q.append(to)
print('Yes')
print(*back[1:], sep='\n')

Solution (Python):
import sys
import heapq


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    prev = [-1] * n_nodes
    dist[start] = 0
    
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        
        d, i = heapq.heappop(q)
        
        
        if dist[i] < d:
            continue
        
        
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                prev[j] = i
                heapq.heappush(q, (dist[j], j))
    return dist, prev


def main():
    N, M = map(int, input().split())
    node = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        node[a - 1].append((1, b - 1))
        node[b - 1].append((1, a - 1))
    d, p = dijkstra(0, N, node)
    for i in range(N):
        if d[i] == float("inf"):
            print("No")
            return
    print("Yes")
    for i in range(1, N):
        print(p[i] + 1)


if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
l=[-1]*n
d=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
from collections import deque
q=deque()
q.append(0)
while q:
    now=q.popleft()
    for x in d[now]:
        if l[x]==-1:
            l[x]=now
            q.append(x)
if -1 in l:
    print("No")
else:
    print("Yes")
    for i in l[1:]:
        print(i+1)

Solution (Python):
from collections import deque

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

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

for i in li:
    i[0]-=1
    i[1]-=1
    road[i[0]].append(i[1])
    road[i[1]].append(i[0])

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    
    v = que.popleft()
    for i,r in enumerate(road[v]):
        if dist[r]!=-1:
            continue
        dist[r] = v+1
        que.append(r)

dist.pop(0)
print('Yes')
print(*dist,sep='\n')

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


from collections import deque
ans = [-1] * n
todo = deque()
todo.append(0)
while len(todo) > 0:
    i = todo.popleft()
    for j in road[i]:
        if ans[j] > -1:
            continue
        ans[j] = i
        todo.append(j)

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

Solution (Python):
from queue import Queue as Q
INF = float('inf')
def bfs(s):
	dist = [INF]*(n+1)
	q = Q()
	q.put(s)
	dist[s] = 0
	while not q.empty():
		u = q.get()
		for v in adj[u]:
			if dist[v]==INF:
				dist[v] = 1+dist[u]
				pred[v] = u
				q.put(v)
				
n,m = map(int,input().split())
pred = [-1]*(n+1)
adj = [[] for i in range(n+1)]
for _ in range(m):
	u,v = map(int,input().split())
	adj[u]+=[v]
	adj[v]+=[u]
bfs(1)
	
if -1 in pred[2:]:
	print("No")
else:
	print("Yes")
	print(*(pred[2:]),sep = "\n")

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    graph = {}
    for i in range(N):
        graph[i] = set()
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A-1].add(B-1)
        graph[B-1].add(A-1)
    que = deque([])
    que.append(0)
    seen = [0 for _ in range(N)]
    ans = [0 for _ in range(N)]
    while len(que) != 0:
        v = que.popleft()
        for node in graph[v]:
            if seen[node] == 1:continue
            ans[node] = v
            seen[node] = 1
            que.append(node)
    ok = "Yes"
    for i in range(N):
        if seen[i] == 0:
            ok = "No"
            break
    print(ok)
    if ok == "Yes":
        for i, a in enumerate(ans):
            if i == 0:continue
            print(a+1)
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

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

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

q = deque()
q.append(1)

while q:
	cur = q.popleft()
	for dest in roads[cur]:
		if ans[dest] == -1:
			ans[dest] = cur
			q.append(dest)


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

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

def main():
    N,M = map(int,input().split())
    edge = [[] for _ in range(N)]
    
    for _ in range(M):
        a,b = map(int,input().split())
        a -= 1;b -= 1
        edge[a].append(b)
        edge[b].append(a)
        
    go = [False]*N
    go[0] = True
    bef = [-1]*N
    
    q = deque([0])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if not go[fol]:
                bef[fol] = now
                go[fol] = True
                q.append(fol)

    if False in go:
        print("No")
    else:
        print("Yes")
        for i in range(1,N):
            print(bef[i]+1)

if __name__ == "__main__":
    main()

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

prev = [-1] * N

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        prev[w] = v
        que.append(w)

print("Yes")
print(*[prev[i]+1 for i in range(1, N)], sep='\n')

Solution (Python):
n, m = map(int ,input().split())

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

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

from collections import deque
q = deque()

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

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

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

Solution (Python):
from heapq import heappop, heappush

def dijkstra(s):
    used = [1] * N
    dp = [INF] * N
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

INF = 10 ** 18
N, M = map(int, input().split())
cost = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    cost[a].append([1, b])
    cost[b].append([1, a])
dp1 = dijkstra(0)
for i in dp1:
    if i == INF:
        print('No')
        exit()
print('Yes')
for i in range(1, N):
    tmp = dp1[i] - 1
    for j in cost[i]:
        if dp1[j[1]] == tmp:
            print(j[1] + 1)
            break

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

for i in range(m):
    a, b = map(int, input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
seen = set([0])
q = deque([0])
ans = [0] * n
while q:
    parent = q.popleft()
    for child in d[parent]:
        if child not in seen:
            ans[child] = parent + 1
            q.append(child)
            seen.add(child)
    if len(seen) == n:
        break
print('Yes')
for i in ans[1:]:
    print(i)

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

ans = [0 for i in range(n+1)]
import queue
q = queue.Queue()
q.put(1)
while not q.empty():
  node = q.get()
  for e in edges[node]:
    if ans[e] == 0:
      ans[e] += node
      q.put(e)

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
g = [[] for 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 = [None]*(n+1)
q = deque([1])
ans[1] = 0

while q:
    now = q.popleft()
    for next in g[now]:
        if ans[next] == None:
            ans[next] = now
            q.append(next)

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

Solution (Python):
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)

D = [None]*(N+1)
D[1] = 0

Q = set([1])

while len(Q) > 0:
    Q2 = set()
    for q in Q:
        for r in G[q]:
            if D[r] == None:
                D[r] = q
                Q2.add(r)

    Q = Q2


print('Yes')
for d in D[2:]:
    print(d)

Solution (Python):
n, m = map(int, input().split())
visited = set()
my_dict = dict()

for i in range(m):
    a, b = map(int, input().split())
    if a in my_dict:
        my_dict[a].append(b)
    else:
        my_dict[a] = [b]
    if b in my_dict:
        my_dict[b].append(a)
    else:
        my_dict[b] = [a]

ret_dict = dict()

queue = [1]
visited.add(1)

while queue:
    item = queue.pop(0)
    if item in my_dict:
        for val in my_dict[item]:
            if val not in visited:
                visited.add(val)
                queue.append(val)
                ret_dict[val] = item

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

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

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

q = deque()
q.append(1)
d = [0]*(N+1)
d[1]=1
while q:
    u = q.popleft()
    for v in adj[u]:
        if d[v]!=0:
            continue
        q.append(v)
        d[v]=u
isOK = True
for i in range(2,N+1):
    if d[i]==0:
        isOK = False
if isOK:
    print('Yes')
    for j in range(2,N+1):
        print(d[j])
else:
    print('No')

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

q = deque([(0, None)])
searched = [False for i in range(N)]
ans = [-1 for i in range(N)]
while len(q) > 0:
	after, before = q.popleft()
	if searched[after]:
		continue
	searched[after] = True
	ans[after] = before
	for n in edge[after]:
		if searched[n]:
			continue
		q.append((n, after))

flag = True
for i in range(1, N):
	if ans[i] == -1:
		flag = False
		break

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

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

q = [0]
vis = [False]*n
sign = [0]*n
vis[0] = True
while(q):
    s = q.pop(0)
    for i in adj[s]:
        if (not vis[i]):
            vis[i] = True
            sign[i] = s+1
            q.append(i)
if (not all(vis)):
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(sign[i])

Solution (Python):
from collections import defaultdict as dd
n, m = map(int, input().split())
Ways = dd(set)
for i in range(m):
    a, b = map(int, input().split())
    Ways[a].add(b)
    Ways[b].add(a)

visited = set([1])
Ans = [0] * (n+1)
stack = [1]
while stack != [] and len(visited) != n:
    temp = []
    for room in stack:
        for next_room in list(Ways[room] - visited):
            Ans[next_room] = room
            visited.add(next_room)
            temp.append(next_room)
    stack = temp

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

Solution (Python):
import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
def main():
    N, M = map(int,input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int,input().split())
        G[A-1].append(B-1)
        G[B-1].append(A-1)
    Q = deque([0])
    ans = [-1]*N
    while len(Q) > 0:
        ima = Q.popleft()
        for tsugi in G[ima]:
            if ans[tsugi] == -1:
                ans[tsugi] = ima+1
                Q.append(tsugi)
    print("Yes")
    for e in ans[1:]:
        print(e)
if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())

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


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

ans = [-1] * (n+1)


import collections
q = collections.deque([1])

while q:
    now = q.popleft()
    for t in to[now]:
        if ans[t] == -1:
            q.append((t))
            ans[t] = now

if (-1) in ans[2:]:
    print('No')
else:
    print('Yes')
    for a in ans[2:]:
        print(a)

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

table.add(0)

while len(table) != 0:
    new_table = set()
    for point in table:
        for next_room in room[point]:
            if navi[next_room] != -1:
                continue
            navi[next_room] = point
            new_table.add(next_room)

    table = new_table

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