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())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStatus = [False for i in range(n)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStatus


def calculate(n, nodes, nodeStatus):
    nodeMarks = [-1 for i in range(n)]

    q = deque()

    q.append((0, -1))

    while len(q) > 0:
        currentNode, parentNode = q.popleft()

        if nodeStatus[currentNode] == True:
            continue

        nodeStatus[currentNode] = True
        nodeMarks[currentNode] = parentNode
        childNodes = nodes[currentNode]

        for childNode in childNodes:
            q.append((childNode, currentNode))

    minusNumber = nodeMarks.count(-1)
    if minusNumber > 1:
        print("No")
        return

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


nodes, nodeStatus = prepare(N, M, ARR)

calculate(N, nodes, nodeStatus)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStatus = [False for i in range(n)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStatus


def calculate(n, nodes, nodeStatus):
    nodeMarks = [-1 for i in range(n)]

    q = deque()

    q.append((0, -1))

    while len(q) > 0:
        currentNode, parentNode = q.popleft()

        if nodeStatus[currentNode] == True:
            continue

        nodeStatus[currentNode] = True
        nodeMarks[currentNode] = parentNode
        childNodes = nodes[currentNode]

        for childNode in childNodes:
            if nodeStatus[childNode] == True:
                continue
            q.append((childNode, currentNode))

    minusNumber = nodeMarks.count(-1)
    if minusNumber > 1:
        print("No")
        return

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


nodes, nodeStatus = prepare(N, M, ARR)

calculate(N, nodes, nodeStatus)

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

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

sign=[-1]*n
sign[0]=0
work=[]
work_next=graph[0]
for x in work_next:
    sign[x]=0


while work_next:
    work=work_next[:]
    work_next=[]
    for x in work:
        for y in graph[x]:
            if sign[y]>=0 : continue
            if y in work_next : continue
            sign[y]=x
            work_next.append(y)

if -1 in sign : print("No");exit()
print("Yes")
for i in range(1,n):
    print(sign[i]+1)

Solution (Python):


import itertools
import collections





def main():
    n, m = input_list()
    rooms = []
    for _ in range(m):
        rooms.append(input_list())
    prev = [0]*n
    to_list = [[] for i in range(n)]
    for a, b in rooms:
        to_list[a-1].append(b-1)
        to_list[b-1].append(a-1)
    next_q = collections.deque()
    flags = [-1] * n
    flags[0] = 999
    next_q.append(0)
    while next_q:
        cur = next_q.popleft()
        for room in to_list[cur]:
            if flags[room] == -1:
                flags[room] = cur
                next_q.append(room)
    print('Yes')
    for i in range(1, n):
        print(flags[i]+1)


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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
print("Yes")

N,M=map(int,input().split())
lst=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    lst[a-1].append(b-1)
    lst[b-1].append(a-1)
q=deque(lst[0])
go=[None]*N
for i in lst[0]:
    go[i]=0
while q:
    v=q.popleft()
    for new in lst[v]:
        if go[new]==None:
            go[new]=v
            q.append(new)
for i in go[1:]:
    print(i+1)

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

arrow = [-1]*(n+1)
d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if arrow[i]!=-1:
            continue
        arrow[i] = v
        d.append(i)
    

print('Yes')
print(*arrow[2:], sep='\n')

Solution (Python):
from collections import deque
N, M = map(int, input().split())
table = []
for i in range(N):
    table.append([])
for i in range(M):
    Ai, Bi = map(int, input().split())
    table[Ai - 1].append(Bi - 1)
    table[Bi - 1].append(Ai - 1)

cost = [1000000] * N
queue = [0]
counter = 0
cost[0] = 0
answer = [-1] * N
answer[0] = 0
while counter < len(queue):
    current = queue[counter]
    counter += 1

    for n in table[current]:
        if cost[current] + 1 < cost[n]:
            cost[n] = cost[current] + 1
            answer[n] = current
            queue.append(n)
print('Yes')
for a in map(lambda x: x + 1, answer[1:]):
    print(a)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m = map(int, input().split())
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

from collections import deque

def bfs(graph, queue, dist, prev):
    while queue:
        current = queue.popleft()

        for c in graph[current]:
            if dist[c] != -1:
                continue
            else:
                dist[c] = dist[current] + 1
                prev[c] = current
                queue.append(c)

queue = deque([1])
dist = [0] + [-1] * n
prev = [0] + [-1] * n
dist[1] = 0
prev[1] = 0
bfs(graph, queue, dist, prev)

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

Solution (Python):
from collections import deque

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

neighbor_list = [[] for _ in range(N+1)]
for ab in AB:
    neighbor_list[ab[0]].append(ab[1])
    neighbor_list[ab[1]].append(ab[0])


parent_array = [-1]*(N+1)
parent_array[1] = 0
d = deque([1])
while len(d)!=0:
    v = d.popleft()
    for ch in neighbor_list[v]:
        if parent_array[ch] == -1:
            parent_array[ch] = v
            d.append(ch)

print('Yes')
for i in parent_array[2:]:
    print(i)

Solution (Python):
from collections import deque

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

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

ans = [-1] * n
ans[0] = 0
q = deque([(0, 0)])
while q:
    room, prev = q.popleft()
    for next_ in links[room]:
        if ans[next_] < 0:
            ans[next_] = room
            q.append((next_, room))

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

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

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


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


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

q = deque([])
q.append(1)

while len(q) > 0:
    v = q.popleft()
    

    
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        point[i] = v
        q.append(i)

if - 1 not in set(point):
    print('Yes')
    for k in point[2::]:
        print(k)
else:
    print('No')

Solution (Python):

from itertools import dropwhile, takewhile
def main():
    N, M = list(map(int, input().split()))
    lis = [list(map(int, input().split())) for _ in range(M)]
    
    edge = [[] for _ in range(N+1)]
    
    for a,b in lis:
        edge[a].append(b)
        edge[b].append(a)
        
    ans = [0] * (N+1)
    visited = {0}
    stack = [1]
    for i in stack:
        for j in edge[i]:
            if j in visited:
                continue
            stack.append(j)
            
            visited.add(j)
            
            ans[j]=i
    print("Yes")
    for k in ans[2:]:
        print(k)


if __name__ == '__main__':
    
    main()

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

ans = [-1] * n
from collections import deque
d = deque([0])
while d:
    u = d.popleft()
    for v in G[u]:
        if ans[v] == -1:
            ans[v] = u
            d.append(v)

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

Solution (Python):
n,m = map(int, input().split())
neighbors = {key:[] for key in range(1, n+1)}
answers = {key:0 for key in range(1, n+1)}
answers[1] = 1
for i in range(m):
    a,b = map(int, input().split())
    neighbors[a].append(b)
    neighbors[b].append(a)

def register(hs):
    newhs = []
    for h in hs:
        for i in neighbors[h]:
            if answers[i] == 0:
                answers[i] = h
                newhs.append(i)
    return newhs

hosts = [1]
while True:
    hosts = register(hosts)
    if len(hosts) == 0:
        break

flag = 0
for key, item in answers.items():
    if item == 0:
        flag = 1
if flag == 0:
    print("Yes")
    for key, item in answers.items():
        if key != 1:
            print(item)
else:
    print("No")

Solution (Python):
def dijkstra(v, G):
    import heapq

    ret = [10 ** 10] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w in G[u]:
                if ret[w] > ret[u] + 1:
                    ret[w] = ret[u] + 1
                    heapq.heappush(q, (ret[w], w))
    return ret


N, M = map(int, input().split())
G, ans = {i: [] for i in range(N)}, [-1] * N
for _ in range(M):
    A, B = map(int, input().split())
    G[A - 1].append(B - 1)
    G[B - 1].append(A - 1)

d = dijkstra(0, G)
for a in range(N):
    for b in G[a]:
        if d[a] - d[b] == 1:
            ans[a] = b + 1

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
adj=[[] for _ in range(n)]
for _ in range(m):
  a,b =map(int,input().split())
  a-=1
  b-=1
  adj[a].append(b)
  adj[b].append(a)
ans=[0]*n
que=deque([])
que.append(0)
while que:
  e=que.popleft()
  for i in adj[e]:
    if ans[i]!=0:
      continue
    ans[i]=e+1
    que.append(i)
print("Yes")
for i in range(1,n):
  print(ans[i])

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

m = [[] for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  m[a].append(b)
  m[b].append(a)
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in m[c]:
    if dp[i] == 0 :
      dp[i] = c+1
      que.append(i)



print('Yes')
[print(dp[i]) for i in range(1,n)]

Solution (Python):
from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])

Solution (Python):

from collections import deque
n, m = map(int, input().split())
ans = [0] * (n+1)
g = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

nque = deque([1])
while nque:
    now_cave = nque.popleft()
    for next_cave in g[now_cave]:
        if ans[next_cave] == 0:
            ans[next_cave] = now_cave
            nque.append(next_cave)


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

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)

dist = [[-1,0] for _ in range(n+1)]
dist[0][0] = 0
dist[1][0] = 0

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i][0] != -1:
            continue
        dist[i][0] = dist[v][0] + 1
        dist[i][1] = v
        d.append(i)

ans = dist[2:]

print('Yes')
for j in range(n-1):
    print(ans[j][1])

Solution (Python):
N, M = map(int, input().split())
nextroom = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  nextroom[A-1].append(B-1)
  nextroom[B-1].append(A-1)

sgn = [-1 for _ in range(N)]
sgn[0] = 0

depth = [float('inf') for _ in range(N)]
depth[0] = 0

now = [0]
nextvisit = []
for j in range(1, M+1):
  for n in now:
    for i in nextroom[n]: 
      if depth[i] > j:
        nextvisit.append(i)
        sgn[i] = n
        depth[i] = j
  now = [] + nextvisit
  nextvisit = []

if -1 in sgn:
  print('No')
else:
  print('Yes')
  for k in range(1, len(sgn)):
    print(sgn[k]+1)

Solution (Python):
N, M = map(int, input().split())
nextroom = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  nextroom[A-1].append(B-1)
  nextroom[B-1].append(A-1)

sgn = [-1 for _ in range(N)]
sgn[0] = 0

depth = [float('inf') for _ in range(N)]
depth[0] = 0

now = [0]
nextvisit = []
for j in range(1, M+1):
  for n in now:
    for i in nextroom[n]: 
      if depth[i] > j:
        nextvisit.append(i)
        sgn[i] = n
        depth[i] = j
  now = [] + nextvisit
  nextvisit = []

if -1 in sgn:
  print('No')
else:
  print('Yes')
  for k in range(1, len(sgn)):
    print(sgn[k]+1)

Solution (Python):
from collections import deque

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)
    g[B-1].append(A)

ans = [-1] * N
ans[0] = 0
d = deque([1])
while len(d) != 0:
    now = d[0]
    d.popleft()
    for i in g[now-1]:
        if ans[i-1] != -1:
            continue
        ans[i-1] = now
        d.append(i)

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

Solution (Python):
from collections import deque

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



path_list = [[] for i in range(N + 1)]


for i in range(M):
    a, b = list(map(int, input().split()))
    path_list[a].append(b)
    path_list[b].append(a)

queue = deque([1])
d = [None] * (N + 1)

while queue:
    
    v = queue.popleft()
    
    for i in path_list[v]:
        if d[i] is None:
            d[i] = v
            queue.append(i)

print("Yes")

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

Solution (Python):
inlist=input("").split(" ")
n=int(inlist[0])
m=int(inlist[1])
lista=[]
listb=[]
for i in range(n):
    lista+=[[]]
    listb+=[-1]
listb[0]=-2

listnum=[0]
for i in range(m):
    inlist=input("").split(" ")
    s=int(inlist[0])
    t=int(inlist[1])
    lista[s-1]+=[t-1]
    lista[t-1]+=[s-1]
k=0
while(k<len(listnum)):
    for i in lista[listnum[k]]:
        
        if(listb[i]==-1):
            listb[i]=listnum[k]
            listnum+=[i]
    k+=1

if (-1 in listb):
    print("No")
else:
    print("Yes")
    for i in listb[1:]:
        print(i+1)

Solution (Python):
import queue
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 = queue.Queue()
q.put(0)
d = [-1]*n
d[0] = 0

while not q.empty():
    v = q.get()
    for i in g[v]:
        if d[i] != -1:
            continue
        d[i] = v
        q.put(i)
if -1 in d:
    print("No")
else:
    print("Yes")
    for i in d[1:]:
        print(i+1)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

n,m = I()
g = [[] for _ in range(n)]
for i in range(m):
    a,b = I()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = deque([0])
d = [-1]*n
d[0] = 0
while q:
    v = q.popleft()
    for i in g[v]:
        if d[i] != -1:
            continue
        d[i] = v
        q.append(i)
if -1 in d:
    print("No")
else:
    print("Yes")
    for i in d[1:]:
        print(i+1)

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])
d = [-1]*n
d[0] = 0
while q:
    v = q.popleft()
    for i in g[v]:
        if d[i] != -1:
            continue
        d[i] = v
        q.append(i)
if -1 in d:
    print("No")
else:
    print("Yes")
    for i in d[1:]:
        print(i+1)

Solution (Python):
N,M=list(map(int,input().split()))
 
g=[[] for i in range(N+1)]
 
for i in range(M):
	a,b=list(map(int,input().split()))
	g[a].append(b)
	g[b].append(a)
 
from collections import deque
 
queue = deque([1])
d = [None] * (N+1)
while queue:
	v = queue.popleft()
	for i in g[v]:
		if d[i] is None:
			d[i] = v
			queue.append(i)
 
print("Yes")
print(*d[2:],sep='\n')

Solution (Python):
from collections import deque

def bfs(graph, visited, ss):
  queue = deque([ss])
  visited[ss] = 0
  ans = [0]*n
  while queue:
    s = queue.popleft()
    for new_s in graph[s] :
      if visited[new_s] == -1:
        
        visited[new_s] = visited[s] + 1
        queue.append(new_s)
        ans[new_s] = s
  return ans

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

visited = [-1]*n
ans = bfs(graph, visited, 0)

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

Solution (Python):
from collections import deque

n, m = [int(w) for w in input().split()]
links = [[] for i in range(n + 1)]
mark = [-1] * (n + 1)

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

q = deque([1])
while q:
    now = q.popleft()
    for l in links[now]:
        if mark[l] == -1:
            q.append(l)
            mark[l] = now

if -1 in mark[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join([str(w) for w in mark[2:]]))

Solution (Python):
from collections import defaultdict
from collections import deque
N, M = map(int, input().split())
edges = defaultdict(list)
ans = [0]*(N+1)
num = 1
q = deque([1])
currentdepth = {1}
nextdepth = set()
for _ in range(M):
  a, b = map(int, input().split())
  edges[a].append(b)
  edges[b].append(a)
while q:
  current = q.popleft()
  for nextver in edges[current]:
    if ans[nextver]==0:
      q.append(nextver)
      ans[nextver] = current
print('Yes')
print(*(ans[2:]),sep='\n')

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

q = deque([1])
while q:
  fr = q.popleft()
  for i in r[fr]:
    if ans[i] != 0:
      continue
    ans[i] = fr
    q.append(i)
print("Yes")
for i in ans[2:]:
  print(i)

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

    for i in range(m):
        src, dst = (int(i) for i in input().split())
        graph[src].append(dst)
        graph[dst].append(src)

    def bfs():
        st = [1] 
        pptr = { 1: 0 }

        while st:
            room = st.pop(0)
            for dest_room in graph[room]:
                if dest_room in pptr:
                    continue
                st.append(dest_room)
                pptr[dest_room] = room

        return pptr

    pptr = bfs()
    if len(pptr) != n:
        print('No')

    else:
        print('Yes')
        for i in sorted(pptr.keys()):
            if i == 1:
                continue
            print(pptr[i])

main()

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(*result[2:], 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
def main():
    N,M,*AB=map(int,open(0).read().split())
    g=[[] for _ in range(N+1)]
    for a,b in zip(*[iter(AB)]*2):
        g[a].append(b)
        g[b].append(a)
    q=deque([1])
    s=[0]*(N+1)
    s[1]=1
    while q:
        u=q.popleft()
        for v in g[u]:
            if not s[v]:
                s[v] = u
                q.append(v)
    print("Yes")
    print("\n".join(map(str, s[2:])))
if __name__ == "__main__":
    main()

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

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

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

dist = [-100 for _ in range(n)]
dist[0] = 0



p = deque()
p.append(0)

while len(p) > 0:
    now = p.pop()
    for i in graph[now]:
        if dist[i] != -100:
            continue
        p.appendleft(i)
        dist[i] = now
        
print('Yes')
for i in range(1,n):
    print(dist[i]+1)

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

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

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


d = deque()
d.append(1)
while d:
  v = d.popleft()
  for i in graph[v]:
    if route[i] == -1:
      
      route[i] = v
      d.append(i)
if route.count(-1) == 0:
  print("Yes")
  for i in range(2,len(route)):
    print(route[i])
else:
  print("No")

Solution (Python):
from collections import deque
n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
vi=[0 for _ in range(n+1)]

for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=deque([1])
f=set([1])


while st:
  x=st.popleft()
  for k in l[x]:
    if k not in f:
      st.append(k)
      f.add(k)
      vi[k]=x   
  
print("Yes")
for m in vi[2:]:
  print(m)

Solution (Python):
import queue

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


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

flag = True


q = queue.Queue()
q.put(0)
r = queue.Queue()


while flag:
    flag = False
    num = 1

    while not q.empty():
        hoge = q.get()
        for i in range(len(root[hoge])):
            if sign[root[hoge][i]] == -1:
                sign[root[hoge][i]] = hoge
                r.put(root[hoge][i])
                flag = True

    while not r.empty():
        q.put(r.get())

    num += 1

if sign.count(-1) == 0:
    print("Yes")
    for i in range(1,N):
        print(sign[i]+1)
else:
    print("No")
    print(sign)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _i in range(m)]
 
visit = [-1 for _ in range(n)]
visit[0] = 0
tree = [[] for _ in range(n)]
for a, b in ab:
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
 
from collections import deque
q = deque([0])
while q:
    p = q.popleft()
    for i in tree[p]:
        if visit[i] < 0:
            visit[i] = p
            q.append(i)
if all(i >= 0 for i in visit):
    print("Yes")
    for i in visit[1:]:
        print(i+1)
else:
    print("No")

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    to = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        to[a].append(b)
        to[b].append(a)
    q = deque([1])
    ans = [None]*(n+1)
    while q:
        p = q.pop()
        for child in to[p]:
            if ans[child] is None:
                ans[child] = p
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))
    
    

if __name__ == "__main__":
    main()

Solution (Python):






def main():
    (N, M) = map(int, input().split())
    neighbor = [[] for _ in range(N+1)]
    for _ in range(M):
        (A,B) = map(int, input().split())
        neighbor[A] += B,
        neighbor[B] += A,

    guide = [0 for _ in range(N+1)]

    
    
    
    target = [1]
    checked = [1]
    while len(target) > 0:
        
        n = target.pop(0)
        
        dests = neighbor[n]
        
        dests = filter(lambda d: guide[d] == 0, dests)
        
        for d in dests:
            guide[d] = n
            checked += d,
            
            target += d,

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

main()

Solution (Python):
import sys
import queue
s = sys.stdin.readlines

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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


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

def bfs():
    q = queue.Queue()
    q.put(0)

    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = v + 1
            q.put(nv)
    
bfs()

if -1 in dist:
    print("No")
else:
    print("Yes")
    dist.pop(0)
    for s in dist:
        print(s)

Solution (Python):
from heapq import heappop, heappush

INF = 1000000
N, M = map(int, input().split())
d = [INF]*(N+1)
d[1] = 0
prev = [0]*(N+1)
G = {}
for i in range(M):
  a, b = map(int, input().split())
  try:
    G[a].append(b)
  except:
    G[a] = [b]
  try:
    G[b].append(a)
  except:
    G[b] = [a]

que = []
heappush(que, (0, 1))
    
while True:
  if len(que) == 0:
    break
  p = heappop(que)
  v = p[1]
  
  for u in G[v]:
    if (d[u] > d[v] + 1):
      d[u] = d[v] + 1
      heappush(que, (d[u], u))
      prev[u] = v
      
if 0 in prev[2:]:print('No')
else:
  print('Yes')
  for i in range(2, N+1):
    print(prev[i])

Solution (Python):
from collections import deque
n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
vi=[0 for _ in range(n+1)]

for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=deque([1])
f=set([1])


while st:
  x=st.popleft()
  for k in l[x]:
    if k not in f:
      st.append(k)
      f.add(k)
      vi[k]=x   
  
print("Yes")
for m in vi[2:]:
  print(m)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
vi=[0 for _ in range(n+1)]
vi[1]=-1

for i in range (m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
st=deque([1])
e=set()
f=set()


while st:
    x=st.popleft()
    if x not in e:
      e.add(x)
      for k in l[x]:
        if k not in f:
          st.append(k)
          f.add(k)
          vi[k]=x   
  
print("Yes")
for m in vi[2:]:
  print(m)