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

Solution (Python):


import copy
import random
import bisect 
import fractions 
import math
import sys
import collections
from decimal import Decimal 

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

"""
N rooms
M paths

0 room is start
"""
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, M = LI()
AB = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append((a,b))

paths = {}
for i in range(N):
    paths[i] = []
for a, b in AB:
    paths[a].append(b)
    paths[b].append(a)














q = collections.deque()


q.append((0, -1))

anss = [0 for i in range(N)]
rooms = [0 for i in range(N)]
rooms[0] = 1
while len(q) > 0:
    node, p = q.popleft()

    for path in paths[node]:
        if path == p:
            continue
        if rooms[path]: 
            continue
        q.append((path, node))
        rooms[path] = 1
        anss[path] = node
print("Yes")
for ans in anss[1:]:
    print(ans + 1)

Solution (Python):


import copy
import random
import bisect 
import fractions 
import math
import sys
import collections
from decimal import Decimal 

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

"""
N rooms
M paths

0 room is start
"""
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, M = LI()
AB = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append((a,b))

paths = {}
for i in range(N):
    paths[i] = []
for a, b in AB:
    paths[a].append(b)
    paths[b].append(a)

uf = UnionFind(N)
for a,b in AB:
    uf.Unite(a,b)

ans = True
for i in range(N):
    if not uf.isSameGroup(0, i):
        ans = False

if ans == False:
    print("No")
    sys.exit()

q = collections.deque()


q.append((0, -1))

anss = [0 for i in range(N)]
rooms = [0 for i in range(N)]
rooms[0] = 1
while len(q) > 0:
    node, p = q.popleft()

    for path in paths[node]:
        if path == p:
            continue
        if rooms[path]: 
            continue
        q.append((path, node))
        rooms[path] = 1
        anss[path] = node
print("Yes")
for ans in anss[1:]:
    print(ans + 1)

Solution (Python):
from collections import deque

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

queue = deque()
landmarks[1] = 0
queue.append(1)
while len(queue) != 0:
  v = queue.popleft()
  for i in edges[v]:
    if landmarks[i] != -1:
      continue
    landmarks[i] = v
    queue.append(i)
flag = 1
for i in range(2,n+1):
  if landmarks[i] == -1:
    flag = 0
if flag:
  print('Yes')
  for i in range(2,n+1):
    print(landmarks[i])
else:
  print('No')

Solution (Python):
import sys
import time
st = time.perf_counter()


from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
D = deque([0])
visited = [False] * N
visited[0] = True
sirusi = [0] * N
while D:
    d = D.popleft()
    for i in graph[d]:
        if visited[i]: continue
        visited[i] = True
        D.append(i)
        sirusi[i] = d
print('Yes')
for i in range(1, N):
    print(sirusi[i] + 1)
    

ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Solution (Python):
from collections import deque

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

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

N, M = MI()
room = [[] for _ in range(N)]

for _ in range(M):
    A, B = MI()
    room[A - 1].append(B - 1)
    room[B - 1].append(A - 1)

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

while queue:
    u = queue.popleft()
    
    for r in room[u]:
        if ans[r] == -1:
            ans[r] = u + 1
            queue.append(r)

print("Yes")

for a in ans[1:]:
    print(a)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
sign = [-1] * n
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
D = deque([0])
visited = [False]*n
visited[0] = True
while D:
    v=D.popleft()
    for j in graph[v]:
        if visited[j]:
            continue
        visited[j] = True
        sign[j] = v
        D.append(j)

print("Yes")
for k in range(1, n):
    print(sign[k]+1)

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

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

for i in range(m):
    a, b = map(int, input().split())
    if b != 1:
        memo[a].append(b)
    if a != 1:
        memo[b].append(a)
        
signs = [-1] * (n+1)

now = [1]
cnt = 1
while cnt < n:
    next = []
    for j in now:
        roots = memo[j]
        for k in roots:
            if signs[k] == -1:
                signs[k] = j
                next.append(k)
                cnt += 1
    now = next[:]

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

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


dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

from collections import deque
d = deque()
d.append(1)

while d:
  v = d.popleft()
  
  for i in graph[v]:
    if dist[i] != -1:
      continue
    dist[i] = v
    d.append(i)
    
ans = dist[2:]
if all(d == -1 for d in dist):
  print('No')
  exit()
print('Yes')
for i in range(len(ans)):
  print(ans[i])

Solution (Python):
from collections import deque

n,m=map(int,input().split())
x=[[]for i in range(n)]
cnt=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    x[a].append(b)
    x[b].append(a)

D=deque([])
D.append(0)
visit=[False]*n
visit[0]=True

while D:
    v=D.popleft()
    for i in x[v]:
        if visit[i]:continue
        visit[i]=True
        cnt[i]=v
        D.append(i)
print("Yes")
for i in range(1,n):
    print(cnt[i]+1)

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


queue = deque([1])

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

depth[0] = depth[1] = 0

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

while queue:
    v = queue.popleft()
    for i in path[v]:
        if depth[i] == -1:
            depth[i] = depth[v] + 1
            queue.append(i)
            ans[i] = v

if -1 in depth:
    print("No")
else:
    print("Yes")
    
    
    
    print(*ans[2:], sep="\n")

Solution (Python):
from collections import defaultdict
from queue import Queue
g = defaultdict(list)
visted = defaultdict(bool)
N, M = map(int, input().split())
for i in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)

h = [-1] * (N+1)

h2 = defaultdict(list)
def solve(v):
    visited = set()
    q = Queue()
    visited.add(v)
    h[v] = 0
    h2[0].append(v)
    q.put(v)
    while not q.empty():
        v = q.get()
        for c in g[v]:
            if not c in visited:
                visited.add(c)
                h[c] = h[v] + 1
                h2[h[v]+1].append(c)
                q.put(c)

solve(1)
ans = []

for v in range(2, N+1):
    i = h[v]

    for c in g[v]:
        if h[c] == i-1:
            ans.append(c)
            break


print('Yes')
for v in ans:
    print(v)

Solution (Python):
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=[[] for i in range(a)]
for j in range(b):
  x,y=mi()
  l[x-1].append(y-1)
  l[y-1].append(x-1)
lst=[-1]*a
q=deque([0])
while q:
  s=q.popleft()
  for j in l[s]:
    if lst[j]==-1:
      lst[j]=s
      q.append(j)
print("Yes")
for k in range(a-1):
  print(lst[k+1]+1)

Solution (Python):
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=[[] for i in range(a)]
for j in range(b):
  x,y=mi()
  l[x-1].append(y-1)
  l[y-1].append(x-1)
lst=[-1]*a
q=deque([0])
while q:
  s=q.popleft()
  for j in l[s]:
    if lst[j]==-1:
      lst[j]=s
      q.append(j)
print("Yes")
for k in range(a-1):
  print(lst[k+1]+1)

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

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

from collections import deque

def bfs(Que, Dist, L, Root):    
    while Que:
        x = Que.popleft()
        d = Dist[x]
        
        for l in L[x]:
            new_x = l
            if Dist[new_x] == -1:
                Dist[new_x] = d + 1
                Root[new_x] = x
                Que.append(new_x)
    return Dist, Root
    
Que = deque()
Dist = [-1 for _ in range(N+1)]
Root = [-1 for _ in range(N+1)]

Que.append(1)
Dist[1] = 0
Dist, Root = bfs(Que, Dist, L, Root)

More0 = [r > 0 for r in Root[2:]] 
Is1 = [r == 1 for r in Root[2:]]

if all(More0) and any(Is1):
    print('Yes')
    print('\n'.join(map(str, Root[2:])))
else:
    print('No')

Solution (Python):
from collections import deque

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

for a, b in AB:
  g[a].append(b)
  g[b].append(a)

d = deque([1])
l = [0]*(N+1)
while d:
  r = d.popleft()
  for s in g[r]:
    if l[s] == 0:
      d.append(s)
      l[s] = r

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

Solution (Python):
import queue
N, M = map(int, input().split())
adj = [[]for i in range(N+1)]
parent = [-1] * (N+1)  
for m in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
q = queue.Queue()  
q.put((1, 0))  
while(not q.empty()):
    x, p = q.get()
    if parent[x] != -1:  
        continue
    parent[x] = p
    for next in adj[x]:
        if parent[next] == -1:  
            q.put((next, x))  
print('Yes')  
for p in parent[2:]:  
    print(p)

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

ans = 'No'
st = deque([1])
check = [0]*(N+1)
check[1] = 1
mark = [0]*(N+1)

while st:
  s = st.popleft()
  for t in l[s]:
    if check[t] == 0:
      mark[t] = s
      check[t] = 1
      st.append(t)
if sum(check) == N:
  ans = 'Yes'

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

Solution (Python):
import networkx as nx
N, M = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(M)]
 
G = nx.Graph()
G.add_nodes_from(range(1, N+1))
G.add_edges_from(l)
pre = nx.predecessor(G, 1)

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
g = [[] for _ 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)
q = deque([0])
pre = [-1 for _ in range(n)]
while q:
    v = q.popleft()
    for t in g[v]:
        if pre[t] == -1:
            pre[t] = v
            q.append(t)
print('Yes')
for i in range(1, n):
    print(pre[i]+1)

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

n,m = imap()
ab = np.array([iarr() for i in range(m)])
g = adj(n+1)
for i in range(m):
    aa,bb = ab[i][0],ab[i][1]
    g[aa].append(bb)
    g[bb].append(aa)

dep = iarr(n+1)
dep[1] = 1
q = col.deque([1])
route = iarr(n+1)
while q:
    now = q.popleft()
    for next in g[now]:
        if dep[next]: continue
        else:
            q.append(next)
            dep[next] = dep[now]+1
            route[next] = now

print("Yes")
for ans in route[2:]: print(ans)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
cnct = [[] for i in range(N+1)]
for _ in range(M):
  A,B = map(int,input().split())
  cnct[A].append(B)
  cnct[B].append(A)
Q = deque()
Q.append(1)
ans = [0]*(N+1)
vstd = [0]*(N+1)
while Q:
  temp = Q.popleft()
  for a in cnct[temp]:
    if vstd[a] == 0:
      ans[a] = temp
      vstd[a] = 1
      Q.append(a)
print('Yes')
for a in ans[2:]:
  print(a)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
cnct = [[] for i in range(N+1)]
for _ in range(M):
  A,B = map(int,input().split())
  cnct[A].append(B)
  cnct[B].append(A)
Q = deque()
Q.append(1)
ans = [0]*(N+1)
vstd = [0]*(N+1)


while Q:
  temp = Q.popleft()
  for a in cnct[temp]:
    if vstd[a] == 0:
      ans[a] = temp
      vstd[a] = 1
      Q.append(a)
print('Yes')
for a in ans[2:]:
  print(a)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
cnct = [[] for i in range(N+1)]
for _ in range(M):
  A,B = map(int,input().split())
  cnct[A].append(B)
  cnct[B].append(A)
Q = deque()
Q.append(1)
ans = [0]*(N+1)
vstd = [0]*(N+1)
while Q:
  temp = Q.popleft()
  for a in cnct[temp]:
    if vstd[a] == 0:
      ans[a] = temp
      vstd[a] = 1
      Q.append(a)
print('Yes')
for a in ans[2:]:
  print(a)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
ab=[[] for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  ab[a].append(b)
  ab[b].append(a)
ans=[-1]*(N+1)
que=deque([1])
while que:
  q=que.popleft()
  for i in ab[q]:
    if ans[i]==-1:
      que.append(i)
      ans[i]=q
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Solution (Python):
import queue
n,m = map(int,input().split())
way = [set() for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    way[a-1].add(b-1)
    way[b-1].add(a-1)
    
guide = [-1]*n
guide[0] = 0
q = queue.Queue() 
q.put((0,0))
while not q.empty():
    room,cost = q.get()
    for k in way[room]: 
        if guide[k] == -1:
            guide[k] = room
            q.put((k,cost+1))
            way[k].discard(room)
            
if -1 in guide:
    print('No')
else:
    print('Yes')
    for i in guide[1:]:
        print(i+1)

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)
par = [0]*(n+1)
visited = [0]*(n+1)
root = 1
visited[root] = 1
q = deque([root])
while q:
  v = q.popleft()
  for w in links[v]:
    if visited[w]:
      continue
    visited[w] = 1
    par[w] = v
    q.append(w)
    
print('Yes')
print(*par[2:], sep='\n')

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def BFS(n,m,table,dist):
    next = deque([0])
    while next:
        tmp = next.popleft()
        for rep in table[tmp]:
            if dist[rep]==-1:
                dist[rep] = tmp+1
                next.append(rep)
    return not -1 in dist

def main():
    n,m = IL()
    table = [[] for _ in range(n)]
    for _ in range(m):
        a,b = IL()
        table[a-1].append(b-1)
        table[b-1].append(a-1)
    dist = [-1]*n
    dist[0] = 0
    if BFS(n,m,table,dist):
        print('Yes')
        for i in range(1,len(dist)):
            print(dist[i])
    else:  print('No')
    return

if __name__=='__main__':
    main()

Solution (Python):
import heapq
import numpy as np

N, M = [int(x) for x in input().split(" ")]

e = {i: [] for i in range(N)}
for _ in range(M):
  a, b = [int(x)-1 for x in input().split(" ")]
  e[a].append(b)
  e[b].append(a)

d = np.ones(N, dtype=int) * -1
q = [0]
while len(q) != 0:
  v = q.pop(0)
  for ne in e[v]:
    if d[ne] == -1:
      d[ne] = v
      q.append(ne)

print("Yes")



for p in d[1:]:
  print(p+1)

Solution (Python):
import numpy as np
N, M = map(int, input().split(" "))

goto = {i: [] for i in range(1, N+1)}
sign = np.zeros(N, dtype=int)
for _ in range(M):
  A, B = map(int, input().split(" "))
  goto[A].append(B)
  goto[B].append(A)



visited = set([1])
queue = [1]
while len(queue) > 0:
  v = queue.pop(0)
  for nex in goto[v]:
    if nex in visited:
      continue
    sign[nex-1] = v
    queue.append(nex)
    visited.add(nex)
print("Yes")
for s in sign[1:]:
  print(s)

Solution (Python):
from collections import deque

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

adj = [[] for i in range(n+1)]
dist = [-1]*(n+1)

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

d = deque([[1,0]])

while len(d) > 0:
    x,y = d.popleft()
    if dist[x] != -1:
        continue
    
    dist[x] = y
    
    for n in adj[x]:
        if dist[n] == -1:
            d.append([n,x])

print("Yes")

for i in dist[2:]:
    print(i)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}

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

q = deque([1])
INF = 10**20
dist = [INF]*(N+1)
dist[1] = 0
par = [-1]*(N+1)
par[1] = 0

while q:
    a = q.popleft()
    for b in d[a]:
        if dist[b] > dist[a]+1:
            dist[b] = dist[a]+1
            par[b] = a
            q.append(b)

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

Solution (Python):

from collections import deque

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

while len(que)>0:
    k = que.popleft()
    for x in route[k]:
        if ans[x]<0:
            ans[x] = k
            que.append(x)

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

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

done=[False for i in range(n)]
ans=[-1 for i in range(n)]
def bfs():
  que=[0]

  while(que):
    now=que.pop(0)
    done[now]=True
    for i in l[now]:
      if done[i]==False:
        que.append(i)
        done[i]=True
        ans[i]=now+1
bfs()
print("Yes")
print(*ans[1:])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def BFS(n,m,table,dist):
    next = deque([0])
    while next:
        tmp = next.popleft()
        for rep in table[tmp]:
            if dist[rep]==-1:
                dist[rep] = tmp+1
                next.append(rep)
    return not -1 in dist

def main():
    n,m = IL()
    table = [[] for _ in range(n)]
    for _ in range(m):
        a,b = IL()
        table[a-1].append(b-1)
        table[b-1].append(a-1)
    dist = [-1]*n
    dist[0] = 0
    if BFS(n,m,table,dist):
        print('Yes')
        for i in range(1,len(dist)):
            print(dist[i])
    else:  print('No')
    return

if __name__=='__main__':
    main()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
A=[set() for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  A[a-1].add(b)
  A[b-1].add(a)
visit=[0]*n
visit[0]=n+1
stack=deque()
stack.append(1)
while stack:
  now=stack.popleft()
  for j in A[now-1]:
    if visit[j-1]==0:
      visit[j-1]=now
      stack.append(j)
if min(visit)>0:
  print('Yes')
  for j in range(1,n):
    print(visit[j])
else:
  print('No')

Solution (Python):

"""
Created on Sun Jun 14 16:45:05 2020

@author: NEC-PCuser
"""

from collections import deque

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

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

for i in range(M):
    a_tmp, b_tmp = map(int, input().split())
    g[a_tmp - 1].append(b_tmp - 1)
    g[b_tmp - 1].append(a_tmp - 1)
    
queue = deque([0])

d = [-1] * N
d[0] = 0

while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] == -1:
            d[i] = v
            queue.append(i)

out_flg = True
for i in d:
    if i == -1:
        out_flg = False
        break

if out_flg is False:
    print("No")
else:
    print("Yes")
    for i in range(1, len(d)):
        print(d[i] + 1)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
edge=[[] for i in range(N)]
visited=[-1 for i in range(N)]
dist=[1000000000 for i in range(N)]
last=[-1 for i in range(N)]
i=0
dist[0]=0
for i in range(M):
    A,B=map(int,input().split())
    edge[A-1].append(B-1)
    edge[B-1].append(A-1)
Q=deque()
Q.append(0)
while Q:
    i=Q.popleft()
    if visited[i]==-1:
        for j in edge[i]:
            if dist[j]>dist[i]+1:
                dist[j]=dist[i]+1
                last[j]=i+1
            if visited[j]==-1:
                Q.append(j)
    visited[i]=1
print("Yes")
for i in range(1,N):
	print(last[i])

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

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

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

queue = [0]
isSearched = [False]*n
isSearched[0] = True
ans = [-1]*n
def bfs():
    while(queue):
        now = queue.pop(0)

        for t in target[now]:
            if(isSearched[t]):
                continue
            ans[t] = now
            queue.append(t)
            isSearched[t] = True
bfs()
print('Yes')
for i in range(n):
    if(i==0):
        continue
    print(ans[i]+1)

Solution (Python):

"""AtCoder Beginner Contest 168: D - .. (Double Dots)
https://atcoder.jp/contests/abc168/tasks/abc168_d
"""


def main():
    N, M = map(int, input().split())

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

    dist = [-1]*N
    q = [0]
    while q:
        v = q.pop(0)
        for i in to[v]:
            if dist[i] != -1:
                continue
            dist[i] = v
            q.append(i)

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


if __name__ == '__main__':
    main()

Solution (Python):

"""AtCoder Beginner Contest 168: D - .. (Double Dots)
https://atcoder.jp/contests/abc168/tasks/abc168_d
"""


def main():
    N, M = map(int, input().split())

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

    p = [-1]*N
    q = [0]
    while q:
        v = q.pop(0)
        for u in to[v]:
            if p[u] == -1:
                p[u] = v
                q.append(u)
    print('Yes')
    for i in range(1, N):
        print(p[i]+1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N)]
R = [0]*N
for m in range(M):
    A,B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
d = deque()
for n in G[0]:
    d.append(n)
    R[n]=1
while len(d)>0:
    i = d.popleft()
    for j in range(len(G[i])):
        if R[G[i][j]] == 0 and G[i][j]!=0:
            d.append(G[i][j])
            R[G[i][j]]=i+1
for n in range(1,N):
    if R[n]==0:
        print("No")
        sys.exit()
print("Yes")
for n in range(1,N):
    print(R[n])

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

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

l = [0]*(n+1)
num = [1]

while num:
    v = num.pop(0)
    for i in lab[v]:
        if not l[i]:
            l[i] = v
            num.append(i)
            
if not 0 in l[2:]:
    print("Yes")
    for i in range(2, n+1):
        print(l[i])
else:
    print("No")

Solution (Python):

from collections import deque


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, m = xnxn()
a = xnxn(m)

graph = [[] for _ in range(n+1)]
for g in a:
    graph[g[0]].append(g[1])
    graph[g[1]].append(g[0])



d = deque([1])
rout = [0]*(n+1)
while d != deque([]):
    pos = d.popleft()
    for i in graph[pos]:
        if rout[i] == 0:
            rout[i] = pos
            d.append(i)


if rout != [0]*(n+1):
    print("Yes")
    for i in rout[2:]:
        print(i)
else:
    print("No")

Solution (Python):
import sys
sys.setrecursionlimit(2000000)
n,m=map(int,input().split())
path={i:[] for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  path[a-1].append(b)
  path[b-1].append(a)
sign=[0]*n

def bfs(poslist,sign):
  if len(poslist)==0:
    return sign
  nex=[]
  for pos in poslist:
    lis = [x for x in path[pos-1] if sign[x-1]==0]
    for i in lis:
      sign[i-1]=pos
      nex.append(i)
  return bfs(nex,sign)
      
  
sign=bfs([1],sign)
print('Yes')
for i in range(1,n):
  print(sign[i])

Solution (Python):
import sys
sys.setrecursionlimit(2000000)
n,m=map(int,input().split())
path={i:[] for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  path[a-1].append(b)
  path[b-1].append(a)
sign=[0]*n

def bfs(poslist,sign):
  if len(poslist)==0:
    return sign
  nex=[]
  for pos in poslist:
    lis = [x for x in path[pos-1] if sign[x-1]==0]
    for i in lis:
      sign[i-1]=pos
      nex.append(i)
  return bfs(nex,sign)
      
  
sign=bfs([1],sign)
print('Yes')
for i in range(1,n):
  print(sign[i])

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

from collections import deque

class Node:
    def __init__(self, id_=0):
        self.id = id_
        self.link = []
        self.check = False

def main():
    N, M = map(int, input().split())

    nodes = [Node(i) for i in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    
    pre = [-1] * N
    q = deque()
    q.append(nodes[0])
    nodes[0].check = True
    while len(q) > 0:
        node = q.popleft()
        for nex in node.link:
            if not nex.check:
                nex.check = True
                pre[nex.id] = node.id
                q.append(nex)
    
    print("Yes")
    for i in range(1, N):
        print(pre[i]+1)

if __name__ == "__main__":
    main()