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):
n,m = map(int,input().split())
AB = []
ans = [-1] * (n) 

edge = [[] for _ 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)    
    
import collections
que = collections.deque()
que.append(0) 
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        a = x
        b = to
        
        if ans[b] == -1: 
            ans[b] = x + 1 
            que.append(b)
            
print("Yes")
print(*ans[1:],sep="\n")

Solution (Python):
from queue import Queue

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

l = [[] for _ in range(n)]
for a, b in ab:
    l[a-1].append(b-1)
    l[b-1].append(a-1)

q = Queue()
ans = [0] * n
ans[0] = 1
f = [0] * n
f[0] = 1
for v in l[0]:
    q.put((v, 0))
    f[v] = 1
    
cnt = 0
x = 0
while not q.empty():
    i = q.get()
    ans[i[0]] = i[1]+1
    for v in l[i[0]]:
        if f[v] == 0:
            q.put((v, i[0]))
            f[v] = 1

if 0 not in ans:
    print("Yes")
else:
    print("No")
    exit()

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

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

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

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

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

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

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

Solution (Python):


from collections import deque

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

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

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

miteru = deque([1]) 
mita = {1} 
res = [-1]*(N+1)

while  miteru: 
    now = miteru.popleft()
    x =set( r[now])
    x = x - mita
    for i in x:
        miteru.append(i)
        if res[i] == -1:res[i] =now
        mita.add(i)
    
print("Yes")
for i in res[2:]:
    print(i)

Solution (Python):
from collections import deque

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

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

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

signposts = [None] * N
que = deque([0])

while que:
    n = que.popleft()
    for room in rooms[n]:
        if signposts[room] is None:
            que.append(room)
            signposts[room] = n + 1

if None in signposts:
    print("No")
else:
    signposts[0] = "Yes"
    for s in signposts:
        print(s)

Solution (Python):
import collections
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]
ans = [None] * (N + 1)
G = collections.defaultdict(set)
for a, b in AB:
    G[a].add(b)
    G[b].add(a)
Q = collections.deque([1])
while Q:
    i = Q.popleft()
    for j in G[i]:
        if ans[j] is None:
            Q += [j]
            ans[j] = i
print('Yes')
print('\n'.join(map(str, ans[2:])))

Solution (Python):
n,m = map(int,input().split())
AB = []
ans = [0] * (n-1)

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

for i in range(m):
    a,b = map(int,input().split())
    edge[a].append(b)    
    edge[b].append(a)    
    
import collections
que = collections.deque()
que.append(1)
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        a = x
        b = to
        
        if b!=1 and ans[b-2] == 0:
            ans[b-2] = x
            que.append(b)
            
if 0 in ans:
    print("No")
else:
    print("Yes")
    
    for i in ans:
        print(i)

Solution (Python):
from collections import defaultdict, deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    parents = [-1]*N
    G = defaultdict(list)
    for _ in range(M):
        a, b = read_ints()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    Q = deque([(0, 0)])
    count = 0
    while len(Q) != 0:
        node, parent = Q.popleft()
        for child in G[node]:
            if child != parent and parents[child] == -1:
                parents[child] = node
                count += 1
                Q.append((child, node))
    if count == N-1:
        print('Yes')
        for p in parents[1:]:
            print(p+1)
    else:
        print('No')


if __name__ == '__main__':
    solve()

Solution (Python):
import queue

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

INF = 1001001001
q = queue.Queue()
dist = [INF for i in range(n)]
pre = [-1 for i in range(n)]
dist[0] = 0
q.put(0)
while not q.empty():
    v = q.get()
    for u in to[v]:
        if dist[u] != INF:
            continue
        dist[u] = dist[v] + 1
        pre[u] = v
        q.put(u)

print('Yes')
for i in range(n):
    if i == 0:
        continue
    print(pre[i] + 1)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**9)


INF = 10**20
def main():
    N,M = map(int,input().split())

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

    stack = deque([0])
    ans = [0]*N
    visited = set()
    while len(stack) > 0:
        x = stack.popleft()
        for next in graph[x]:
            if not next in visited:
                ans[next] = x
                visited.add(next)
                stack.append(next)

    if len(visited) != N:
        print("No")
    else:
        print("Yes")
        for i in ans[1:]:
            print(i+1)



if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque

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

seen = [False for i in range(n)]

ans = [0] * (n)
for i in range(0, m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
q = deque()
q.append(0)
INF = float('inf')
dist = [INF for i in range(n)]
dist[0] = 0
pre = [-1 for i in range(n)]
seen[0] = True
while len(q) > 0:
    v = q.popleft()
    for next_v in graph[v]:
        if seen[next_v]:
            continue
        q.append(next_v)
        seen[next_v] = True
        dist[next_v] = dist[v] + 1
        pre[next_v] = v

print('Yes')

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

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






q = [1]


ans = ['No' for n in range(N + 1)]
ans[0] = 1  
ans[1] = 1  

while q:  
    now = q.pop(0) 
    for edge in graph[now]:
        if ans[edge] != 'No': 
            continue
        ans[edge] = now
        q.append(edge)

if not 'No' in ans:
    print('Yes')
    for n in range(2, N + 1):
        print(ans[n])
else:
    print('No')

Solution (Python):
from collections import deque

n,m = map(int,input().split())
edge = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    
v = [-1 for i in range(n)]
v[0]=0
q = deque()
q.append(0)
while len(q) > 0:
    x = q.popleft()
    for y in edge[x]:
        if v[y]!=-1:
            continue
        q.append(y)
        v[y] = x

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

Solution (Python):

n, m = map( int, input().split() )
connect = {}

for _ in range( m ):
    a, b = map( int, input().split() )
    try:
        connect[ a ].append( b )
    except KeyError:
        connect[ a ] = [ b ]
    try:
        connect[ b ].append( a )
    except KeyError:
        connect[ b ] = [ a ]

queue = [ 1 ]
guide = [ -1 ] * ( n+1 )
visited = [ False ] * ( n+1 )

while queue:
    x = queue.pop(0)
    for y in connect[ x ]:
        if visited[ y ] == False:
            queue.append( y )
            guide[ y ] = x
            visited[ y ] = True

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

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
            dist[c] = dist[current] + 1
            prev[c] = current
            queue.append(c)

queue = deque([1])
dist = [0] + [-1] * n
dist[1] = 0
prev = [0] + [-1] * n
prev[1] = 0
bfs(graph, queue, dist, prev)
if -1 in prev:
    print('No')
else:
    print('Yes')
    for p in prev[2:]:
        print(p)

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


G = nx.Graph()
N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
G.add_edges_from(edge)
pre = nx.predecessor(G, 1)

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

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

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

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

res = [0]*(n-1)
used = [False]*n

tank = deque([0])
while tank:
    q = tank.popleft()
    if used[q]:
        continue
    used[q] = True

    for go in edge[q]:
        if go == 0 or res[go-1] != 0:
            continue
        res[go-1] = q+1
        tank.append(go)
print("Yes")
print(*res,sep='\n')

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






q = [1]

ans = ['No' for n in range(N+1)]
ans[0] = 1
ans[1] = 1 
while q: 
    
    now = q.pop(0)
    for edge in graph[now]:
        if ans[edge] != 'No':
            continue
        ans[edge] = now
        q.append(edge)

if not 'No' in ans:
    print('Yes')
    for n in range(2,N+1):
        print(ans[n])
else:
    print('No')

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






q = [1]

ans = ['No' for n in range(N+1)]
ans[1] = 1 
while q: 
    
    now = q.pop(0)
    for edge in graph[now]:
        if ans[edge] != 'No':
            continue
        ans[edge] = now
        q.append(edge)

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

Solution (Python):
n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
from collections import deque
d = deque([[0,0]]) 
ans = [-1 for i in range(n)]
kak = [-100 for i in range(n)]
while d:
    u,v = d.popleft()
    ans[u] = v
    for j in g[u]:
        if  kak[j] == -100:
            kak[j] = 0
            d.append([j,u])
        else:
            continue
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

Solution (Python):
import collections


def main():
    n, m = input_list()
    route = [[] for i in range(n)]
    for _ in range(m):
        a, b = input_list()
        route[a-1].append(b-1)
        route[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 route[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()))


if __name__ == '__main__':
    main()

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



Q = deque([])
DIST = [-1 for i in range(n)]
PRE = [-1 for i in range(n)]

DIST[0] = 0
Q.append(0)

while len(Q) > 0:
    x = Q.popleft()  
    for i in range(len(TO[x])):
        y = TO[x][i]
        if DIST[y] != -1: continue
        DIST[y] = DIST[x] + 1
        PRE[y] = x
        Q.append(y)

print('Yes')
for i in range(n):
    if i == 0: continue
    ans = PRE[i] + 1 
    print(ans)

Solution (Python):
from sys import stdin
from collections import deque
from heapq import heappush, heappop


class BreadthFirstSearch:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.adj_list = [[] for _ in range(self.n)]

    
    def add_edge(self, start, end, undirected=True):
        self.adj_list[start].append(end)
        if undirected:
            self.adj_list[end].append(start)

    
    def search(self, start_node):
        order = [-1] * self.n  
        parent = [-1] * self.n  
        depth = [-1] * self.n  
        q = deque([(start_node, -1, 0)])  
        num = 0  
        while len(q) > 0:
            v, p, d = q.popleft()
            if order[v] < 0:  
                order[v] = num
                parent[v] = p
                depth[v] = d
                num += 1
                for u in self.adj_list[v]:
                    if order[u] >= 0:
                        continue
                    q.append((u, v, d+1))
        return order, parent, depth


class Dijkstra:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.adj_list = [[] for _ in range(self.n)]

    
    def add_edge(self, start, end, weight=1, undirected=False):
        self.adj_list[start].append((end, weight))
        if undirected:
            self.adj_list[end].append((start, weight))

    def distance(self, start):
        
        self.dist = [float('inf') for _ in range(self.n)]
        
        self.prev = [-1 for _ in range(self.n)]
        self.dist[start] = 0
        
        q = []
        heappush(q, (0, start))
        while len(q) != 0:
            prov_cost, src = heappop(q)
            
            if self.dist[src] < prov_cost:
                continue
            
            for val in self.adj_list[src]:
                dest, cost = val
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost  
                    heappush(q, (self.dist[dest], dest))  
                    self.prev[dest] = src
        return self.dist, self.prev

    def shortest_path(self, goal):
        path = [goal]
        dest = goal
        
        while self.prev[dest] != float('inf'):
            if self.prev[dest] == -1:
                break
            path.append(self.prev[dest])
            dest = self.prev[dest]
        return path[::-1]


def get_result(data):
    N, M = data[0]
    A = data[1:]
    solver = Dijkstra(N)
    for val in A:
        solver.add_edge(val[0]-1, val[1]-1, undirected=True)
    _, prev = solver.distance(0)
    print('Yes')
    for p in prev[1:]:
        print(p + 1)
    return None















if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    get_result(data)

Solution (Python):
def solve(string):
    from collections import deque
    n, m, *ab = map(int, string.split())
    p = [[] for _ in range(n)]
    for a, b in zip(*[iter(ab)] * 2):
        p[a - 1].append(b - 1)
        p[b - 1].append(a - 1)
    s, ans, d = deque([0]), [0] * n, [0] + [n] * (n - 1)
    while s:
        c = s.popleft()
        for t in p[c]:
            if d[c] + 1 < d[t]:
                d[t] = d[c] + 1
                ans[t] = c + 1
                s.append(t)
    return "Yes\n" + "\n".join(map(str, ans[1:]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
import math
n, k = map(int,input().split())
g={}
for i in range(n):
    g[i]=[]
for i in range(k):
    a,b= map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
ans = [-1] * n
queue = [0]
visited = [False] * n
 

while queue:
    x = queue.pop(0)
    for n in g[x]:
        if visited[n] == False: 
            queue.append(n)
            if ans[n] == -1: 
                ans[n] = x
                visited[n] = True
 
if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for a in ans[1:]:
        print(a+1)

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
que = [1]
ans = [0 for _ in range(N+1)]
while len(que)>0:
  current = que.pop(0)
  for next in g[current]:
    if ans[next] == 0:
      que.append(next)
      ans[next] = current
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Solution (Python):
from collections import defaultdict, deque


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

    route = defaultdict(list)
    for ab in AB:
        route[ab[0]].append(ab[1])
        route[ab[1]].append(ab[0])

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

    
    while(len(que) != 0):
        v = que.popleft()

        for nv in route[v]:
            if ans[nv-1] != -1:
                continue

            ans[nv-1] = v
            que.append(nv)

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


if __name__ == "__main__":
    main()

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

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

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

ans = [-1] * n
queue = [0]
visited = [False] * n


while queue:
    x = queue.pop(0)
    
    for g in tree[x]: 
        if visited[g] == False: 
            queue.append(g)
            if ans[g] == -1: 
                ans[g] = x
                visited[g] = True

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

Solution (Python):
from sys import stdin
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N 
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N 
        self.prev = prev = [-1] * N 
        dist[s] = 0
        n_visited = 1 
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]


def get_result(data):
    N, M = data[0]
    A = data[1:]
    solver = Dijkstra(N)
    for val in A:
        solver.add_edge(val[0]-1, val[1]-1, 1, undirected=True)
    solver.distance(0)
    prev = solver.prev
    print('Yes')
    for p in prev[1:]:
        print(p + 1)
    return None

if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    get_result(data)

Solution (Python):
from collections import defaultdict, deque


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

    route = defaultdict(list)
    for ab in AB:
        route[ab[0]].append(ab[1])
        route[ab[1]].append(ab[0])

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

    
    while(len(que) != 0):
        v = que.popleft()

        for nv in route[v]:
            if ans[nv-1] != -1:
                continue

            ans[nv-1] = v
            que.append(nv)

    print('Yes')
    for i in range(1, N):
        print(ans[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)

dist = [1e8 for i in range(N)]
dist[0] = 0

ans = [-1 for i in range(N)]

Q = deque()
Q.append(0)

while len(Q) > 0:
    now = Q.popleft()

    for to in G[now]:
        if(dist[now] + 1 < dist[to]):
            dist[to] = dist[now] + 1
            ans[to] = now+1
            Q.append(to)

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

Solution (Python):
from _collections import deque
n,m=map(int,input().split())
M=[[] for _ in range(n)]
ANS=[-1]*n
ANS[0]=0
for i in range(m):
    a,b=map(int,input().split())
    M[b-1].append(a-1)
    M[a-1].append(b-1)

q=deque([0])

while q:
    s=q.popleft()
    for x in M[s]:
        if ANS[x]!=-1:
            continue
        q.append(x)
        ANS[x]=s
print('Yes')
for ans in ANS[1:]:
    print(ans+1)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
ary = []
a = []
b = []
ary = [0 for i in range(n)]
chk = [False for i in range(n)]
d = {}
for i in range(m):
	aa, bb = map(int, input().split())
	if aa not in d:
		d[aa] = []
	d[aa].append(bb)
	if bb not in d:
		d[bb] = []
	d[bb].append(aa)

visited = [-1 for i in range(n)]
visited[0] = 0
queue = deque([1])
while queue:
	c = queue.popleft()
	for i in d[c]:
		if visited[i-1] != -1:
			continue
		visited[i-1] = c
		queue.append(i)
for i in visited:
	if i == -1:
		print ("No")
		exit()
print ("Yes")
for i in visited[1:]:
	print (i)

Solution (Python):
from collections import defaultdict
from collections import deque
n , m = map(int , input().split())
g = defaultdict(list)
for i in range(m):
	u , v = map(int , input().split())
	g[u].append(v)
	g[v].append(u)

visited = [False]*(n+1)
a = [10**10]*(n+1)
q = deque()
q.append(1)
while q:
	node = q.popleft()
	visited[node] = True
	for ele in g[node]:
		if not visited[ele]:
			if a[ele] != 10**10: 
				continue
			a[ele] = node
			q.append(ele)


print("Yes")
for i in a[2:]:
	print(i)

Solution (Python):
import networkx as nx
n,m,*s = map(int, open(0).read().split())
 
g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])
for x in zip(*[iter(s)] * 2):
    g.add_edge(x[0],x[1])
di=nx.predecessor(g,source=1)
 
if len(di)!=n:
    print("No");exit()
print("Yes")
for x in range(2,n+1):
    print(di[x][0])

Solution (Python):
n,m = map(int,input().split())
map_li = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    map_li[a].append(b)
    map_li[b].append(a)
 
ans_li = [-1]*n
queue=[0]
visited = [False]*n
 
while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Solution (Python):
from collections import deque

N, M = map(int,input().split())
A=[0]*M
B=[0]*M

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


def BFS(top):
    queue = deque([top])
    dist = [-1]*(N+1)
    dist[1]=0

    queue.extend(graph[top])
    
    while(queue):
        Now_vertex = queue.popleft()
        
        for j in range(len(graph[Now_vertex])):
            if(dist[graph[Now_vertex][j]]==-1):
                queue.append(graph[Now_vertex][j])
                dist[graph[Now_vertex][j]]=Now_vertex
            
    print("Yes")
    for i in range(2,len(dist)):
        print(dist[i])
    
        
    return



BFS(1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
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())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
q = deque()
done = [-1]*N
done[0] = 1
q.appendleft(0)
while q:
    now = q.pop()
    for to in G[now]:
        if done[to] != -1: continue
        done[to] = now+1
        q.appendleft(to)
print("Yes")
print(*done[1:], sep="\n")

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

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

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

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Solution (Python):
import numpy as np
from collections import deque
N,M = [int(i) for i in input().split()]
roads = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    roads[A].append(B)
    roads[B].append(A)
places = [0]*(N+1)
places[1] = 1
q = deque([1])
vis = [False]*(N+1)
vis[1] = True
while q:
    now = q.popleft()
    L = roads[now]
    for j in L:
        if vis[j]:
            continue
        vis[j] = True
        places[j] = now
        q.append(j)

print("Yes")
s = "\n".join(map(str, places[2:]))
print(s)

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

next_vec = [0]
visited = [1] + [0] * (N-1)
parent = [-1] + [0] * (N-1)
flag = 1


while next_vec:
    current_vec = next_vec[:]
    next_vec = []
    while current_vec:
        u = current_vec.pop()
        visited[u] = 1
        for v in path[u]:
            if visited[v] == 0:
                visited[v] = 1
                parent[v] = u
                next_vec.append(v)

ans_flag = 1
for i in visited:
    if i == 0:
        ans_flag = 0
if ans_flag:
    print('Yes')
    for i in range(1,N):
        print(parent[i]+1)
else:
    print('No')

Solution (Python):
from collections import deque

def bfs2(g,n,m):
    pre=[0 for _ in range(n+1)]
    pre[1]=1
    q=deque([1])
    while q:
        x=q.popleft()
        for i in range(len(g[x])):
            if pre[g[x][i]]==0:
                q.append(g[x][i])
                pre[g[x][i]]=x
    return pre

def main2():
    
    n,m=map(int,input().strip().split())
    g=[[] for _ in range(n+1)]
    for _ in range(m):
        a,b=map(int,input().strip().split())
        g[a].append(b)
        g[b].append(a)
        
    pre=bfs2(g,n,m)
    
    print("Yes" if 0 not in pre[1:] else "No")
    for i in range(2,len(pre)):
        print(pre[i])

if __name__=="__main__":
    main2()

Solution (Python):
from collections import deque

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)
ans = [0] * (n + 1)
f = [0] * (n + 1)
d = deque()
d.append(1)
while len(d) > 0:
    k = d.popleft()
    f[k] = 1
    for i in l[k]:
        if f[i] == 1:
            continue
        ans[i] = k
        d.append(i)
        f[i] = 1
for i in range(2, n + 1):
    if ans[i] == 0:
        print("No")
        exit()
print("Yes")
for i in range(2, n + 1):
    print(ans[i])