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

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

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

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

    ans = [x + 1 for x in parent[1:]]

    print('Yes')
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):

def get_input():
    N, M =  list(map(int, input().split()))
    routes = {}
    for i in range(M):
        a, b =  list(map(int, input().split()))
        a_idx = a - 1
        b_idx = b - 1
        if a_idx in routes:
            routes[a_idx].append(b_idx)
        else:
            routes[a_idx] = [b_idx]
        
        if b_idx in routes:
            routes[b_idx].append(a_idx)
        else:
            routes[b_idx] = [a_idx]

    return N, M, routes

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy


marks = {0:0}

N, M, routes = get_input()
mark = {0:0}
start_nodes = [0]
while start_nodes:
    next_nodes = []
    for i in start_nodes:
        for n in routes[i]:
            if n in marks:
                continue
            marks[n] = i
            next_nodes.append(n)
    start_nodes = next_nodes   
write_result(marks, N)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
R = [[] for _ in range(N)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for _ in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(que):
    if que==[]:
        return
    i = que[0]
    for j in R[i-1]:
        if ans[j-1]==0:
            ans[j-1]=i
            que.append(j)
    que.pop(0)
    bfs(que)
    
bfs(queue)
print('Yes')
for i in range(1,N):
    print(ans[i])

Solution (Python):
import queue

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

for _ in range(N):
    V.append(set())

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

q = queue.Queue()

q.put(0)
visit = [False]*N
visit[0] = True
ans_list = [0]*N
while not (q.empty()):
    node = q.get()
    for next_node in V[node]:
        if visit[next_node]:
            continue
        visit[next_node] = True
        ans_list[next_node] = node
        q.put(next_node)

if False in visit:
    print("No")
else:
    print("Yes")
    for i in range(1, len(ans_list), 1):
        print(ans_list[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")
for i in range(2,N+1):
	print(d[i])

Solution (Python):
import queue

n,m = map(int, input().split())
root = [[] for i in range(n)]
for i in range(m):
    tmp1, tmp2 = map(int, input().split())
    root[tmp1 - 1].append(tmp2 - 1)
    root[tmp2 - 1].append(tmp1 - 1)
q = queue.Queue()
q.put(0)
arrive = [0 for i in range(n)]
ans = [0 for i in range(n)]
arrive[0] = 0
while not q.empty():
    now = q.get()
    for i in root[now]:
        if arrive[i] == 0 and i != 0:
            arrive[i] = arrive[now] + 1
            ans[i] = now + 1
            q.put(i)
        else:
            if arrive[i] > arrive[now] + 1:
                ans[i] = now + 1

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

Solution (Python):
from collections import defaultdict, deque

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

def bfs():
    q = deque([(1, None)])
    visited = set()
    posts = {}

    while q:
        node, last_node = q.pop()
        if last_node:
            posts[node] = last_node
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                q.appendleft((neighbor, node))
                visited.add(neighbor)
    
    return posts, len(visited)

posts, total_visited = bfs()
if total_visited != n:
    print('No')
else:
    print('Yes')
    for p in range(2, n+1):
        print(posts[p])

Solution (Python):








from collections import deque

def bfs(path_list,guide,n):
    color = [0]*(n+1)
    color[1] = 1
    Q = deque()
    Q.append(1)
    while Q:
        u = Q.popleft()
        for v in path_list[u]:
            if color[v] == 0:
                color[v]=1
                Q.append(v)
                guide[v]=u

def main():
    n,m = map(int,input().split())
    path_list = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,input().split())

        path_list[a].append(b)
        path_list[b].append(a)


    
    guide = [0]*(n+1)
    bfs(path_list,guide,n)
    print("Yes")
    for i in range(2,n+1):
        print(guide[i])


if __name__ == "__main__":
    main()

Solution (Python):
import collections
N, M = map(int, input().split())
nodes = [None] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    if nodes[A] is None:
        nodes[A] = set()
    nodes[A].add(B)
    if nodes[B] is None:
        nodes[B] = set()
    nodes[B].add(A)
r = [None] * N
r[0] = "Yes"
Q = collections.deque([0])
while len(Q) != 0:
    i = Q.popleft()
    for j in nodes[i]:
        if r[j] is None:
            r[j] = i+1
            Q.append(j)
for x in r:
    print(x)

Solution (Python):
n,m = [int(e) for e in input().split(" ")[:2]]

r_dic = {i+1: [] for i in range(n)}
for i in range(m):
	a,b = [int(e) for e in input().split(" ")[:2]]
	r_dic[a].append(b)
	r_dic[b].append(a)

m_dic = {i+1: None for i in range(1,n)}
search_flag_dic = {i+1: False for i in range(n)}

s_ls = [1]
while True:
	next_s_ls = []
	for s in s_ls:
		search_flag_dic[s] = True
		
		d_ls = r_dic[s]
		
		for d in d_ls:
			if d == 1: continue
			if m_dic[d] is None: m_dic[d] = s
			next_s_ls.append(d)
	
	next_s_ls = list(set(next_s_ls))
	next_s_ls = [e for e in next_s_ls if search_flag_dic[e] is False]
	if len(next_s_ls) == 0: break
	s_ls = next_s_ls

result = "Yes" if len([k for k in m_dic if m_dic[k] is None]) == 0 else "No"
print(result)
if result == "Yes":
	for i in range(1,n):
		print(m_dic[i+1])

Solution (Python):
def resolve():
    from collections import deque
    n, m = map(int, input().split())
    michi = [[] for j in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        michi[a-1].append(b-1)
        michi[b - 1].append(a - 1)
    heya=[-1]*n

    def f():
        check=0
        que = deque([])
        que.append(0)
        while que:
            p = que.popleft()
            for i in michi[p]:
                if heya[i] == -1:
                    heya[i] = p + 1
                    check += 1
                    if check == n :
                        break
                    que.append(i)

        return

    f()
    print("Yes")
    for i in heya[1:]:
        print(i)
resolve()

Solution (Python):
def main():
    n,m=map(int,input().split())
    ab = {}
    ab1 = {}
    for _ in range(m):
        a,b=map(int,input().split())
        ab.setdefault(a,set()).add(b)
        ab.setdefault(b,set()).add(a)
        ab1.setdefault(a,set()).add(b)
        ab1.setdefault(b,set()).add(a)
    g = []
    g.append(set([1]))
    marked = set()
    marked.add(1)
    while ab:
        g_add = set()
        for k in g[-1]:
            for x in ab[k]:
                if x not in marked:
                    g_add.add(x)
                    marked.add(x)
            del ab[k]
        g.append(g_add)
    if len(marked) < n:
        print('No')
        return
    print('Yes')
    result = [None] * n
    for i,s in enumerate(g):
        if not i:
            continue
        for k in s:
            result[k-1] = (g[i-1]&ab1[k]).pop()
    for i in range(1,n):
        print(result[i])

main()

Solution (Python):

import sys
import queue


YES = "Yes"  


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    root = []
    for i in range(N):
        root.append([])
    next = [-1] * N
    for a, b in zip(A, B):
        root[a - 1].append(b - 1)
        root[b - 1].append(a - 1)

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

    while not q.empty():
        
        n = q.get()
        for i in root[n]:
            if next[i] == -1:
                next[i] = n
                q.put(i)

    if -1 in next:
        print("No")
        exit()
    
    print("Yes")
    for i in range(1, len(next)):
        print(next[i] + 1)
    

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

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

for idx in range(n):
    road[idx] = []

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

visited = [-1 for i in range(n)]

from collections import deque
def bfs(road):
    global visited
    queue = deque([0])
    visited[0] = 0
    while queue:
        x = queue.popleft()
        for r in road[x]:
            if visited[r] == -1:
                visited[r] = x
                queue.append(r)

bfs(road)
if (-1) in visited:
    print('No')
else:
    print('Yes')
    for x in visited[1:]:
        print(x + 1)

Solution (Python):
from queue import Queue
import sys

sys.setrecursionlimit(10 ** 6)

def main():
  n, m = map(int, input().split())

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

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

  visited = {0: -1}

  q = Queue()
  q.put(0)

  while not q.empty():
    current = q.get()
    for nxt in edges[current]:
      if nxt not in visited:
        visited[nxt] = current
        q.put(nxt)

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


main()

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

ab = [[] for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    ab[ai].append(bi)
    ab[bi].append(ai)
from collections import deque



def bfs(g, i, N):
    
    
    dis = [float('Inf')] * N 
    route = [0] * N
    
    d = [False] * N
    
    que = deque()
    que.append(i)
    d[i] = True
    dis[i] = 0
    
    while que:
        p = que.popleft()
        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[k] = dis[p] + 1
                route[k] = p

    return dis, route
dis, route = bfs(ab, 0, n)
for i in range(n):
    if i == 0:
        continue
    if dis[i] == 0:
        print('No')
        
print('Yes')
for i in range(1, n):
    print(route[i] + 1)

Solution (Python):
def main():
    n, m = [int(v) for v in input().split(' ')]
    map_table = {}
    for _ in range(m):
        a, b = [int(v) - 1 for v in input().split(' ')]
        if a not in map_table.keys():
            map_table[a] = [b]
        else:
            map_table[a].append(b)

        if b not in map_table.keys():
            map_table[b] = [a]
        else:
            map_table[b].append(a)

    stack = [0]
    min_step = [None for _ in range(n)]
    min_step[0] = 0
    n_step = 0

    while len(stack) > 0:
        n_step += 1
        next_stack = []
        for n in stack:
            next_nodes = map_table[n]
            for next_n in next_nodes:
                if min_step[next_n] is None:
                    min_step[next_n] = n
                    next_stack.append(next_n)
        stack = next_stack

    suucess = True
    for v in min_step:
        if v is None:
            suucess = False
    if suucess is True:
        print('Yes')
        for n in min_step[1:]:
            print(int(n) + 1)
    else:
        print('No')


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n, m = map(int, input().split())
r = [[0] for i in range(n+1)]
num = {0:0, 1:1}
e = deque([]) 
for i in range(m):
	a, b = map(int, input().split())
	r[a].append(b)
	r[b].append(a)
e.append(1)
while len(e) > 0:
	x = e.popleft()
	for y in r[x]:
		if y not in num:
			num[y] = x
			e.append(y)
print("Yes")
for i in range(2, n+1):
	print(num[i])

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
import heapq
class DijkstraList():
	
	
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v in self.list[u]:
				if self.dist[v] > u_dist + 1:
					self.dist[v] = u_dist + 1
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

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)

d = DijkstraList(adj, 0)
d.solve()
print("Yes")
for x in d.prev[1:]:
	print(x+1)

Solution (Python):
def main():
    import sys
    from collections import defaultdict,deque
    sys.setrecursionlimit(10**5+2)

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=defaultdict(list)
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A].append(B)
        dic[B].append(A)
    
    L=[-1]*(N+1)
    R=[-1]*(N+1)


    d = deque()
    d.append((1,1))
    while len(d):
        now,count=d.popleft()
        for goto in dic[now]:
            if L[goto]==-1 or count<L[goto]:
                L[goto]=count
                R[goto]=now
                d.append((goto,count+1))

    if any(x+1 for x in R[2:]):
        print('Yes')
        for x in R[2:]:
            print(x)
    else:
        print('No')
    


main()

Solution (Python):
from collections import deque

R=lambda: map(int, input().split())

n, m = R()
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = R()
  g[u - 1].append(v - 1)
  g[v - 1].append(u - 1)

r = ['Yes'] + [None] * (n - 1)
V = [True] + [False] * (n - 1)
q = deque([0])
while q:
  u = q.popleft()
  for v in g[u]:
    if not V[v]:
      V[v] = True
      r[v] = u + 1
      q.append(v)

print(*(['No'], r)[all(r)], sep='\n')

Solution (Python):
from collections import deque



n,m = map(int,input().split())
ab = [[] for _ in range(m)]
kr = [[] for _ in range(n)]
dist = [-1 for _ in range(n)]
dist[0] = 0
ans = [-1 for _ in range(n)]
qn = deque([1])
for i in range(m):
    a,b = map(int,input().split())
    a,b = min(a,b),max(a,b)
    ab[i] = [a,b]
    kr[a-1].append(b)
    kr[b-1].append(a)

dis = 1
while len(qn) > 0:
    v = qn.popleft()
    d = dist[v-1]
    for w in kr[v-1]:
        if dist[w-1] > -1:
            continue
        dist[w-1] = d + 1
        qn.append(w)
        ans[w-1] = v








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

Solution (Python):
import queue
n,m = map(int,input().split())
graph = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b)
    graph[b-1].append(a)
ans = [0]* n
q = queue.deque()
q.append(1)
while q:
    tmp = q.popleft()
    for i in graph[tmp-1]:
        if ans[i-1] == 0:
            q.append(i)
            ans[i-1] = tmp
                
if 0 in ans:
    print('No')
        
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i])

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

l = [[] for i in range(n)]
for pi in ab:
    l[pi[0]-1].append(pi[1]-1)
    l[pi[1]-1].append(pi[0]-1)

ans=[0]*n

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0 
    while queue:
        v = queue.popleft()
        for i in l[v]:
            if d[i] is None:
                ans[i] = v
                d[i] = d[v] + 1
                queue.append(i)

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

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


def bfs(u):
    ans = [None] * (N+1)
    queue = deque([u])
    d = [None] * (N+1) 
    d[u] = 0 
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                ans[i] = v
                queue.append(i)
    return ans
d = bfs(1)
print("Yes")
for i in range(2,N+1):
    print(d[i])

Solution (Python):
from collections import deque
n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for i in range(m)]
pr=[[] for i in range(n)]
for i in a:
    pr[max(i)-1].append(min(i))
    pr[min(i)-1].append(max(i))
d=deque([1])
checked=[0]*n
checked[0]=1
ans=[0]*(n-1)
while len(d)>0:
    rm=d.popleft()
    for i in pr[rm-1]:
        if checked[i-1]==0:
            d.append(i)
            checked[i-1]=1
            ans[i-2]=rm
    
print('Yes')
for i in ans:
    print(i)

Solution (Python):
import queue
import sys
n, m = list(map(int, input().split()))
a, b = zip(*[list(map(int, input().split())) for i in range(m)])

next0 = [[] for i in range(n+1)]
for i in range(m):
    x = min(a[i], b[i])
    y = max(a[i], b[i])
    next0[x].append(y)
    next0[y].append(x)




def search():
    d = [0] * (n+1)
    z = [-1] * (n+1)

    que = queue.Queue()
    que.put(1)

    while not que.empty():
        p = que.get()
        for nx in next0[p]:
            
            if 1 <= nx <= n and d[nx] == 0:
                que.put(nx)
                d[nx] = d[p] + 1
                z[nx] = p
    return d, z

z = search()[1]

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

Solution (Python):

import sys
from collections import deque

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,m = na()
    path = [[] for _ in range(n)]
    ans = [0] + [-1 for i in range(n-1)]
    sumcheck = 1
    for _ in range(m):
        a,b = na()
        a -= 1
        b -= 1
        path[a] += [b]
        path[b] += [a]
    d = deque([0])
    while len(d):
        now = d.popleft()
        for nxt in path[now]:
            if ans[nxt] == -1:
                ans[nxt] = now
                sumcheck += 1
                d.append(nxt)
    if sumcheck == n:
        print('Yes')
        for i in ans[1:]:
            print(i+1)
    else:
        print('No')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from queue import Queue

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

dict = {}

for i in range(M):
    A,B = list(map(int, input().split()))

    if A in dict:
        l = dict[A]
        l.append(B)
        dict[A] = l
    else:
        l = [B]
        dict[A] = l

    if B in dict:
        l = dict[B]
        l.append(A)
        dict[B] = l
    else:
        l = [A]
        dict[B] = l

queue = Queue()
queue.put(1)
prev = 1

ans = [-1] * N
while not queue.empty():
    tmp = queue.get()

    if tmp in dict:
        next = dict[tmp]
        for i in next:
            if ans[i - 1] == -1:
                queue.put(i)
                ans[i - 1] = tmp
        
    prev = tmp

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

Solution (Python):
from collections import deque

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

mitishil = {i+1:-1 for i in range(1,N)}


q = deque()
q.append(1)
while(q):
  v = q.popleft()
  ls = neib[v]
  
  for l in ls:
    
    if (l == 1): continue
    if (mitishil[l] == -1):
      mitishil[l] = v
      q.append(l)
    
print("Yes")
for i in mitishil.values():
  print(i)

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.readline
N, M = map(int, readline().split())
G = [[] for _ in range(N)]
E = [0] * N
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    E[a] += 1
    G[b].append(a)
    E[b] += 1
pre = [[] for _ in range(N-1)]
visited = [-1] * N
L = []
q = deque([0])
visited[0] = 0
while q:
    x = q.popleft()
    for a in G[x]:
        if visited[a] == -1:
            visited[a] = x+1
            q.append(a)
if -1 in visited:
    print('No')
else:
    print('Yes')
    print(*visited[1:], sep='\n')

Solution (Python):
from collections import deque
n, m = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
visited = [-1] * n
ans = [-1] * n
queue = deque([0])
while queue:
    pos = queue.popleft()
    visited[pos] = 1
    ll = path[pos]
    for l in ll:
        if visited[l] == -1:
            if ans[l] == -1:
                ans[l] = pos + 1
                queue.append(l)
print("Yes")
for i in range(1, n):
    print(ans[i])

Solution (Python):
def main():
    n,m = map(int,input().split())
    ab = [list(map(int,input().split())) for _ in range(m)]
    g = [[] for _ in range(n)]
    for a,b in ab:
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    
    dist = [-1]*n
    from collections import deque
    dist[0] = 0
    q = deque()
    q.append(0)
    while q:
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = v
            q.append(nv)
    
    print('Yes')
    for v in range(1,n):
        print(dist[v]+1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N)]

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

    ans_list = [-1] * N

    queue = [0]
    seen = [False]*N

    while queue:
        qi = queue.pop(0)
        
        for gi in g[qi]:
            if seen[gi] == False:
                queue.append(gi)
                if ans_list[gi] == -1:
                    ans_list[gi] = qi
                    seen[gi] = True

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

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
root=[[] for _ 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)
times=[0]*n
sign=[-1]*n
sign[0]=0
color=[False]*n
que=deque([0])
while que: 
	i=que.popleft()
	if color[i]==False:
		for edge in root[i]:
			if color[edge]==False and sign[edge]==-1: 
				sign[edge]=i
				que.append(edge)
		color[i]=True
print('Yes')
for i in range(n-1):
	print(sign[i+1]+1)

Solution (Python):
from collections import deque
def main():
    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)
    dict={}
    for i in range(n):
        dict[i]=-1

    start=0
    check=[False]*n
    toVis=deque()
    check[start]=True
    for v in root[start]:
        toVis.append(v)
        dict[v]=start
    
        check[v]=True
    while len(toVis)>0:
        now=toVis.popleft()
        
        check[now]=True
        for v in root[now]:
            if check[v]==False:
                toVis.append(v)
                dict[v]=now
            
                check[v]=True
    
    for i in range(1,n):
        if dict[i]==-1:
            print("No")
            return 0
    print("Yes")
    for i in range(1,n):
        print(dict[i]+1)         


if __name__=="__main__":
    main()

Solution (Python):
import queue
n, m = map(int,input().split())
g = [[] for _ in range(n+1)]
g_cost = [ float('inf') for _ in range(n+1)]
g_ans = [ 0 for _ in range(n+1)]
for i in range(0,m):
    s,t = map(int,input().split())
    g[s].append(t)
    g[t].append(s)

q = queue.Queue()
q.put(1)
g_cost[1] = 0
while not q.empty():
    room = q.get()
    for c_room in g[room]:
        if g_cost[room]+1 < g_cost[c_room]:
            g_cost[c_room] = g_cost[room]+1
            g_ans[c_room] = room
            q.put(c_room)


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

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

ans = [0] * (n + 1)
ans[1] = -1
queue = deque()
for s in table[1]:
    ans[s] = 1
    
    queue.append((s, 1))
while len(queue) > 0:
    node = queue.popleft()
    for t in table[node[0]]:
        if ans[t] != 0 or t == 0:
            continue
        ans[t] = node[0]
        queue.append((t, node[0]))
if 0 in ans[2:]:
    print("No")
else:
    print("Yes")
    for a in ans[2:]:
        print(a)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
ans_list = [0]*(n+1)

class Node:
    def __init__(self, x):
        self.val = x
        self.adj = []

nodelist = [Node(0)]
for i in range(1, n+1):
  nodelist.append(Node(i))

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

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

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

    if node is not None:
        for i in node.adj:
            if ans_list[i] == 0:
                ans_list[i] = node.val
                q.append(nodelist[i])

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

Solution (Python):
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 


n, m = map(int, input().split())
root = {i:[] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    root[a].append(b)
    root[b].append(a)

if len(root) != n:
    print('No')
    sys.exit()

r = sorted(root.items())
mae = [ -1 for _ in range(n)]
mae[0] = n
q = [0]
while True:
    l = len(q)
    if l == 0: break
    for i in range(l):
        ima = q[i]
        for tugi in r[ima][1]:
            if tugi == mae[ima]: continue
            if mae[tugi] != -1:
                if mae[tugi] != ima: continue
            mae[tugi] = ima
            q.append(tugi)
    q = q[l:]
if min(mae) == -1:
    print('No')
    sys.exit()
print('Yes')
for x in mae[1:]:
    print(x + 1)

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

me = [0 for _ in range(n+1)]
me[1] = 1
miti = [[] for _ in range(n+1)]
tansaku = [0 for i in range(n+1)]
tansaku[1]=1
for i,j in l:
  miti[j].append(i)
  miti[i].append(j)
a = deque()
for i in miti[1]:
  a.append(i)
  me[i] = 1
  tansaku[i]=1
while len(a)!=0:

  w = a.popleft()
  for j in miti[w]:
    if tansaku[j]==0 :
          a.append(j) 
          tansaku[j] = 1
          me[j] = w
 
  
print("Yes")
for i in range(len(miti)-2):
  print(me[i+2])