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 heapq
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')


def dijkstra_heap(s):
    
    d = [float("inf")] * N
    used = [True] * N 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e+[s])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        pn = minedge[2]
        pns[v] = pn
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, [e[0]+d[v], e[1], v])
    return d

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

pns = [0]*N
dijkstra_heap(0)

print('Yes')
for pni in pns[1:]:
    print(pni+1)

Solution (Python):
N,M=map(int,input().split())
l=[set() for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  l[a-1].add(b-1)
  l[b-1].add(a-1)
ope=[1]*N
ope[0]=0
s={0}
ans=[-1]*N
while len(s):
  news=set()
  for j in s:
    for k in l[j]:
      if ope[k]:
        news.add(k)
        ans[k]=j
        ope[k]=0
  s=news
print('Yes')
for i in range(1,N):
  print(ans[i]+1)

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

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

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

for a, b in ab:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

seen = [-1] * N

seen[0] = 1


def bfs(x):
    q = deque([])
    q.append(x)

    while q:
        now = q.popleft()

        for nex in graph[now]:
            if seen[nex] != -1:
                continue
            seen[nex] = now + 1
            q.append(nex)


bfs(0)

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

Solution (Python):
import math

n, m = map(int, input().split())
ansTimes = [10**6]*(n+1)
ans = [0]*(n+1)
ansTimes[1] = 0
routeList = [[] for j in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    routeList[a].append(b)
    routeList[b].append(a)

checkedList = [0]*(n+1)
tugiChecks = [1]
while tugiChecks != []:
    i = tugiChecks.pop(0)
    for target in routeList[i]:
        if ansTimes[i]+1 < ansTimes[target]:
            ansTimes[target] = ansTimes[i]+1
            ans[target] = i
        if checkedList[target] == 0:
            tugiChecks.append(target)
            checkedList[target] = 1


if 10**6 in ansTimes[1:]:
    print("No")
else:
    print("Yes")
    for i in range(2, n+1):
        print(ans[i])

Solution (Python):
from sys import stdin
from collections import deque, Counter, defaultdict
import heapq

INF = int(1e10)
MOD = int(1e9 + 7)

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

class Dijkstra:
    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) > 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        return prev

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

def main():
    from builtins import int, map
    n, m = map(int,input().split())
    route_map = [dict() for _ in range(n)]
    for i in range(m):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        route_map[u][v] = 1
        route_map[v][u] = 1

    prev = Dijkstra(route_map, 0).execute()
    print("Yes")
    for i in range(1, n):
        print(prev[i] + 1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

explored = {0}

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

q = deque()
parent = 0
for k in graph[0]:
    ans[k] = 0
    q.append(k)
    explored.add(k)
ans[0] = 0
while len(q) != 0:
    now = q.popleft()
    parent = now
    for node in graph[now]:
        if node not in explored:
            q.append(node)
            ans[node] = parent
            explored.add(node)

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

Solution (Python):
import heapq




def dijkstra(e,n,s):
    inf = 10**18
    d = [inf]*n
    prev = [s]*n
    d[s] = 0

    q = [(d[s],s)] 
    heapq.heapify([q])
    while len(q)>0:
        _,v = heapq.heappop(q)
        for u,c in e[v]:
            if d[v]+c>=d[u]:
                continue
            d[u] = d[v] + c
            prev[u] = v
            heapq.heappush(q, (d[u],u))
    return d, prev

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

d,prev = dijkstra(e,n,0)
if max(d)==10**18:
    print("No")
    exit()
print("Yes")
for i in range(1,n):
    print(prev[i]+1)

Solution (Python):
from collections import deque

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

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


todo = deque()
seen = set()

todo.append(0)
seen.add(0)

ans = [-1 for _ in range(N)]
while len(todo) > 0:
    here = todo.popleft()
    for neighbor in G[here]:
        if neighbor not in seen:
            todo.append(neighbor)
            seen.add(neighbor)
            if ans[neighbor] == -1:
                ans[neighbor] = here

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

Solution (Python):
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy




def main():
    N,M = map(int,input().split())
    shirube = [None]*(N+1)
    shirube[1] = (1,0)
    mmap = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int,input().split())
        mmap[a].append(b)
        mmap[b].append(a)
    queue = deque()
    queue.appendleft((1,0))
    while queue:
        current_node, distance = queue.pop()
        for next_node in mmap[current_node]:
            new_distance = distance+1
            if shirube[next_node] is None:
                shirube[next_node] = (current_node, new_distance)
                queue.appendleft((next_node, new_distance))
            elif shirube[next_node][1] > new_distance:
                shirube[next_node] = (current_node, new_distance)
                queue.appendleft((next_node, new_distance))
    shirube = shirube[1::]
    if None in shirube:
        print("No")
        return
    print("Yes")
    for s in shirube[1::]:
        print(s[0])


if __name__ == '__main__':
    main()

Solution (Python):
def resolve():
    from collections import deque
    n,m = map(int,input().split()) 
    edge = [[] for i in range(n+1)]
    visit=[-1]*(n+1)
    for i in range(m):
        a,b = map(int,input().split())
        edge[a].append(b)
        edge[b].append(a)
    chk=deque()
    chk.append([1,0])
    while chk:
        x,bx=chk.popleft()
        if visit[x]>-1:
            continue
        visit[x]=bx
        bx=x
        for i in edge[x]:
            if visit[i]>-1:
                continue
            chk.append([i,bx])
    print('Yes')
    for i in visit[2:]:print(i)

if __name__ == '__main__':
    resolve()

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

result = [0] * (N+1)
c = []
flag = [0]*N
for x in X[1]:
    result[x] = 1
    c.append(x)
    flag[x-1]=True

c_new = []
while not all(flag):
    for x in c:
        for y in X[x]:
            if flag[y-1] == False:
                result[y] = x
                c_new.append(y)
                flag[y-1] = True
    c = c_new
    c_new = []

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

Solution (Python):


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


N, M = LI()
A, B = [None] * M, [None] * M
for i in range(M):
    A[i], B[i] = LI()
    A[i] -= 1
    B[i] -= 1


link = [[] for _ in range(N)]
for a, b in zip(A, B):
    link[a].append(b)
    link[b].append(a)


def solve(w):
    l = link[0]
    visit = [False] * N
    visit[0] = True
    for x in l:
        visit[x] = True
        w[x] = 1
    while len(l) > 0:
        next_list = []
        for x in l:
            for v in link[x]:
                if not visit[v]:
                    visit[v] = True
                    w[v] = x + 1
                    next_list.append(v)
        l = next_list
    
    return True


def main():
    w = [None] * N
    solve(w)
    print("Yes")
    for ans in w[1:]:
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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)

    def dfs(v, p):
        for u in tree[v]:
            if u == p:
                continue
            elif visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u, v)

    visited = [False for _ in range(n)]
    visited[0] = True
    dfs(0, -1)
    for i in visited:
        if not i:
            print("No")
            exit()

    def bfs(v):
        pre = [-1 for _ in range(n)]
        pre[0] = 0
        q = deque()
        q.append(v)
        while q:
            u = q.popleft()
            for nv in tree[u]:
                if pre[nv] == -1:
                    pre[nv] = u
                    q.append(nv)
        return pre

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


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque

n,m = (int(x) for x in input().split())

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

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



flag = [False]*(n+1)

vs = deque([1])

flag[1] = True
res = [0]*(n+1)

while(vs):
    this_v = vs[0]
    for i in E[this_v]:
        if flag[i]:
            continue
        else:
            res[i] = this_v
            flag[i] = True
            vs.append(i)
    vs.popleft()
            
print("Yes")
for i in res[2:]:
    print(i)

Solution (Python):



N,M=map(int,input().split())
C=[[] for _ in range(N)]
for _ in range(M):
    ai,bi=map(int,input().split())
    C[ai-1].append(bi)
    C[bi-1].append(ai)

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

from collections import deque
que = deque([1])
while que:
    new = que.popleft()-1
    for c in C[new]:
        if D[c-1]==-1:
            que.append(c)
            D[c-1] = new+1

if -1 in D[1:N]:
    print('No')
    exit()
print('Yes')
for i in range(1,N):
    print(D[i])

Solution (Python):


n, m = map(int, input().split())
dict_road = {}
dict_room = {}
for i in  range(0, m):
    a, b = map(int, input().split())
    if a in dict_road:
        dict_road[a].append(b)
    else:
        dict_road[a] = [b]
    if b in dict_road:
        dict_road[b].append(a)
    else:
        dict_road[b] = [a]
start_list = dict_road[1]
temp_list = []
for no in start_list:
    dict_room[no] = 1
    temp_list.append(no)

while True:
    next_temp_list = []
    for no in temp_list:
        for next_no in dict_road[no]:
            if next_no not in dict_room:
                dict_room[next_no] = no
                next_temp_list.append(next_no)
    if len(next_temp_list) == 0:
        break
    temp_list = next_temp_list
print("Yes")
for i in range(2, n + 1):
    print(dict_room[i])

Solution (Python):
n, m = [int(_) for _ in input().split()]
w = {}
seen = {}
d = {}
for i in range(n):
    w[i+1] = []
    seen[i+1] = 0
    d[i+1] = -1
for i in range(m):
    a, b = [int(_) for _ in input().split()]
    w[a].append(b)
    w[b].append(a)





que = [1]
n_que = []

seen[1] = 1

while len(que) != 0:
    for i in range(len(que)):
        p = que.pop()
        for u in w[p]:
            if seen[u] == 0:
                d[u] = p
                seen[u] = 1
                n_que.append(u)
            else:
                continue
    que = n_que
    n_que = []




flag = 1
for i in range(n):
    if seen[i+1] == 0:
        flag = 0

if flag == 0:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        
        
        print(d[i+1])

Solution (Python):
N,M = map(int,input().split())
path_list = []
for i in range(N):
    z = []
    path_list.append(z)
for i in range(M):
    A,B = map(int,input().split())
    path_list[A-1].append(B)
    path_list[B-1].append(A)
chk = [0] * N

def bfs(a,chk,path):
    queue = [a]
    while queue:
        b = queue.pop(0)
        for i in range(len(path[b-1])):
            if chk[path[b-1][i]-1] == 0:
                queue.append(path[b-1][i])
                chk[path[b-1][i]-1] =b
    return chk
bfs(1,chk,path_list)
print("Yes")
for i in range(N):
    if i == 0:
        continue
    else:
        print(chk[i])

Solution (Python):
from collections import deque
N, M = map(int,input().split())
signs = [set() for _ in range(N)]
for i in range(M):
    A, B = map(int,input().split())
    signs[A-1].add(B-1)
    signs[B-1].add(A-1)
Q = deque()
check = [0]*N
ans = [10**6]*N
x = 0
for gen in signs[x]:
    check[gen] = 1
    ans[gen] = x
    Q.append(gen)
while len(Q) != 0:
    v = Q.popleft()
    for gen in signs[v]:
        if check[gen] == 0:
            check[gen] = 1
            ans[gen] = v
            Q.append(gen)
if 10**6 in ans:
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i+1)

Solution (Python):
from collections import deque

N,M=list(map(int,input().split()))
g=[set() for _ in range(N+1)]
visit=[0]*(N+1)
anslst=[0]*(N+1)

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

q=deque([1])
visit[1]=1

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

    for v in g[u]:
        if visit[v]==1:
            continue

        anslst[v]=u
        visit[v]=1
        q.append(v)

if sum(visit)==N:
    print('Yes')
    for i in range(2,N+1):
        print(anslst[i])
else:
    print('No')

Solution (Python):
N, M = map(int, input().split())
root_list = [ [] for i in range(N) ]
check_list = [0 for i in range(N)]
ans_list = [0 for i in range(N)]

check_list[0] = 1

for m in range(M):
  A, B = map(int, input().split())
  A,B = A-1,B-1

  root_list[A].append(B)
  root_list[B].append(A)





this_order_check = [0]
this_order_check_next = []

now_ok = 0

def check(now_ok):
  for able in root_list[now_ok]:
    if check_list[able] == 0:
      check_list[able] = 1
      ans_list[able] = now_ok + 1
      this_order_check_next.append(able)

cnt = 0
while 0 in check_list:
  cnt += 1
  for now_ok in this_order_check:
    check(now_ok)
    this_order_check = this_order_check_next
  if cnt >= M:
    break

if 0 not in check_list:
  print('Yes')
  [print(i) for i in ans_list[1:]]
else:
  print('No')

Solution (Python):
from collections import deque
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 = [-1]*n
used = [0]*n
used[0] = 1
que = deque()
que.appendleft(0)
while que:
    v = que.pop()
    
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv] = 1
        que.appendleft(nv)
        if ans[nv] == -1:
            ans[nv] = v
    


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

Solution (Python):
from collections import deque

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

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

def bfs(p):
    ans = [0 for _ in range(n + 1)]
    v = {1}
    q = deque([p])
    while q:
        p = q.popleft()
        c = ab[p] - v
        if len(c) == 0:
            continue
        for pp in c:
            ans[pp] = p
            v.add(pp)
            q.append(pp)
    return ans


ans = bfs(1)
ans = ans[2:]

for an in ans:
    if an == 0:
        print('No')
        exit(0)
print('Yes')
for an in ans:
    print(an)

Solution (Python):
N, M = list(map(int, input().split()))
edge = {i:[] for i in range(1,N+1)}
for _ in range(M):
    A, B = list(map(int, input().split()))
    edge[A].append(B)
    edge[B].append(A)

remain = [1 for _ in range(N)]
remain[0] = 0
ans = [0 for _ in range(N-1)]
before = 1
cand = [(before,edge[before])]
while len(cand)!=0:
    tmp = []
    for one in cand:
        before, can = one
        for on in can:
            tm = []
            if ans[on-2]==0:
                ans[on-2] = before
            remain[on-1] = 0
            for o in edge[on]:
                if remain[o-1]==1:
                    tm.append(o)
                    remain[o-1] = 0
            tmp.append((on, tm))
    cand = tmp
flag = True
for one in ans:
    if one==0:
        flag=False
        break
if not flag:
    print('No')
else:
    print('Yes')
    for one in ans:
        print(one)

Solution (Python):
import sys
import collections
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

DQ=collections.deque([(1,0)])
VS=set([1])
MP={}
N,M=LI()
RES=[0]*(N+1)

for i in range(M):
    ff,tt=LI()
    if not ff in MP: MP[ff] = []
    if not tt in MP: MP[tt] = []
    MP[ff].append(tt)
    MP[tt].append(ff)


while DQ:
    i, dist = DQ.popleft()
    
    if i in MP:
        for j in MP[i]:
            if not j in VS:
                VS.add(j)
                DQ.append((j, dist+1))
                RES[j] = i


if len(VS) < N:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(RES[i])

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

S = [-1 for _ in range(n)]
q = queue.Queue()
for v in A[0]:
    q.put((0,v))
while not q.empty():
    u,v = q.get()
    if S[v] == -1:
        S[v]=u 
        for nex in A[v]:
            if S[nex] == -1: 
                q.put((v,nex))
S[0]= -2
if not -1 in S:
    print('Yes')
    for i in range(1,n):
        print(S[i]+1)
else:
    print('No')

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

import collections
q = collections.deque([])
q.append([1, -1, 0])

while len(q) > 0:
    
    curroom, pv, cost = q.popleft()
    
    
    if used[curroom][0] is True:
        continue
    used[curroom][0] = True
    used[curroom][1] = pv
    for i in range(len(path[curroom])):
        nextroom = path[curroom][i]
        
        
        if used[nextroom][0] is True:
            
            continue
        q.append([nextroom, curroom,cost])




can = True 
for i in range(1, n+1):
    x,y = used[i]
    if x is False:
        can = False

if can is False:
    print("No")
else:
    print("Yes")
    for i in range(2, n+1):
        print(used[i][1])

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

from collections import deque

load = [deque([]) for _ in range(N)]
ans_list = [-1]*N
q = deque([])
flag = [False]*N

for a,b in AB:
  a -= 1
  b -= 1
  load[a].append(b)
  load[b].append(a)
  
q.append(0)
flag[0] = True
while len(q)!=0:
  x = q.popleft()
  y = load[x]
  for i in y:
    if flag[i]:
      continue
    else:
      flag[i] = True
      q.append(i)
      ans_list[i] = x
      
if -1 in ans_list[1:]:
  print('No')
else:
  print('Yes')
  for ans in ans_list[1:]:
    print(ans+1)

Solution (Python):
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


n,m=mp()
step=[-1]*(n+1)
ans=[-1]*(n+1)
edge=[[i] for i in range(n+1)]
for i in range(m):
    a,b=mp()
    edge[a].append(b)
    edge[b].append(a)


que=deque()
que.append(edge[1])
step[1]=0
while len(que):
    q=que.popleft()
    for i in range(1,len(q)):
        if step[q[i]]==-1:
            step[q[i]]=0
            ans[q[i]]=q[0]
            que.append(edge[q[i]])
print("Yes")
for i in range(2,n+1):
    print(ans[i])

Solution (Python):



def dijkstra(costs, s, t, INF=10**10):
    """
    2020/04/11
    https://atcoder.jp/contests/abc079/tasks/abc079_d

    Parameters
    ----------
    costs: list of list of int
    e.g. [[-1,  4,  1, -1],
          [ 4, -1,  5, -1],
          [ 1,  5, -1,  6],
          [-1, -1,  6, -1]]
    """

    costs = [[c if c >= 0 else INF for c in row] for row in costs]
    n_node = len(costs)

    
    
    

    dist_from_s = [INF] * n_node
    dist_from_s[s] = 0
    checked = []  

    while True:
        print(dist_from_s)
        
        nodes = [node for node in range(n_node) if node not in checked]

        
        
        shortest_node, shortest_dist = nodes[0], dist_from_s[nodes[0]]

        for node in nodes:
            if dist_from_s[node] < shortest_dist:
                shortest_node, shortest_dist = node, dist_from_s[node]

        if shortest_node == t:
            return dist_from_s[t]

        checked.append(shortest_node)  

        
        nodes = [node for node in range(n_node) if node not in checked]

        
        for node in nodes:
            dist_from_s[node] = min(
                dist_from_s[shortest_node] + costs[shortest_node][node],
                dist_from_s[node]
            )


def main():
    N, M = map(int, input().split())
    A = [None] * M
    B = [None] * M
    for i in range(M):
        A[i], B[i] = map(int, input().split())
        A[i] -= 1
        B[i] -= 1

    edge_info = {i: [] for i in range(N)}
    for i in range(M):
        edge_info[A[i]].append(B[i])
        edge_info[B[i]].append(A[i])

    
    
    prenodes = [None] * N
    prenodes[0] = 0
    queue = [0]
    queue_size = 1
    queue_idx = 0
    while True:
        
        if queue_idx == queue_size:
            break

        x = queue[queue_idx]
        queue_idx += 1
        nexts = [y for y in edge_info[x] if prenodes[y] is None]
        for node in nexts:
            prenodes[node] = x
            queue.append(node)
            queue_size += 1

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


main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")











N,M = map(int,input().split())
Map = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    Map[a-1].append(b-1)
    Map[b-1].append(a-1)
sign = [0]*N
depth = [-1]*N
depth[0] = 0
q = deque([0])
while len(q) != 0:
    cur = q.popleft()
    for chi in Map[cur]:
        if depth[chi] != -1:
            continue
        depth[chi] = depth[cur]+1
        sign[chi] = cur
        q.append(chi)
print("Yes")
for i in range(1,N):
    print(sign[i]+1)

Solution (Python):
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import heapq
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
d=[float("inf") for _ in range(N)]
d[0]=0
q=[]
prev=[-1]*N
q.append([0,0])
q1=q
flag=1

heapq.heapify(q)

while len(q)>0:
    dist,u=heapq.heappop(q)
    if d[u]<dist: continue
    for i in tree[u]:
        alt=d[u]+1
        if d[i]>alt:
            d[i]=alt
            prev[i]=u
            heapq.heappush(q,[alt,i])
    
for i in range(1,N):
    if prev[i]==-1:
        flag=0
        break
if flag==0:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(prev[i]+1)

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

m=[[] for i in range(N)]

for i in range(M):
  x,y=map(int,input().split(' '))
  m[x-1].append(y-1)
  m[y-1].append(x-1)

sign=[0]
signed_map=[-1]*N
signed_map[0]=1
while True:
  signed=sign
  sign=[]
  for s in signed:
    for room in m[s]:
      if signed_map[room]==-1:
        signed_map[room]=s+1
        sign.append(room)
  if sign==[]:break

print('Yes')
for ch in signed_map[1:]:
  print(ch)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
road = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  road[a].append(b)
  road[b].append(a)
co = set([0])
cn = set([0])
nn = set()
ans = [-1]*n
ans[0] = 0
for _ in range(n):
  if len(cn) == 0:
    break
  for i in cn:
    for j in road[i]:
      if j not in co:
        if j not in cn:
          nn.add(j)
          ans[j] = i
    co.add(i)
  cn = set(nn)
  nn.clear()
if -1 in ans:
  print("No")
else:
  print("Yes")
  for i in ans[1:]:
    print(i+1)

Solution (Python):
import numpy as np
import math
from collections import deque

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

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

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

que = deque()
que.append(0)
ans = [None for i in range(N)]

while(len(que) > 0):
    p = que.popleft()
    
    for to in E[p]:
        if ans[to] is None:
            
            que.append(to)
            ans[to] = p

if None not in ans:
    print("Yes")
    for a in ans[1:]:
        print(a + 1)
else:
    print("No")

Solution (Python):
from collections import deque

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

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


is_visited = [False for _ in range(N)]
ans = [0 for _ in range(N)]
def bfs():
    queue = deque()
    queue.append(0)
    is_visited[0] = True
    while queue:
        pos = queue.popleft()
        for next_pos in A[pos]:
            if is_visited[next_pos] == False:
                is_visited[next_pos] = True
                queue.append(next_pos)
                ans[next_pos] = pos

bfs()

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

Solution (Python):


from collections import deque


N, M = map(int, input().split())
graph_list = {}
for i in range(M):
    a, b = map(int, input().split())
    if a in graph_list:
        graph_list[a].append(b)
    else:
        graph_list[a] = [b]

    if b in graph_list:
        graph_list[b].append(a)
    else:
        graph_list[b] = [a]


visit_list = [0]*N
distance_list = [float("INF")]*N
distance_list[0] = 0
visit_queue = deque([1])
queue_count = 1


while queue_count>0:
    v = visit_queue.popleft()
    queue_count -= 1

    graph = graph_list[v]
    for n in graph:
        if distance_list[v-1]+1<distance_list[n-1]:
            distance_list[n-1] = distance_list[v-1] + 1
            visit_list[n-1] = v
            visit_queue.append(n)
            queue_count += 1


print("Yes")
for i in range(1, N):
    print(visit_list[i])