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())
A=[];B=[]
for i in range(M):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
G=[set() for i in range(N)]
for i in range(M):
    G[A[i]-1].add(B[i]-1)
    G[B[i]-1].add(A[i]-1)
ans=[-1 for i in range(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
        que.append(w)
        ans[w]=v
ex=True
for i in range(1,N):
    if ans[i]==-1:
        ex=False
if ex:
    print("Yes")
    for i in range(1,N):
        print(ans[i]+1)
else:
    print("No")

Solution (Python):
from collections import deque

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

que = deque([1])

while len(que) > 0:
    x = que.popleft()
    for r in rooms[x]:
        if ans[r] == 0:
            ans[r] = x
            que.append(r)

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

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = [int(x) for x in input().split()]
    AB = [[int(x) for x in input().split()] for _ in range(M)]

    A = [[] for j in range(N + 1)]
    ans = [0] * (N + 1)

    u = UnionFind(N)

    for a, b in AB:
        A[a].append(b)
        A[b].append(a)
        u.union(a - 1, b - 1)

    if u.group_count() > 1:
        print("No")
        return

    q = collections.deque()
    v = set()

    q.append(1)
    v.add(1)
    while q:
        c = q.popleft()

        for n in A[c]:
            if n not in v:
                v.add(n)
                q.append(n)
                ans[n] = c

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split())
edge = defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

done = {1}
ans = [None] * (N + 1)
queue = deque()
queue.append(1)
while queue and len(done) < N:
    v1 = queue.popleft()
    for v2 in edge[v1]:
        if v2 not in done:
            done.add(v2)
            ans[v2] = v1
            queue.append(v2)
print('Yes')
for i in range(2, N + 1):
    print(ans[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())
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

from collections import deque
def bfs():
    heap = deque()
    road = [0]*n

    heap.append((0, -1))
    used = set()
    while heap:
        cur, prev = heap.popleft()
        if cur in used:
            continue
        used.add(cur)
        road[cur] = prev+1
        for to in G[cur]:
            if to not in used and to != prev:
                heap.append((to, cur))
    return road

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

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

print("Yes")

d = deque()
d.append(1)
ans[1] = 0
while d:
    now = d.popleft()
    for i in tuuro[now]:
        if ans[i] == -1:
            ans[i] = now
            d.append(i)

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

Solution (Python):
from collections import deque

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

ans = [-1 for _ in range(n)]
d = deque()
d.append(0)
while len(d) > 0:
    now = d.popleft()
    for v in to[now]:
        if ans[v] > -1:
            continue
        ans[v] = now
        d.append(v)

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

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

for _ in range(M):
    u, v = list(map(int, input().split()))
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)

ans = [-1] * N

queue = deque([(0, 0)])
visited = set([0])
while queue:
    v, prev = queue.popleft()
    ans[v] = prev
    for nv in graph[v]:
        if nv not in visited:
            visited.add(nv)
            queue.append((nv, v))

if -1 in ans:
    print('No')
    exit()
    
for i, v in enumerate(ans):
    if i == 0:
        print('Yes')
    else:
        print(v + 1)

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


queue = [0] 
ans=[0]*n
visited =[0]*n
visited[0] = 1  
while queue:
    x= queue.pop(0)
     
    
    for y in maiz[x]:
        if visited[y]==0 :
            visited[y] = 1
            
            queue.append(y)
            ans[y]=x
if min(visited)==0:
    print("No")
    exit()
else:
    print("Yes")
for i in range(1,n):
    print(ans[i]+1)

Solution (Python):
import os
import heapq

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

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

dist = [(INF, None)] * N
dist[0] = 0, None
heap = [(0, 0, None)]
while heap:
    d, v, p = heapq.heappop(heap)
    if dist[v][0] > d:
        continue
    for u in graph[v]:
        if d + 1 >= dist[u][0]:
            continue
        dist[u] = d + 1, v
        heapq.heappush(heap, (d + 1, u, v))
print('Yes')
for d, p in dist[1:]:
    print(p + 1)

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

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

for a,b in lis:
    path[a-1].append(b-1)
    path[b-1].append(a-1)
gone = [0] * n
gone[0] = 1
ans = [-1] * n
now = {0}
for i in range(10 ** 5):
    next = set()
    while now:
        a = now.pop()
        for go in path[a]:
            if gone[go] == 0:
                gone[go] = 1
                ans[go] = a
                next.add(go)
    now = next
print("Yes")
for i in range(1,n):
    print(ans[i]+1)

Solution (Python):
import queue
import sys
sys.setrecursionlimit(1000000)

n,m=map(int,input().split())
G=[[] for i 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)
    
P=[-1]*n 
q=queue.Queue()
q.put(0)
while not q.empty(): 
    now=q.get() 
    for i in G[now]:
        if P[i]==-1 and i!=0: 
            P[i]=now 
            q.put(i) 
print("Yes")
for i in range(1,n):
    print(P[i]+1)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
edge=[]
ans=[-1]*n
for i in range(n):
    edge.append([])
for i in range(m):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
q=deque([0])
while q:
    x=q.popleft()
    for i in range(len(edge[x])):
        if ans[edge[x][i]]==-1:
            ans[edge[x][i]]=x+1
            q.append(edge[x][i])
print('Yes')
for i in range(len(ans)-1):
    print(ans[i+1])

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

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

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

q = queue.Queue()
q.put(0)
point = [0] * n
seen = [0] * n
seen[0] = 1

while not q.empty():
    i = q.get()
    for j in graph[i]:
        if seen[j] == 0:
            point[j] = i + 1
            seen[j] = 1
            q.put(j)

print('Yes')
for x in range(1, n):
    print(point[x])

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,M=mis()
    W = [None] + [set() for _ in range(N)]
    for _ in range(M):
        a, b = mis()
        W[a].add(b)
        W[b].add(a)
    ans = [None]*(N+1)
    ans[1] = True
    q = deque()
    q.append(1)
    while q:
        p = q.popleft()
        for np in W[p]:
            if ans[np] is None:
                ans[np] = p
                q.append(np)
    print('Yes')
    print(*ans[2:], sep='\n')


main()

Solution (Python):
from heapq import heappush, heappop

INF = 10**15

def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    prev = [-1] * n
    d[s] = 0
    heappush(que, (0, s))

    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                prev[w] = v
                heappush(que, (d[w], w))

    return d, prev

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

d, prev = dijkstra(0, edges)
print('Yes')
for i in range(1, n):
    print(prev[i]+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)

q = deque([1])
ans = {}

visited = [False] * (n+1)
visited[1] = True

while q:
    now = q.popleft()
    for i in graph[now]:
        if not visited[i]:
            q.append(i)
            visited[i] = True
            ans[i] = now

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

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


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

q = deque()
q.append((0, -1))
seen = set()
seen.add(0)
ans = [0] * N
while len(q) > 0:
    v, p = q.popleft()
    ans[v] = p
    for nxt in adj[v]:
        if nxt not in seen:
            q.append((nxt, v))
            seen.add(nxt)
print('Yes')
for a in ans[1:]:
    print(a + 1)

Solution (Python):



import queue 












mod = 998244353
INF = 1<<29
lINF = 1<<35

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

def main():
    n,m = readInt()
    g = [[] for i in range(n)]
    for i in range(m):
        x,y = readInt()
        g[x-1].append(y-1)
        g[y-1].append(x-1)
    v = [[-1,-1] for i in range(n)]
    v[0] = [0,0]
    q = queue.Queue()
    q.put(0)
    while not q.empty():
        x = q.get()
        for y in g[x]:
            if v[y][0]!=(-1):
                continue
            q.put(y)
            v[y][0] = v[x][0] + 1
            v[y][1] = x
    print("Yes")
    for i in range(1,n):
        print(v[i][1]+1)
    return

if __name__=='__main__':
    main()

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

class Graph(): 
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]-1].append(e[1]-1)
            self.graph[e[1]-1].append(e[0]-1)
            self.deg[e[0]-1] += 1
            self.deg[e[1]-1] += 1
    def BFS(self,s):
        dist = [None for _ in range(self.n)]
        dist[s] = 0
        queue = deque([s])
        self.par = [None for _ in range(self.n)]
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                if dist[adj] is not None:
                    continue
                dist[adj] = dist[node]+1
                self.par[adj] = node
                queue.append(adj)
        return dist

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

G = Graph(N, E)

G.BFS(0)
res = list()

print('Yes')

for i in range(N):
    if i == 0:
        continue
    res.append(G.par[i] + 1)

print('\n'.join(map(str, res)))

Solution (Python):
from queue import Queue
INF = 10 ** 6
N, M = map(int,input().split())
Q = Queue()
edges = [[] for _ in range(N+1)]
guidepost = [INF for _ in range(N+1)]
for _ in range(M):
    A, B = map(int,input().split())
    edges[A].append(B)
    edges[B].append(A)
Q.put(1)
while not Q.empty():
    parent = Q.get()
    for i in edges[parent]:
        if guidepost[i] == INF:
            guidepost[i] = parent
            Q.put(i)
print('Yes')
for i in range(2,N+1):
    print(guidepost[i])

Solution (Python):
import sys

N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    ta, tb = map(int, input().split())
    E[ta].append(tb)
    E[tb].append(ta)

q = [1]

root = [0] * (N+1)
root[0], root[1] = -1, -1
flg = [0] * (N+1)
flg[0], flg[1] = 1, 1

while q:
    cp = q.pop(0)
    for np in E[cp]:
        if root[np] != 0:
            continue
        else:
            root[np] = cp
            q.append(np)

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

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

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


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

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        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

    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    


N, M = map(int, input().split())
graph = Dijkstra()
for i in range(M):
    a, b = map(int, input().split())
    
    graph.add(a, b, 1, directed=False)
ans = []
_, prev = graph.Dijkstra_search(1)
for i in range(2, N + 1):
    if prev[i] is None:
        print("No")
        exit()
    else:
        ans.append(prev[i])
print("Yes")
print("\n".join(map(str, ans)))

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

markers = [-1] * N

queue = [0]
steps = [-1] * N
steps[0] = 0
while len(queue) >= 1:
    room = queue.pop(0)
    for r in connections[room]:
        if steps[r] >= 0:
            continue
        queue.append(r)
        steps[r] = steps[room] + 1
        markers[r] = str(room + 1)

print("Yes")
print("\n".join(markers[1:]))

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

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

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

vst = [-1] * N
q = [0]
vst[0] = 0
cnt = 0
for u in q:
    cnt += 1
    for v in adj[u]:
        if vst[v] < 0:
            vst[v] = u
            q.append(v)

if cnt == N:
    print('Yes')
    for k in vst[1:]:
        print(k + 1)

else:
    print('No')

Solution (Python):
import collections
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

ans = [0]*N
G = [set() for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

q = collections.deque([0])

r = set()
r.add(0)
while(q):
    x = q.popleft()
    for y in G[x]:
        if y in r:
            continue
        else:
            ans[y] = x+1
            r.add(y)
            q.append(y)

if len(r) < N:
    print('No')
else:
    print("Yes")
    print(*ans[1:], sep='\n')

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

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

from collections import deque
d = deque([0])
dp = [100000000000]*n
ma = [0]*n
i = 1

while d:
    a = d.popleft()
    for j in g[a]:
        if dp[j] > i:
            dp[j] = i
            ma[j] = a
            d.append(j)
    i += 1

print('Yes')

for i in range(1,n):
    print(ma[i]+1)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n,m=map(int,input().split())
    graph=[[] for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    queue=deque([0])
    visited=[False]*n
    visited[0]=True
    ans=[0]*n
    while queue:
        node=queue.popleft()
        for xnode in graph[node]:
            if visited[xnode]:continue
            ans[xnode]=node+1
            visited[xnode]=True
            queue.append(xnode)
    print("Yes")
    for a in ans[1:]:
        print(a)


if __name__=='__main__':
    main()

Solution (Python):
from collections import deque
N, M = map(int, input().split())
G = [deque() for _ in range(N+1)]
ans = [0]*(N+1)
for _ in range(M):
  a, b = map(int, input().split())
  G[a].append(b)
  G[b].append(a)
memo = [False]*(N+1)
q = deque()
q.append(1)
while q:
  x = q.popleft()
  if not memo[x]:
    memo[x] = True
    for y in G[x]:
      if ans[y] == 0:
        ans[y] = x
        q.append(y)
print("Yes")
print("\n".join([str(x) for x in ans[2:]]))

Solution (Python):
import sys
from collections import deque


N, M = map(int, input().split())
edge = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1; b -= 1
    edge[a].add(b)
    edge[b].add(a)

INF = 10 ** 8
path = [INF] * N
prev = [0] * N

q = deque()
path[0] = 0
q.append((0, 0))

while q:
    v, s = q.popleft()
    ns = s + 1
    for nv in edge[v]:
        if path[nv] > ns:
            path[nv] = ns
            prev[nv] = v
            q.append((nv, ns))

print('Yes')
for i in range(N - 1):
    print(prev[i + 1] + 1)

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

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


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start,N):
        self.g = graph.graph
        self.N = N
        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
    
    def solve(self):
        res = []
        for i in range(1, self.N):
            res.append(self.prev[i]+1)
        return res

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
G = Graph()
for a,b in ab:
    G.add_edge(a-1,b-1)
    G.add_edge(b-1,a-1)
d = Dijkstra(G,0,n)
ans = d.solve()
print("Yes")
for i in ans:
    print(i)

Solution (Python):
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m = map(int,input().split())
G = [[] for i 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)


que = collections.deque()
que.append(0)
visited = [-1] * n
visited[0] = 0
while que:
  way = que.popleft()
  for gi in G[way]:
    if visited[gi] == -1:
      visited[gi] = way + 1
      que.append(gi)

for vi in visited:
  if vi == -1:
    print("No")
    exit()
else:
  print("Yes")
  for i in range(1,n):
    print(visited[i])

Solution (Python):
from collections import deque
N , M =[int(hoge) for hoge in input().split()]
route = [[] for i in range(N)]
for i in range(M):
    A,B = [int(hoge)-1 for hoge in input().split()]
    route[A].append(B)
    route[B].append(A)



queue = deque()
went = [-1] * N
went[0] = True
queue.append(0)
while queue:
    cur = queue.popleft()
    for togo in route[cur]:
        if went[togo] == -1:
            went[togo] = cur
            queue.append(togo)

if any([x == -1 for x in went]):
    print("No")
else:
    print("Yes")
    for w in went[1:]:
        print(w+1)

Solution (Python):
from heapq import *

def dijkstra(s, edges):
    dist = [INF] * len(edges)
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u in edges[v]:
            if dv+1 < dist[u]:
                dist[u] = dv+1
                heappush(h, (dv+1, u))
    return dist

INF = 10**9
N, M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    es[a].append(b)
    es[b].append(a)
f = [-1]*N
d = dijkstra(0, es)
for v in range(1, N):
    dv = d[v]
    for u in es[v]:
        if d[u] < dv:
            f[v] = u+1
print('Yes')
print(*f[1:], sep='\n')

Solution (Python):
from collections import deque

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

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

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
l = [[] for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
visited = [-1]*n
deq = deque([0])
c = 0
visited[0] = 0
while deq:
  cur = deq.popleft()
  c += 1
  for i in l[cur]:
    if visited[i] == -1:
      deq.append(i)
      visited[i] = cur
if c == n:
  print('Yes')
  for i in visited[1:]:
    print(i+1)
else:
  print('No')

Solution (Python):
from collections import deque

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

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

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



queue=deque()
queue.append(0)

mada=[True]*n
mada[0]=False

ans=[-1]*n

for i in range(10*n):
    
    if(len(queue)==0):
        break
    gen=queue.popleft()
    for h in heya[gen]:
        
        if(mada[h]):
            mada[h]=False
            queue.append(h)
            ans[h]=gen+1

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