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):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque


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



def bfs(start):
    distance = [-1 for _ in range(N)]
    Q = deque()
    Q.append(start)
    d = [-2 for _ in range(N)]
    d[start] = -1
    distance[start] = 0
    while len(Q) > 0:
        u = Q.popleft()
        for v in G[u]:
            if d[v] == -2:
                Q.append(v)
                d[v] = u  
                distance[v] = distance[u] + 1
    
    return d, distance

p, distance = bfs(0)


for path in p:
    if path == -2:
        print("No")
else:
    print("Yes")
    for path in p[1:]:
        print(path + 1)

Solution (Python):
from collections import deque
deck=deque()

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


not_visited=[1 for i in range(n)]
not_visited[0]=0

deck.append(0)
while len(deck)!=0:
    target=deck.popleft()
    tsuuro=tsuuro_list[target]
    for node in tsuuro:
        if not_visited[node]:
            not_visited[node]=0
            deck.append(node)
            saiteki[node]=target

if sum(not_visited)!=0:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(saiteki[i]+1)

Solution (Python):

from collections import deque
N, M = map(int, input().split())
graph = {i:deque() for i in range(1, N+1)}

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

seen = [0]*(N+1)
queue = deque()
dist = [-1]*(N+1)
dicgq = {i: 0 for i in range(2, N+1)}
dicqg = {i: 0 for i in range(2, N+1)}

def bfs(v):
    dist[v] = 0
    seen[v] = 1
    queue.append(v)
    while queue:
        q = queue[0]
        if not graph[q]:
            queue.popleft()
            continue
        g = graph[q].popleft()
        if seen[g]:
            continue
        seen[g] = 1
        dist[g] = dist[q] + 1
        dicgq[g] = q 
        dicqg[q] = g 
        queue.append(g)

bfs(1)
pre_dis = dist.copy()

for i in range(2, N+1):
    graph[i] = dicqg[i]



seen = [0]*(N+1)
queue = deque()
def bfs2(v):
    dist[v] = 0
    seen[v] = 1
    queue.append(v)
    while queue:
        q = queue[0]
        if not graph[q]:
            queue.popleft()
            continue
        g = graph[q].popleft()
        if seen[g]:
            continue
        seen[g] = 1
        dist[g] = dist[q] + 1
        
        queue.append(g)


bfs2(1)
if pre_dis != dist:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(dicgq[i])

Solution (Python):
def main():
    N, M = map(int, input().split())
    d = {}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    v = set()
    v.add(0)
    l = [0] * N
    c = set()
    c.add(0)
    r = 0
    while len(v) < N:
        n = set()
        for i in c:
            for j in d[i]:
                if j not in v:
                    l[j] = i
                    v.add(j)
                    n.add(j)
        c = n
    print('Yes')
    for i in range(1,N):
        print(l[i] + 1)
main()

Solution (Python):
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) 
    path[B-1].append(A)
    
    

visited = [False for _ in range(N)]
que = [1]
visited[0] = True
sign = [-1 for _ in range(N)]

while True:
    next_que = []
    if not que:
        break



    else:
        for q in que:
            probable_room = path[q-1]
            for p in probable_room:


                if visited[p-1]:
                    continue
                else:

                    visited[p-1] = True
                    sign[p-1] = q
                    next_que.append(p)
    que = next_que
if all(visited):
    print("Yes")
    for i in range(1,N):
        print(sign[i])
else:
    print("No")

Solution (Python):
from collections import deque

def bfs(s):
    status[s] = VISITING
    signs[s] = 0
    Q.append(s)
    while len(Q) > 0:
        u = Q.popleft()
        for v in rooms[u]:
            if status[v] == NOT_VISITED:
                status[v] = VISITING
                signs[v] = u
                Q.append(v)
        status[u] = VISITED


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

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

INFTY = float('inf')
signs = [INFTY] * n

NOT_VISITED = 0
VISITING = 1
VISITED = 2
status = [NOT_VISITED] * n
Q = deque()

bfs(0)
ok = True

for sign in signs:
    if sign == INFTY:
        ok = False

if ok:
    print('Yes')
    signs = signs[1:]
    for sign in signs:
        print(sign + 1)

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

cnt = 0
check = [False for _ in range(n)]
check[0] = True
listA = [0]
listB = []
michishirube = [-1 for _ in range(n)]
while len(listA) > 0:
	
	listB = []
	for la in listA:
		for laa in ab[la]:
			if not check[laa]:
				michishirube[laa] = la
				listB.append(laa)
				check[laa] = True
				cnt += 1
	listA = listB

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

Solution (Python):

from collections import deque


def bfs(u):
    queue = deque([u])
    d = [None] * N  
    d[u] = 0  
    ans = [0] * N
    while queue:
        v = queue.popleft()
        for i in g[v]:

            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                ans[i] = v + 1
    return ans

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

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

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

Solution (Python):
from collections import deque


def main():
    n, m = [int(x) for x in input().split()]
    corridors = [list() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        corridors[a].append(b)
        corridors[b].append(a)

    qu = deque()
    
    ans = [None] * n
    
    qu.append(0)
    ans[0] = 0
    
    while len(qu):
        v = qu.popleft()
        for new in corridors[v]:
            if ans[new] is not None:
                continue
            
            ans[new] = v + 1
            qu.append(new)

    
    
    
    

    print('Yes')
    for x in ans[1:]:
        print(x)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n,m = map(int, input().split())

INF = 1001001001

to = [[] for _ in range(n)]
dist = [INF]*n
dist[0] = 0
ans = [-1]*n
ans[0] = [0]

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

import queue

q = queue.Queue()
used = [0]*n
q.put(0)
used[0] = 1 

while not q.empty():
    v = q.get()
    for i in range(len(to[v])):
        u = to[v][i]
        if used[u]: continue
        if dist[v]+1 < dist[u]:
            dist[u] = dist[v]+1
            ans[u] = v
        q.put(u)
        used[u] = 1 

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

Solution (Python):
from heapq import heappush, heappop

def dijkstra(graph, start):
    
    INF = float("inf")

    num = len(graph)
    dist = [INF] * num
    prev = [INF] * num

    dist[start] = 0
    q = []
    heappush(q, (0, start))
    
    while len(q) != 0:
        prov_cost, src = heappop(q)

        if dist[src] < prov_cost:
            continue
        
        for edge in graph[src]:
            cost = edge[1]
            dest = edge[0]

            if dist[dest] > dist[src] + cost:
                 dist[dest] = dist[src] + cost
                 heappush(q, (dist[dest], dest))
                 prev[dest] = src
        
    return prev

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

    path = dijkstra(G, 0)
    
    print("Yes")
    for i in range(1, n):
        print(path[i] + 1)

if __name__ == "__main__":
    main()

Solution (Python):
import queue
N, M = map(int, input().split())
q=queue.Queue()
room=[['' for i in range(0)] for j in range(N+1)]
checkRoom=[0 for j in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    room[A].append(B)
    room[B].append(A)
q.put(1)
while not q.empty():
    checkI=q.get()
    for j in range(len(room[checkI])):
        if checkRoom[room[checkI][j]]==0:
            q.put(room[checkI][j])
            checkRoom[room[checkI][j]]=checkI
print("Yes")
for i in range(2,N+1):
    print(checkRoom[i])

Solution (Python):
n,m = map(int,input().split())
node_dict = {i:set() for i in range(1,n+1,1)}
for i in range(m):
    tmp1,tmp2 = map(int,input().split())
    node_dict[tmp1].add(tmp2)
    node_dict[tmp2].add(tmp1)
mitishirube_list = [1]
tansaku_set = set([i for i in range(2,n+1,1)])
tansakusumi_list = []
while(tansaku_set != set()):
    tmp_list = mitishirube_list
    mitishirube_list = []
    for i in tmp_list:
        for j in node_dict[i] & tansaku_set:
            tansakusumi_list.append([j,i])
            tansaku_set.remove(j)
            mitishirube_list.append(j)
tansakusumi_list.sort()
print("Yes")
for i in tansakusumi_list:
    print(i[1])

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

seen = [False for i in range(n)]
que = deque()
def bfn(i,j):
    for x in pas[i]:
        if seen[x-1]!=False:
            continue
        seen[x-1]=i
        que.append([x,i])
    if que:
        now,pre =que.popleft()
        bfn(now,pre)
    else:
        return

bfn(1,1)

if False in seen:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(seen[i+1])

Solution (Python):
import queue




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)

sign = [-1] * N
que = queue.Queue()
que.put(0)

while not que.empty():
    v = que.get()
    for nv in G[v]:
        if sign[nv] != -1:
            continue
        sign[nv] = v
        que.put(nv)

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

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

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

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

a = [-1] * (n+1)
d = deque()
d.append(1)
while d:
    u = d.popleft()
    for child in net[u]:
        if a[child] != -1:continue
        a[child] = u
        d.append(child)
a = a[2:]
for z in a:
    if z == -1:
        print("No")
        exit()
print("Yes")
for z in a:
    print(z)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    
    
    from heapq import heapify, heappop, heappush

    N, M = map(int, input().split())
    inf = 10 ** 17

    def dijkstra_heap(start, edge):
        
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)

        while len(edgelist):
            
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d

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

    d = dijkstra_heap(0, edge)
    max_times = max(d)

    times_list = [[] for _ in range(max_times+1)]
    for id, val in enumerate(d):
        times_list[val].append(id)

    def main():
        mark = [0]+[-1]*(N-1)
        cur = 1
        for i in range(1, N):
            if d[i] == 1:
                mark[i] = 0
            else:
                if times_list[d[i]-1]:
                    mark[i]=times_list[d[i]-1][0]
                else:
                    return False
        return mark[1:]

    if main():
        print('Yes')
        for i in main():
            print(i+1)
    else:
        print('No')

resolve()

Solution (Python):
import collections

def get_input():
    return list(map(lambda x:int(x), input().split()))

def main():
    inp = get_input()
    n, m = inp[0], inp[1]
    adj_list = [[] for i in range(n)]
    for i in range(m):
        inpu = get_input()
        a, b = inpu[0], inpu[1]
        adj_list[a - 1].append(b - 1)
        adj_list[b - 1].append(a - 1)
    
    q = collections.deque()
    visited = set()
    q.append(0)
    visited.add(0)
    p = [-1] * n

    
    while q:
        u = q.popleft()
        for i in adj_list[u]:
            
            if i not in visited:
                q.append(i)
                visited.add(i)
                p[i] = u
    
    
    for i in range(1, len(p)):
        if p[i] == -1:
            print("No")
            return

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

if __name__ == '__main__':
    main()

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

room_dict = {i+1:[] for i in range(N)}
for _ in range(M):
  _a, _b = list(map(int, input().split()))
  room_dict[_a].append(_b)
  room_dict[_b].append(_a)

rooms = set(room_dict.keys())
s_dict = {i+1:None for i in range(1, N)}
traversed_rooms = set([1])

now_rooms = [1]
from operator import add
while now_rooms:
    next_rooms = set()
    for _room in now_rooms:
        traversed_rooms.add(_room) 
        _n_rooms  = [i for i in room_dict[_room] 
                         if (not i in traversed_rooms) and (s_dict[i] is None)]
        for n_room in _n_rooms:
            next_rooms.add(n_room) 
            s_dict[n_room] = _room 
    now_rooms = [i for i in next_rooms if not i in traversed_rooms] 
    
print('Yes') 

for i in range(2, N+1):
    print(s_dict[i])

Solution (Python):
N, M = map(int, input().split())
root = [[] for _ in range(N+1)]

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

ans = [10**9] * (N+1)
ans[0] = 0
ans[1] = 0

from collections import deque
q = deque([1])

while q:
    p = q.popleft()
    for i in root[p]:
        if ans[i] == 10**9:
            ans[i] = p
            q.append(i)

if 10**9 in set(ans):
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(ans[i])

Solution (Python):
nm = input().split()
n = int(nm[0])
m = int(nm[1])

load = []
load_roomn = {}

for i in range(m):
  l = list(map(lambda x:int(x), input().split()))
  load.append(l)
  
  if l[0] in load_roomn:
    load_roomn[l[0]].append(i)
  else:
    load_roomn[l[0]] = [i]
  if l[1] in load_roomn:
    load_roomn[l[1]].append(i)
  else:
    load_roomn[l[1]] = [i]
    



visitCost = [10^5+1]*(n+1)

marker = [-1]*(n+1)
marker[1] = 0
visitable = [1]
visited = []
visitednum = 1


while visitednum < n:
  
  
  visiting = visitable.pop(0)
  
  for i in load_roomn[visiting]:
    if load[i][0] == visiting:
      if marker[load[i][1]] == -1:
        visitable.append(load[i][1])
        marker[load[i][1]] = visiting
        visitednum += 1
        
    elif load[i][1] == visiting:
      if marker[load[i][0]] == -1:
        visitable.append(load[i][0])
        marker[load[i][0]] = visiting
        visitednum += 1
        
    else:
      print("error")

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

Solution (Python):
from collections import deque

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

n, m = map(int, input().split())
a, b = [], []
nodes = []

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(m):
    A, B = map(int, input().split())
    nodeA, nodeB = nodes[A-1], nodes[B-1]
    nodeA.adj.append(nodeB)
    nodeB.adj.append(nodeA)
    
    

q = deque()
q.append(nodes[0])
done = set()

while q:
    node = q.popleft()
    parent = node.val

    for adj in node.adj:
        if adj not in done:
            done.add(adj)
            adj.sign = parent
            q.append(adj)
            
print('Yes')            

for i in range(1, len(nodes)):
    print(nodes[i].sign)

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

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

out=[0 for i in range(n)]

seen={1}
next=[[1],[]]
i=0
while len(next[0])+len(next[1]) != 0:
    if i == 0:
        x=1
    else:
        x=0
    
    for j in next[i]:
        for k in ilist[j-1]:
            if not k in seen:
                seen.add(k)
                next[x].append(k)
                out[k-1]=j
    next[i]=[]
    i=x

print("Yes")
for o in out[1:]:
    print(o)

Solution (Python):
from collections import deque,defaultdict
import sys
rel=defaultdict(set)
n,m=map(int,input().split())
for s in sys.stdin:
  a,b=map(int,s.split())
  rel[int(a)].add(int(b))
  rel[int(b)].add(int(a))
cand=deque([1])
visited=set([1])
dlist=[0]*n
while len(visited)!=n:
  now=cand.popleft()
  for i in rel[now]:
    if i not in visited:
      cand.append(i)
      visited.add(i)
      dlist[i-1]=now
print('Yes')
print(*dlist[1:],sep='\n')

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

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

edges = [[] for j in range(N+1)]
for p in path:
    x, y = p
    edges[x].append(y)
    edges[y].append(x)

que = deque([])
dic = {1: 0}
def bfs(now):
    e = edges[now]
    for q in e:
        if not q in dic:
            dic[q] = now
            que.append(q)
    try:
        n = que.popleft()
        bfs(n)
    except IndexError:
        pass

bfs(1)

if len(dic) != N:
    print("No")
else:
    print('Yes')
    dic_sort = sorted(dic.items())
    for elem in dic_sort:
        if elem[0] != 1:
            print(elem[1])

Solution (Python):
import sys
input = sys.stdin.readline

from collections import deque

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

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

d = [-1] * (N + 1)
ans = [-1] * (N + 1)
que = deque()
root = 1
ans[root] = 0
que.append(root)
while que:
    now = que.popleft()
    for next_ in G[now]:
        if ans[next_] == -1:
            que.append(next_)
            ans[next_] = now

for i in ans[1:]:
    if i == -1:
        print ('No')
        exit()
print ('Yes')
print (*ans[2:], sep = '\n')

Solution (Python):
import sys


def input():
    return sys.stdin.readline()[:-1]


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

ans = [0]*(N-1)
next_root = [0]
zumi = {}
while True:
    
    for root in next_root:
        if not(root in zumi):
            break
    else:
        break

    tmp_next_root = []
    for root in next_root:
        if root in zumi:
            continue
        for v in tree[root]:
            if v in zumi:
                continue
            if ans[v-1] == 0:
                ans[v-1] = root+1
                tmp_next_root.append(v)
        zumi[root] = True
    next_root = tmp_next_root

if ans.count(0) == 0:
    print('Yes')
    for a in ans:
        print(a)
else:
    print('No')

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

que = []
seen = [-1 for i in range(n+1)]
back = [-1 for i in range(n+1)]

seen[1] = 0
que.append(1)

while len(que) != 0:
  now = que.pop(0)
  
  for nxt in cave[now]:
    if seen[nxt] != -1:
      continue
    
    seen[nxt] = seen[now] + 1
    back[nxt] = now
    que.append(nxt)
    
flag = True
for i in back[2:]:
  if i == -1:
    flag = False

if flag == True:
  print("Yes")
  for i in back[2:]:
    print(i)
else:
  print("No")

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  ans=[-1]*n

  q=collections.deque()
  v=[[] for _ in range(n)]
  for _ in range(m):
    a,b=LI()
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    if a==0:
      q.append((0,b,0))
    elif b==0:
      q.append((0,a,0))

  while q:
    moto,nxt,stp=q.popleft()
    if ans[nxt]==-1:
      ans[nxt]=moto
    else:
      continue

    for x in v[nxt]:
      if ans[x]==-1:
        q.append((nxt,x,stp+1))

  if -1 in ans[1:]:
    print('No')
    exit()

  print('Yes')
  for x in ans[1:]:
    print(x+1)

main()

Solution (Python):
N, M = list(map(int, input().split()))
AB = []
for i in range(M):
    AB.append(list(map(int, input().split())))

rinsetu = {}
mitisirube = {}
kyori = {}
for i in range(1, N+1):
    rinsetu[i] = []
    mitisirube[i] = None
    kyori[i] = None
kyori[1]=0

for ab in AB:
    rinsetu[ab[0]].append(ab[1])
    rinsetu[ab[1]].append(ab[0])

queue = [1]
while queue:
    this = queue.pop(0)
    
    for r in rinsetu[this]:
        if kyori[r] is None:
            kyori[r] = kyori[this] + 1
            mitisirube[r] = this
            queue.append(r)





all_mitisirube = [mitisirube[i] for i in range(2, N+1)]
if None in all_mitisirube:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(mitisirube[i])

Solution (Python):
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())


def solve(N, M, graph):
    dist = {0: 0}
    queue = [0]
    parent = {}
    for node in queue:
        for nei in graph[node]:
            if nei not in dist:
                dist[nei] = dist[node] + 1
                parent[nei] = node
                queue.append(nei)

    if len(parent) != N - 1:
        return
    return [parent[i] for i in xrange(1, N)]

N, M = rrm()
graph = [[] for _ in xrange(N)]
for _ in xrange(M):
    u,v = rrm()
    u -= 1;v-=1
    graph[u].append(v)
    graph[v].append(u)
ans= solve(N,M,graph)
if ans is None:
    print "No"
else:
    print "Yes"
    for x in ans: print x+1

Solution (Python):
n,m=map(int,input().split())
link=[[] for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  link[a-1].append(b-1)
  link[b-1].append(a-1)
q=[0]
visited=[0]*n
visited[0]=1
while q:
  x=q.pop(0)
  for i in link[x]:
    if visited[i]==0:
      visited[i]=x+1
      q.append(i)
print('Yes')
print(*visited[1:],sep='\n')

Solution (Python):

from collections import defaultdict

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

paths = defaultdict(list)

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

checked = set([1])
ct = set([1])
rp = defaultdict(int)

while ct:
    nt = set()
    for r in ct:
        for nr in paths[r]:
            if nr in checked:
                continue
            rp[nr] = r
            checked.add(nr)
            nt.add(nr)
            
            
    ct = nt

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

Solution (Python):
import numpy
import queue

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

r=[]
for i in range(n):
    r.append([])

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


mark=numpy.zeros(n,dtype=int)

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

while q.empty()==False:
    c=q.get()
    for i in iter(r[c-1]):
        if mark[i-1]==0:
            q.put(i)
            mark[i-1]=c


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

Solution (Python):

"""
Created on Sun May 17 20:56:20 2020

@author: Kanaru Sato
"""
import collections

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

distance = [-1,0]
for i in range(n-1):
    distance.append(-1)

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

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

while q:
    cp = q.popleft()
    for np in connected[cp]:
        if ans[np] == -1 or distance[ans[np]] > distance[cp]:
            q.append(np)
            ans[np] = cp
            distance[np] = distance[cp] + 1

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

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())
    a -= 1
    b -= 1
    rooms[a].append(b)
    rooms[b].append(a)
reached = [-1]*N
def bfs():
    d = deque() 
    d.append(0)
    reached[0] = 0
    while d:
        
        now = d.popleft()
        for i in rooms[now]:
            
            if reached[i] == -1:
                reached[i] = now
                d.append(i)
bfs()
print('Yes')
for i in range(1,N):
    print(reached[i]+1)

Solution (Python):

import sys
from heapq import heappush,heappop,heapify

N,M=map(int, sys.stdin.readline().split())

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

for _ in range(M):
	a,b=map(int, sys.stdin.readline().split())
	al[a].append(b)
	al[b].append(a)

d=[ float("inf") for _ in range(N+1)]
restore=[ None for _ in range(N+1)]


def dij(fro):
	d[fro]=0
	hq=[]
	heappush(hq,(0,fro))
	while hq:
		cost,fro=heappop(hq)
		for to in al[fro]:
			alt=d[fro]+1
			if alt<d[to]:
				d[to]=alt
				restore[to]=fro
				heappush(hq, (alt,to))

dij(1)

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

Solution (Python):
import sys
sys.setrecursionlimit(9**9)
n,m=map(int,input().split())
L=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
A=[0]+[-1]*(n-1)
B=[[0,L[0]]]
def wfs(A,B):
    C=[]
    f=False
    for b in B:
        for l in b[1]:
            if A[l]==-1:
                A[l]=b[0]
                C.append([l,L[l]])
                f=True
    if f:
        return wfs(A,C)
    else:
        print('Yes')
        for a in A[1:]:
            print(a+1)
wfs(A,B)

Solution (Python):
import sys
from collections import deque

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

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

for A, B in AB:
    doors[A-1].append(B)
    doors[B-1].append(A)



answer = [sys.maxsize for _ in range(N-1)]
distance = [sys.maxsize for _ in range(N)]
distance[0] = 0
q = deque([1])

while len(q) > 0:
  current = q.popleft()
  for nextroom in doors[current-1]:
    if distance[current-1] + 1 < distance[nextroom-1]:
        q.append(nextroom)
        distance[nextroom-1] = distance[current-1] + 1
        answer[nextroom-2] = current
    else:
        pass
if sys.maxsize in answer:
    print('No')
    exit()
print('Yes')
for a in answer:
    print(a)

Solution (Python):
from queue import Queue

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

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

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

shortest_adj = [None] * n
room_queue = Queue()
room_queue.put(0)
while not room_queue.empty():
    room = room_queue.get()
    for next_room in adj_list[room]:
        if shortest_adj[next_room] is None:
            shortest_adj[next_room] = room
            room_queue.put(next_room)

can_reach = all([x is not None for x in shortest_adj])

if not can_reach:
    print('No')
    exit()

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