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):
def main():
    from sys import stdin
    import math
    n,m = map(int,stdin.readline().rstrip().split())
    way = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,stdin.readline().rstrip().split())
        way[a].append(b)
        way[b].append(a)
    
    mark = [0]*(n+1)
    flag = True
    check = [1]

    while flag:
        flag = False
        check_bf = [i for i in check]
        check = []

        for i in check_bf:
            for j in way[i]:
                if mark[j] == 0:
                    mark[j] = i
                    check.append(j)
                    flag = True
    
    if 0 in mark[2:]:
        print("No")
    else:
        print("Yes")
        for i in mark[2:]:
            print(i)
main()

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf



import math

import bisect
import queue

class Graph:

    def __init__(self, size):
        
        self.size = size
        self.vertices = [0] * size 
        self.visited = [False] * size
        self.edges = [None] * size
        for i in range(size):
            self.edges[i] = []

    def add_edge(self, frm, to):
        self.edges[frm].append(to)
        self.edges[to].append(frm)


class Solver:

    def __init__(self, graph):
        self.graph = graph
        self.que = queue.Queue() 
        self.set(0, -1)

    def set(self, v, parent):
        self.que.put(v)
        self.graph.visited[v] = True
        self.graph.vertices[v] = parent

    def run(self):
        while not self.que.empty():
            parent = self.que.get()
            for to in self.graph.edges[parent]:
                if self.graph.visited[to]:
                    continue
                self.set(to, parent)
        self.print_ans()

    def print_ans(self):
        
        
        print("Yes")
        for parent in self.graph.vertices[1:]:
            print(parent + 1)

if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    graph = Graph(n)
    for _ in range(m):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        graph.add_edge(a, b)
    Solver(graph).run()

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


import heapq
BIGDI = 10**18

n,m = inm()
s = 1
dst = [{} for i in range(n+1)]
for i in range(m):
    u,v = inm()
    dst[u][v] = 1
    dst[v][u] = 1

cost = [BIGDI]*(n+1)
q = [(0,s)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v], v))


ans = [-1]*(n+1)
for i in range(1,n+1):
    for j in dst[i]:
        if cost[j] == cost[i]+1:
            ans[j] = i
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Solution (Python):
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")

from collections import deque

def solve(n, m, passages):
    neighbors = {}
    for passage in passages:
        if passage[0] not in neighbors:
            neighbors[passage[0]] = []
        if passage[1] not in neighbors:
            neighbors[passage[1]] = []
        neighbors[passage[0]].append(passage[1])
        neighbors[passage[1]].append(passage[0])

    parents = {}
    visited = set([1])
    bfs = deque([1])
    while len(bfs) > 0:
        curr = bfs.popleft()
        for item in neighbors[curr]:
            if item not in visited:
                parents[item] = curr
                bfs.append(item)
                visited.add(item)


    if len(visited) != n:
        return None
    result = []
    for i in range(2, n+1):
        result.append(parents[i])
    return result



if __name__ == "__main__":
    n, m = arr_in()
    passages = mat_in(m)
    result = solve(n, m, passages)
    out("Yes" if result is not None else "No")
    if result is not None:
        for item in result:
            out(item)

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

q = deque()
q.append(1)
while (len(q) > 0):
    v = q.popleft();
    for nv in G[v]:
        
        if dist[nv] != -1: continue
        dist[nv] = v 
        
        q.append(nv)
print("Yes")
for x in range(2,len(dist)):
    print(dist[x])

Solution (Python):
import collections

[n,m] = [int(i) for i in input().split()]
def BFS(s,G,num):
    ls = collections.deque()
    check = [0] * num
    marker = [-1] * num
    check[0] = 1
    ls += G[s]
    for i in G[s]:
        marker[i] = s
    while(len(ls)):
        now = ls.popleft()
        if check[now] == 1:
            continue
        else:
            
            check[now] = 1
            ls += G[now]
            for i in G[now]:
                if marker[i] == -1:
                    marker[i] = now
    return marker
dic = collections.defaultdict(list)
for i in range(m):
    [a,b] = [int(i)-1 for i in input().split()]
    dic[a].append(b)
    dic[b].append(a)

ans = BFS(0,dic,n)

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

Solution (Python):
from collections import deque
def bfs(s):
    visited = [-1 for _ in range(n)]
    visited[0] = 0
    inf = float("inf")
    que = deque()
    que.append(s)
    while que:
        p = que.popleft()
        for i in grid[p]:
            if visited[i]==-1:
                que.append(i)
                visited[i] = p
    return visited

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

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

v=bfs(0)

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

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())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

prev = [0] * N
se = set([0])
q = deque([0])
while q:
    x = q.popleft()
    for y in graph[x]:
        if y in se:
            continue
        prev[y] = x
        q.append(y)
        se.add(y)
if len(se) == N:
    print('Yes')
    for x in prev[1:]:
        print(x + 1)
else:
    print('No')

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


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

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



ans = [None for _ in range(N)]
visited = [False for _ in range(N)]

que = [0]
while len(que) > 0:
    heya_i = que.pop(0)
    neighbors = Heyas[heya_i]
    for nei in neighbors:
        if not visited[nei]:
            ans[nei] = heya_i + 1
            visited[nei] = True
            que.append(nei)

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

Solution (Python):
from collections import deque

def main():
    N, M = map(int, input().split())
    edge = [[] for i in range(N)]
    for i in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        edge[A].append(B)
        edge[B].append(A)
    cnt = [float('inf')] * N  
    cnt[0] = 0
    Q = deque([0])
    visited = [False] * N
    visited[0] = True
    while Q:
        s = Q.popleft()

        for v in edge[s]:
            if visited[v]:
                continue
            cnt[v] = s + 1
            visited[v] = True
            Q.append(v)

    for i in range(N):
        if cnt[i] == float('inf'):
            print('No')
            exit()
    print('Yes')
    for i in range(1,N):
        print(cnt[i])


if __name__ == "__main__":
    main()

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

L=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    
now=[]
nex=[1]
went={1}
res={i:-1 for i in range(n+1)}
res[1]=1

while len(nex)>0:
    now=nex[:]
    nex=[]
    for x in now:
        for go in L[x]:
            if res[go]==-1:
                res[go]=x
                nex.append(go)
                
                

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

Solution (Python):
from collections import deque

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

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

ms = [0] * (N+1)
def bfs(c):
    queue = deque()
    ns = Gs[c]
    for n in ns:
        queue.append((n, c))
    while queue:
        c, p = queue.popleft()

        if ms[c] != 0:
            continue

        ms[c] = p

        ns = Gs[c]
        for n in ns:
            if n != p:
                queue.append((n, c))

bfs(1)

for m in ms[2:]:
    if m == 0:
        print('No')
        break
else:
    print('Yes')
    for m in ms[2:]:
        print(m)

Solution (Python):
from collections import defaultdict


num_room, num_path = map(int, input().split(' '))

paths = defaultdict(set)
for i in range(0, num_path):
    src, dest = map(int, input().split(' '))
    paths[src].add(dest)
    paths[dest].add(src)

rooms = {1}
route = {}

while rooms:
    new_rooms = set()
    for src in rooms:
        dest_set = paths[src]
        for dest in dest_set:
            if dest in route.keys():
                continue
            route[dest] = src
            new_rooms.add(dest)
    rooms = new_rooms

for i in range(2, num_room+1):
    if i not in route.keys():
        print("No")
        exit(0)

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

Solution (Python):

from collections import deque, defaultdict


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

visited = [False]*N
q = deque([0])  
visited[0] = True
ans = defaultdict(int)
while len(q):
    
    v = q.popleft()
    color = 1

    for e in tree[v]:
        if visited[e]:  
            continue
        visited[e] = True
        ans[e] = v
        q.append(e)

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

Solution (Python):

from collections import deque
N, M = map(int, input().split())
dd = {i:[] for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    dd[a-1].append(b-1)
    dd[b-1].append(a-1)
ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
queue = []
for i in range(len(dd[0])):
    queue.append([0, dd[0][i]])
queue = deque(queue)
while queue:
    q = queue.popleft()
    if visited[q[1]]:
        continue
    visited[q[1]] = True
    ans[q[1]] = q[0] + 1
    for v in dd[q[1]]:
        if not visited[v]:
            queue.append([q[1], v])
print("Yes")
print(*ans[1:], sep="\n")

Solution (Python):
from collections import deque

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

def BFS(x):
  v=deque([x])
  d[x]=0

  while len(v)>0:
    s=v.popleft()
    for t in C[s]:
      
      if d[t]==-1:
        d[t]=0
        m[t]=s
        v.append(t)
        
  else:
    pass
    
  
BFS(0)

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

Solution (Python):
from collections import deque

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

sign = {}
reached = {i: False for i in nodes}
reached[1] = True
queue = deque([1])
while queue:
    v = queue.popleft()
    for w in edges[v]:
        if not reached[w]:
            reached[w] = True
            queue.append(w)
            sign[w] = v

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

Solution (Python):
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)
ans = [-1 for _ in range(N)]
check = [(-1,0)]
count = 1
while True:
    for _ in range(len(check)):
        From, now = check.pop(0)
        for next in root[now]:
            if next == From:
                continue
            else:
                if ans[next] == -1:
                    ans[next] = now + 1
                    check.append((now,next))
                    count += 1
    if count == N:
        break
print('Yes')
ans.pop(0)
print('\n'.join(list(map(str,ans))))

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

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

target = [-1]*n
seen = [False]*n

from collections import deque
que = deque()

que.append(0)
while len(que) > 0:
    current = que.popleft()
    if seen[current]:
        continue
    seen[current] = True
    nodes = graph[current]

    for i in nodes:
        if target[i] == -1:
            target[i] = current + 1
        que.append(i)

target.pop(0)

if -1 in target:
    print('No')
else:
    print('Yes')
    for t in target:
        print(t)

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

P=[-1 for i in range(N+1)]
P[1]=1
Q=[]
for i in L[1]:
    Q.append([i,1])

for i in range(10**7):
    if i==len(Q):
        break
    q1,q2=Q[i]
    if P[q1]!=(-1):
        continue
    else:
        P[q1]=q2
        for j in L[q1]:
            if P[j]==(-1):
                Q.append([j,q1])

print("Yes")
for i in range(2,len(P)):
    print(P[i])

Solution (Python):
import heapq
from collections import deque
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:
                        heapq.heappush(queue,(w,j,k))

        return gb

    def bfs(self,vartex = 0):
        todo = [True]*self.v
        queue = deque([vartex])
        while(len(queue)>0):
            v = queue.popleft
            todo[v] = False
            yield v
            for v_i in self.neighbor[v]:
                if todo[v_i]:
                    queue.append(v_i)

    def dfs(self,vartex = 0):
        seen = [False]*self.v
        def recdfs(v):
            seen[vartex] = True
            for next_v in self.neighbor[vartex]:
                if (seen[next_v]):continue
                recdfs(next_v)
    
        
            
class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False,edge = None, weights = None):
        self.v = v
        self.directed = directed
        self.edge = []
        self.weights = []
        if edge is not None:
            self.addEdges(edge)
        if weights is not None:
            self.addVartex(weights)

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
    
    def addVartex(self,weights):
        if len(weights) != self.v:
            return
        self.weights.extend(weights)

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():
    n,m = tuple([int(t)for t in input().split()])
    edge = []

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

    gb = GraphBuilder(n,edge=edge)
    g = gb.buildGraph()

    queue = deque([0])
    root = [-1]*n
    checked = [False]*n
    determined = [False]*n
    while(len(queue)>0):
        p = queue.popleft()
        if checked[p]:
            continue
        checked[p] = True
        for q in g.neighbor[p]:
            if determined[q]:
                continue 
            root[q] = p+1
            queue.append(q)
            determined[q] = True

    if all(checked):
        print("Yes")
        for i in root[1:]:
            print(i)
    else:
        print("No")

if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
D = {i: [] for i in range(N)}
for i in range(M):
  a, b = map(int, input().split())
  D[a-1].append(b-1)
  D[b-1].append(a-1)
R = [-1 for _ in range(N)]
R[0] = 0
p = [0]
pnt = 0
cnt = 1
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    x = D[p[i]][:]
    for k in x:
      if R[k] == -1:
        R[k] = p[i]+1
        cnt += 1
        p.append(k)
  pnt = n
print("Yes")
for i in range(1, N):
    print(R[i])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    n, m = LI()
    G = [[] for _ in range(n)]
    for _ in range(m):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
    q = deque()
    q.append((0, 0))
    michi = [-1 for _ in range(n)]
    while q:
        v, par = q.popleft()
        michi[v] = par
        for next_v in G[v]:
            if michi[next_v] != -1:
                continue
            michi[next_v] = v
            q.append((next_v, v))
    print('Yes')
    for i in range(1, n):
        print(michi[i] + 1)


main()

Solution (Python):
import sys
from collections import deque

n, m, *ab = map(int, sys.stdin.read().split())
ab = zip(*[iter(ab)] * 2)
graph = [[] for _ in range(n)]
for a, b in ab:
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)

def main():
    parent = [None] * n 
    parent[0] = 0
    queue = deque([0])
    while queue:
        x = queue.popleft()
        for y in graph[x]:
            if parent[y] is not None: continue 
            parent[y] = x
            queue.append(y)

    if None in parent:
        print('No')
    else:
        print('Yes')
        for i in range(1, n):
            print(parent[i] + 1)

if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(M)]
   
from collections import deque
import sys
sys.setrecursionlimit(10**7)

D=[[]for i in range(N)]
E=[-1]*N
for a,b in A:
   a-=1
   b-=1
   D[a].append(b)
   D[b].append(a)


def bfs(x):
  q=deque()
  q.append(x)
  
  while len(q):
    x=q.popleft()    
    for i in D[x]:
      nx=i
      if E[nx]==-1:
        E[nx]=x
        q.append(nx)
bfs(0)
print('Yes')
for i in E[1:]:
  print(i+1)

Solution (Python):
import random
import math
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
yes = lambda: print("Yes")
no = lambda: print("No")
I = lambda: list(input())
J = lambda x: "".join(x)
II = lambda: int(input())
SI = lambda: input()

n,m = MI()
d = {}
for i in range(m):
	a,b = MI()
	if a not in d:
		d[a] = [b]
	else:
		d[a].append(b)
	if b not in d:
		d[b] = [a]
	else:
		d[b].append(a)
q = [1]
mark = [0]*(n+1)
di = [0]*(n+1)
di[1] = 0
mark[1] = 1
way = [0]*(n+1)
while len(q)>0:
	v = q.pop(0)
	for i in range(len(d[v])):
		if mark[d[v][i]] == 0:
			di[d[v][i]] = di[v] + 1
			mark[d[v][i]] = 1
			q.append(d[v][i])
			way[d[v][i]] = v
if 0 in di[2:]:
	print("No")
else:
	print("Yes")
	for i in range(2,n+1):
		print(way[i])

Solution (Python):
import sys
import heapq

def main():
    n, m = map(int, input().split())
    graph = {}
    for i in range(n):
        graph[i + 1] = []
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    
    visited = set()
    stack = [1]
    ans = [None] * (n + 1)
    while stack:
        temp = []
        while stack:
            node = stack.pop()
            if node in visited:
                continue
            visited.add(node)
            for i in graph[node]:
                if ans[i] == None:
                    ans[i] = node
                if i not in visited:
                    temp.append(i)
        stack = temp[:]
    if len(visited) != n:
        print("No")
    else:
        print("Yes")
        for i in range(2, n + 1):
            print(ans[i])
    
    return

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
import numpy as np
from heapq import heapify, heappop, heappush
import copy
from collections import deque


def main():
    N, M = map(int, input().split())
    adj_lists = {i: [] for i in range(1, N + 1)}
    for i in range(M):
        a, b = map(int, input().split())
        adj_lists[a].append(b)
        adj_lists[b].append(a)
    alreadys = np.zeros((N + 1, ))
    queue = deque()
    queue.append(1)
    while(len(queue) != 0):
        now = queue.popleft()
        nexts = adj_lists[now]
        for next_ in nexts:
            if alreadys[next_] != 0:
                continue
            alreadys[next_] = now
            queue.append(next_)
    for i in range(2, N+1):
        if alreadys[i] == 0:
            print('No')
            sys.exit()
    
    print('Yes')
    for i in range(2, N + 1):
        print(int(alreadys[i]))





if __name__ == '__main__':
    main()

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-1)
    G[b-1].append(a-1)
oya = [-1]*n
oya[0] = 0
que = deque([0])
while que:
    v = que.popleft()
    for w in G[v]:
        if oya[w] > -1:
            continue
        oya[w] = v
        que.append(w)
if -1 in oya:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        print(oya[i]+1)

Solution (Python):
import itertools
from collections import defaultdict
import collections
import math
import sys
import queue
sys.setrecursionlimit(200000)
mod = 1000000007

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

graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

tf = [False] * (n + 1)
sirube = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v,0])
    tf[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        before = sub[1]
        for next in graph[now]:
            if tf[next]:
                continue
            tf[next] = True
            if sirube[next] == 0:
                sirube[next] = now
            q.put([next, now])

bfs(1)
for i in range(2, n + 1):
    if sirube[i] == 0:
        print("No")
        exit()

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

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, input().split())
path = [[] for _ in range(n)]
ans = [-1] * (n - 1)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    
    path[a].append(b)
    path[b].append(a)


stack = deque()
stack.append(0)
while len(stack) > 0:
    pos = stack.popleft()
    for next_pos in path[pos]:
        if next_pos == 0:
            continue
        if ans[next_pos - 1] == -1:  
            ans[next_pos - 1] = pos + 1
            stack.append(next_pos)  
print("Yes")
for i in ans:
    print(i)

Solution (Python):

from collections import Counter, defaultdict, deque



import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    q = deque()
    q.append(1)
    d = {}
    d[1] = 0
    prev = {}
    while q:
        u = q.popleft()
        for v in g[u]:
            if v in d:
                continue
            d[v] = d[u] + 1
            prev[v] = u
            q.append(v)
    print('Yes')
    return [prev[i] for i in range(2, N+1)]


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(*slv(N, M, AB), sep='\n')


if __name__ == '__main__':
    main()

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

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

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

result=[-1]*n
result[0]=0
from collections import deque
stack=deque([0])
while len(stack)>0:
    key=stack.popleft()
    for item in tree[key]:
        if result[item]==-1:
            result[item]=key+1
            stack.append(item)

if -1 in stack:
    print("No")
    exit()
else:
    print("Yes")   
    for item in result[1:]:
        print(item)

Solution (Python):
from collections import deque


def bfs(graph, n, start):
    visited = [0] * (n+1)
    visited[start] = 1
    start = min(graph.keys())
    queue = deque([])
    queue.append(start)
    pos = {}
    pos[start] = 0

    while queue:
        u = queue.popleft()
        for v in graph[u].keys():
            if  visited[v]:
                continue
            visited[v] = u
            queue.append(v)

    print('Yes')
    [print(i) for i in visited[2:]]
    return True

def resolve():
    n,m = map(int,input().split())
    graph = {i: {} for i in range(1,n+1)}

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

    bfs(graph, n, 1)

if __name__ == "__main__":
    resolve()