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 = 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)

d = [0] * (n + 1)
q=deque()
q.append(1)

while q:
    v = q.popleft()
    for j in graph[v]:
        if not d[j]:
            q.append(j)
            d[j] = v
print('Yes')
for x in range(2,n+1):
    print(d[x])

Solution (Python):


class Room:
    sign = -1
    distance = -1
    def __init__(self):
        self.connected = set()
    def print(self, no: str):
        print(f"{no}: sign={self.sign} dist={self.distance} / {self.connected}")

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

Rooms = []
for i in range(N+1):
    Rooms.append(Room())

for i in range(M):
    (A, B) = map(int, input().split(" "))
    Rooms[A].connected.add(B)
    Rooms[B].connected.add(A)

Rooms[0].distance = 0
Rooms[1].distance = 0
target = [1]

while(len(target)):
    new_target = []
    for t in target:
        for c in Rooms[t].connected:
            if Rooms[c].distance == -1 or Rooms[t].distance + 1 < Rooms[c].distance:
                Rooms[c].sign = t
                Rooms[c].distance = Rooms[t].distance + 1
                new_target.append(c)
    target = list(set(new_target))

if all([r.distance != -1 for r in Rooms]):
    print("Yes")
    for i in range(2, N+1):
        print(Rooms[i].sign)
else:
    print("No")

Solution (Python):
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
 
g=nx.Graph() 
g.add_edges_from(s) 
di=nx.predecessor(g,source=1)
 
print("Yes")
for x in range(2,n+1):
      print(di[x][0])

Solution (Python):
import sys, queue
def input():
    return list(map(int, sys.stdin.readline().strip().split()))
 
n, m = input()
mem = [10 ** 6 for _ in range(n + 1)] 
adj = [[] for _ in range(n + 1)]
q = queue.Queue()
for i in range(m):
    a, b = input()
    adj[b].append(a)
    adj[a].append(b)
    if b == 1: 
        q.put(a)
        mem[a] = 1
    if a == 1: 
        q.put(b)
        mem[b] = 1
mem[1] = -1
while not q.empty():
    v = q.get()
    for vv in adj[v]:
        if mem[vv] != 10 ** 6: continue
        mem[vv] = v
        q.put(vv)
 
if 10 ** 6 in mem[2:]:
    print('No')
else:
    print('Yes', *mem[2:], sep='\n')

Solution (Python):
from collections import deque

n, m = map(int, input().split())
rooms = [[] for i in range(n + 1)]

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

q = deque()
q.append(1)
signs = [-1]*(n + 1)
signs[1] = 0

while q:
    rnum = q.popleft()
    for i in rooms[rnum]:
        if signs[i] == -1:
            signs[i] = rnum
            q.append(i)

print("Yes")

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

Solution (Python):
import collections

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)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
ans=[0]*(n+1)
while len(q)!=0:
 v=q.popleft()
 for u in g[v]:
   if check[u]==0: 
     check[u]=1
     ans[u]=v
     q.append(u)
print('Yes')
for i in range(2,n+1):
 print(ans[i])

Solution (Python):
def BFS(K,edges,N):
  INF = 10**10
  roots=[ [] for i in range(N)]
  for a,b in edges:
    roots[a-1]+=[b-1]
    roots[b-1]+=[a-1]
  dist=[INF]*N
  pre = [-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(0)
    for i in roots[label]:
      if dist[i]==INF:
        dist[i]=dist[label]+1
        pre[i]=label
        stack+=[i]

  return pre
 
N,M=map(int,input().split())
edges=[]
for i in range(M):
  edges+=[list(map(int,input().split()))]


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

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 = [False] * n
ans = [0] * n

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

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

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

for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d[a].add(b)
  d[b].add(a)
dist=[-1]*n
dist[0]=0
prev=[-1]*n
queue=deque()
queue.append(0)

while queue:
  q=queue.popleft()
  for next in d[q]:
    if dist[next]!=-1:
      continue
    dist[next]=dist[q]+1
    prev[next]=q
    queue.append(next)

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

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n+1)]
    for i in range(m):
        a,b=map(int,readline().split())
        G[a].append(b)
        G[b].append(a)

    ans=[0]*(n+1)
    flags=[False]*(n+1)
    flags[1]=True
    d=deque([1])
    while len(d)>0:
        now=d.popleft()
        v=now
        for u in G[v]:
            if flags[u]==False:
                flags[u]=True
                ans[u]=v
                d.append(u)

    print("Yes")
    for i in range(2,n+1):
        print(ans[i])
        
if __name__=="__main__":
    main()

Solution (Python):
import collections

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)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
ans=[0]*(n+1)
while len(q)!=0:
 v=q.popleft()
 for u in g[v]:
   if check[u]==0:
     check[u]=1
     ans[u]=v
     q.append(u)
print('Yes')
for i in range(2,n+1):
 print(ans[i])

Solution (Python):
n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
br = [0 for i in range(n)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
cr = [0]
dr = []
for r in cr:
    for i in ar[r]:
        if br[i] == 0:
            br[i] = r + 1
            cr.append(i)
print("Yes")
for i in range(1,n):
    print(br[i])

Solution (Python):
import queue
N, M = map(int, input().split())
E = [set() for i in range(N)]
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  E[A].add(B)
  E[B].add(A)

V = [-1]*N
q = queue.Queue()
q.put(0)
while not q.empty():
  p = q.get()
  s = E[p]
  for i in s:
    if V[i] < 0:
      V[i] = p
      q.put(i)

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

Solution (Python):


import sys
readline = sys.stdin.readline

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

from collections import deque
q = deque([])
q.append([0,-1])
ans = [-1 for i in range(N)]
while q:
  v,parent = q.popleft()
  if ans[v] != -1:
    continue
  ans[v] = parent + 1
  for child in G[v]:
    if child == parent:
      continue
    q.append([child,v])

for i in range(1,len(ans)):
  if ans[i] == -1:
    print("No")
    exit(0)
print("Yes")
for i in range(1,len(ans)):
  print(ans[i])

Solution (Python):
from collections import deque

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

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

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

visited = [-1] * N
q = deque([0])

while q:
  p = q.popleft()
  for node in g[p]:
    if visited[node] == -1:
      visited[node] = p + 1
      q.append(node)

print ('Yes')
print ('\n'.join(map(str, visited[1:])))

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

b = [[] for i in range(n)]
for i in range(m):
    a=list(map(int,input().split()))
    b[a[1]-1].append(a[0])
    b[a[0]-1].append(a[1])
    
c = [-1 for i in range(n)]
c[0] = 0
q = deque([1])
now = 0
count = 0
while q:
    
    count = count + 1
    if count > n:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        
        
        if c[b[now][i] - 1] == -1:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            
            

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

Solution (Python):
from collections import deque
newarr = input()
newarr = newarr.split()
n = int(newarr[0])
m = int(newarr[1])
dicts = {}
ans = [0] * (n + 1)
for line in range(m):
    newarr = input()
    newarr = newarr.split()
    froom = int(newarr[0])
    sroom = int(newarr[1])
    if froom not in dicts:
        dicts[froom] = []
    if sroom not in dicts:
        dicts[sroom] = []
    dicts[froom].append(sroom)
    dicts[sroom].append(froom)
queue = deque([])
if 1 not in dicts:
    print("No")
else:
    ans[1] = 1
    curarr = dicts[1]
    for i in curarr:
        queue.append(i)
        ans[i] = 1 
    while queue:
        curitem = queue.popleft()
        if curitem not in dicts:
            continue 
        curarr = dicts[curitem]
        for i in curarr:
            if ans[i] == 0:
                ans[i] = curitem 
                queue.append(i)

    finalans = []
    flag = 0 
    for i in range(2, n + 1):
        if i == 0 :
            flag = 1 
            break 
        finalans.append(ans[i])
    if flag == 1:
        print("No")
    else:
        print("Yes")
        for i in finalans:
            print(i)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
candidate = [[] for i in range(n)]
parent = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    candidate[a].append(b)
    candidate[b].append(a)
q = deque([0])
visited = [False] * n
visited[0] = True
while len(q) > 0:
    v = q.popleft()
    for i in candidate[v]:
        if visited[i]:
            continue
        visited[i] = True
        parent[i] = v
        q.append(i)
print("Yes")
for i in range(1, n):
    print(parent[i]+1)

Solution (Python):
from collections import deque
def bfs(graph,N):
   que=deque([0])
   visited=[0]*N
   visited[0]=1
   while que:
      node=que.popleft()
      for i in graph[node]:
         if not visited[i]:
            visited[i]=node+1
            que.append(i)
   return visited
N,M= list(map(int,input().split()))
l=[[] for i in range(N)]
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   l[b].append(a)
ans=bfs(l,N)[1:]
if all(ans):
   print("Yes")
   print(*ans,sep="\n")
else:
   print("No")

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

rdic = [0]*(N)
d = deque()
d.append(1)
c = 0
ans = [0]*N
while len(d)>0:
    getlist = T[d[0]-1]
    for i in getlist:
        if rdic[i-1]==0:
            rdic[i-1] = d[0]
            d.append(i)
    d.popleft()
print('Yes')
for n in range(2,N+1):
    print(rdic[n-1])

Solution (Python):




from collections import deque

def bfs(graph,N,source):
    visited=[0]*N
    visited[source]=1
    q=deque([source])
    while len(q)>0:
        node=q.popleft()
        for i in graph[node]:
            if visited[i]==0:
                visited[i]=node+1
                q.append(i)
    return visited

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)
aw=bfs(graph,n,0)
print('Yes')
for i in range(1,n):
    print(aw[i])

Solution (Python):
from collections import deque

n, m = map(int, input().split())
rooms = [[] for i in range(n + 1)]

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

q = deque()
q.append(1)
signs = [-1]*(n + 1)
signs[1] = 0

while q:
    rnum = q.popleft()
    for i in rooms[rnum]:
        if signs[i] == -1:
            signs[i] = rnum
            q.append(i)

print("Yes")

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

Solution (Python):
n,m=map(int,input().split())
route=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    route[a].append(b)
    route[b].append(a)
from collections import deque
q=deque()
q.append(1)
sigh=[0]*(n+1)
depth=[0]*(n+1)
depth[1]=0
while q:
    a=q.popleft()
    for i in route[a]:
        if depth[i]==0 or depth[i]>depth[a]+1:
            if i!=1:
                depth[i]=depth[a]+1
                q.append(i)
                sigh[i]=a
print('Yes')
for i in range(2,n+1):
    print(sigh[i])