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
from collections import deque


def main():
    n, m = map(int, sys.stdin.readline().split())

    to = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        to[a].append(b)
        to[b].append(a)
    INF = float("inf")

    dist = [INF] * (n + 1)
    dist[1] = 0
    pre = [0] * (n + 1)
    que = deque([])
    que.append(1)

    while que:
        p = que.popleft()
        for i in to[p]:
            if dist[i] > dist[p] + 1:
                dist[i] = dist[p] + 1
                pre[i] = p
                que.append(i)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque


def main():
    n, m = map(int, sys.stdin.readline().split())

    to = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        to[a].append(b)
        to[b].append(a)
    INF = float("inf")

    dist = [INF] * (n + 1)
    dist[1] = 0
    pre = [0] * (n + 1)
    que = deque([])
    que.append(1)

    while que:
        p = que.popleft()
        for i in to[p]:
            if dist[i] == INF:
                dist[i] = dist[p] + 1
                pre[i] = p
                que.append(i)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque


def main():
    n, m = map(int, sys.stdin.readline().split())

    to = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        to[a].append(b)
        to[b].append(a)
    INF = float("inf")

    dist = [INF] * (n + 1)
    dist[1] = 0
    pre = [0] * (n + 1)
    que = deque([])
    que.append(1)

    while que:
        p = que.popleft()
        for i in to[p]:
            if dist[i] == INF:
                dist[i] = dist[p] + 1
                pre[i] = p
                que.append(i)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque


def main():
    n, m = map(int, sys.stdin.readline().split())

    to = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        to[a].append(b)
        to[b].append(a)
    INF = float("inf")

    dist = [INF] * (n + 1)
    dist[1] = 0
    pre = [0] * (n + 1)
    que = deque([])
    que.append(1)

    while que:
        p = que.popleft()
        for i in to[p]:
            if dist[i] > dist[p] + 1:
                dist[i] = dist[p] + 1
                pre[i] = p
                que.append(i)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

to = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    to[a].append(b)
    to[b].append(a)
INF = float("inf")

dist = [INF] * (n + 1)
dist[1] = 0
pre = [0] * (n + 1)
que = deque([])
que.append(1)

while que:
    p = que.popleft()
    for i in to[p]:
        if dist[i] > dist[p] + 1:
            dist[i] = dist[p] + 1
            pre[i] = p
            que.append(i)

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
path=[[] for _ in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  path[b].append(a)
  path[a].append(b)
q=deque()
q.append(1)
l=[-1]*(n+1)
while q:
  v=q.popleft()
  for i in path[v]:
    if l[i]==-1:
      l[i]=v
      q.append(i)
print('Yes')
for i in l[2:]:
  print(i)

Solution (Python):
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([a, b])
    g[b].append([b, a])
res = [-1 for _ in range(n+1)]
res[1] = 0
q = deque(g[1])
while q:
    q_ = q.popleft()
    if res[q_[1]] == -1:
        for gi in g[q_[1]]: q.append(gi)
        res[q_[1]] = q_[0]
print("Yes")
for i in res[2:]: print(i)

Solution (Python):
from collections import deque
INF = 10**9 + 7
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([a, b])
    g[b].append([b, a])
res = [INF for _ in range(n+1)]
res[1] = 0
q = deque(g[1])
while q:
    q_ = q.popleft()
    if res[q_[1]] == INF:
        for gi in g[q_[1]]: q.append(gi)
        res[q_[1]] = q_[0]
print("Yes")
for i in res[2:]: print(i)

Solution (Python):
n,m=map(int,input().split())
l=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  l[a-1].append(b)
  l[b-1].append(a)
ans=[-1]*n
ans[0]=0
x=[1]
y=[]
count=1
while x!=[]:
  for i in x:
    for j in l[i-1]:
      if ans[j-1]==-1:
        ans[j-1]=i
        y.append(j)
        count+=1
  x=y
  y=[]
print('Yes')
for i in range(1,n):
    print(ans[i])

Solution (Python):
from collections import deque
INF = 10**9 + 7
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([a, b])
    g[b].append([b, a])
res = [[0, INF] for _ in range(n+1)]
res[1][1] = 0
q = deque(g[1])
while q:
    q_ = q.popleft()
    if res[q_[1]][1] == INF:
        for gi in g[q_[1]]: q.append(gi)
        res[q_[1]][0] = q_[0]
        res[q_[1]][1] = res[q_[0]][1] + 1
print("Yes")
for i in res[2:]: print(i[0])

Solution (Python):
from collections import deque
n, m = map(int, input().split())
to = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)
q = deque()
visited = [0 for _ in range(n)]
pre = [-1 for _ in range(n)]
q.append(0)
visited[0] = 1
while q:
    
    v = q.popleft()
    for u in to[v]:
        if visited[u] == 1: continue
        visited[u] = 1
        pre[u] = v
        q.append(u)
print("Yes")
for p in pre[1:]:
    p += 1
    print(p)

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(lambda x: int(x)-1, input().split())

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

q = deque()
q.append(0)
dist = [-1 for _ in range(n)]
dist[0] = 0
to = {}

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

    for nv in g[v]:
        if(dist[nv] != -1): continue
        
        dist[nv] = dist[v] + 1
        to[nv] = v
        q.append(nv)

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

Solution (Python):
from collections import deque

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

ans = [0] * (n - 1) 
seen = deque([1])
not_seen = [True] * n
not_seen[0] = False
cnt = n - 1

while cnt > 0:
    pre = seen.popleft()
    for now in path[pre]:
        if not_seen[now - 1]:
            seen.append(now)
            ans[now - 2] = pre
            not_seen[now - 1] = False
            cnt -= 1

print("Yes")
for i in ans:
    print(i)

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

visited = [False]*N
q = deque([0])
visited[0] = True
ans = defaultdict(int)
while len(q):
    v = q.popleft()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        ans[e] = v
        q.append(e)
print("Yes")
for i in range(1, N):
    print(ans[i]+1)

Solution (Python):
from collections import deque

n,m=map(int,input().split())
L=[[] for i 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)
D=[float('inf') for i in range(n)]

def bfs():
	que=deque([])
	que.append(0)
	D[0]=0
	while que:
		p=que.popleft()
		for np in L[p]:
			if D[np]==float('inf'):
				que.append(np)
				D[np]=p+1

bfs()

if sum(D)==float('inf'):
	print('No')
else:
	print('Yes')
	for i in range(1,n):
		print(D[i])

Solution (Python):
import collections

def main():
    n, m = map(int, input().split())
    g = [[] for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        g[a].append(b)
        g[b].append(a)
    ans = solve(n, m, g)
    if -1 in ans:
        print('No')
    else:
        print('Yes')
        print(*ans, sep = '\n')


def solve(n, m, g):
    q = collections.deque()
    distances = [-1 for i in range(n)]
    ans  = [-1 for i in range(n)]
    distances[0] = 0
    q.append(0)
    while len(q):
        pos = q.popleft()
        for i in g[pos]:
            if distances[i] == -1:
                q.append(i)
                distances[i] = distances[pos] + 1
                ans[i] = pos + 1
    return ans[1:]


if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
box=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    box[a-1].append(b-1)
    box[b-1].append(a-1)
ans=[None]*(N)
ans[0]=0
que=[0]
while len(que)>0:
    index=que.pop(0)
    for x in box[index]:
        if ans[x]==None:
            ans[x]=index+1
            que.append(x)
print("Yes")
for i in range(1,N):
    print(ans[i])

Solution (Python):
from collections import defaultdict
import queue

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

guide = {}
room = defaultdict(list)

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


q = queue.Queue()

for i in room[1]:
    q.put(i)
    guide[i] = 1

while not(q.empty()):
    x = q.get()
    for i in room[x]:
        if i not in guide:
            guide[i]=x
            q.put(i)



if len(guide) != N:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(guide[i])

Solution (Python):
import queue

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

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

q = queue.Queue()
q.put((1, 0))
while(not q.empty()):
    x, p = q.get()
    if parents[x] != -1:
        continue
    parents[x] = p
    for connection in rooms[x]:
        if parents[connection] == -1:
            q.put((connection, x))
print('Yes')
for p in parents[2:]:
    print(p)

Solution (Python):

from queue import Queue
N,M=map(int,input().split())

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

Pas=[0 for i in range(N+1)]
Flag=[True for i in range(N+1)]
Flag[0:2]=[False,False]
st=Queue()
st.put(1)
while not st.empty():
    s=st.get()
    for i in X[s]:
        if Flag[i]:
            Pas[i]=s
            Flag[i]=False
            st.put(i)

result="Yes"
for i in range(2,N+1):
    if Flag[i]:
        result="No"

if result=="Yes":
    print(result)
    for i in range(2,N+1):
        print(Pas[i])
else:
    print(result)

Solution (Python):
from collections import defaultdict

N, M = [int(el) for el in input().split()]
paths = defaultdict(lambda: set())

for _ in range(M):
    S, D = [int(el) for el in input().split()]
    paths[S].add(D)
    paths[D].add(S)

post = [0 for _ in range(N + 1)]
post[0] = post[1] = 1
queue = [1, ]
while queue:
    s = queue.pop(0)
    for d in paths[s]:
        if post[d] == 0:
            post[d] = s
            queue.append(d)

if post.count(0) != 0:
    print("No")
else:
    print("Yes")
    for item in post[2:]:
        print(item)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from collections import deque

def main():
    n, m = list(map(int, input().strip().split()))
    G = [[] for i in range(n)]
    for i in range(m):
        a, b = list(map(int, input().strip().split()))
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = deque()
    q.append((0, -1))
    visited = [False] * (n)
    shirube = [-1] * n
    visited[0] = True
    while len(q) != 0:
        src, prev = q.popleft()
        
        shirube[src] = prev
        for node in G[src]:
            if not visited[node]:
                visited[node] = True
                q.append((node, src))
    
    print('Yes')
    for i in range(1, n):
        print(shirube[i]+1)


if __name__ == '__main__':
    main()

Solution (Python):
import queue
q=queue.Queue()
n,m=map(int,input().split())
room=[]
singpost=[0]*(n+1)

for i in range(n+1):
    room.append([])

for _ in range(m):
    r1,r2=map(int,input().split())
    if r1==1 :
        singpost[r2]=1
        q.put(r2)
    elif r2==1:
        singpost[r1]=1
        q.put(r1)
    else:
        room[r1].append(r2)
        room[r2].append(r1)

while not(q.empty()):
    loca=q.get()
    for x in room[loca]:
        if singpost[x]==0:
            singpost[x]=loca
            q.put(x)

if singpost.count(0)>2:print("No")
else:
    print("Yes")
    for x in range(2,n+1):
        print(singpost[x])

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

while len(q):
    now = q.pop(0)
    for i in room[now]:
        if mark[i] == -1:
            mark[i] = now
            q.append(i)

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

Solution (Python):
from collections import deque
import queue
N,M = list(map(int,input().split()))
linked_list ={i:[] for i in range(1,N+1)}
A_list = []
B_list = []
depths = [-1 for _ in range(N)]
depths[0] = 0
for m in range(M):

    A, B = list(map(int,input().split()))
    linked_list[A].append(B)
    linked_list[B].append(A)

    
    
node = []
simbols =[]
q = deque()
q.append(1)
while len(q) >0:
    node_no  = q.popleft()
    for i in linked_list[node_no]:
        if depths[i-1] != -1:
            continue

        q.append(i)
        depths[i-1]=node_no

        
        

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

mod = 998244353
INF = 1 << 29
lINF = 1 << 35


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

Solution (Python):
from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])

Solution (Python):
from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])

Solution (Python):
from collections import deque

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

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

q = deque()
q.append(1)
l = [-1]*(n + 1)
l[1] = 0

while q:
    v = q.popleft()
    for i in paths[v]:
        if l[i] == -1:
            l[i] = v
            q.append(i)

print("Yes")

for i in l[2:]:
    print(i)

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


parent=[0 for i in range(N+1)]
done=[0 for i in range(N+1)]
done[1]=1

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

while q:
    r=q.popleft()
    for t in goto[r]:
        if done[t]:
            continue
        parent[t]=r
        done[t]=1
        q.append(t)



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

Solution (Python):
ma = lambda :map(int,input().split())
n,m = ma()
import collections
que = collections.deque()
ls = [[] for i in range(n)]
for i in range(m):
    a,b = ma()
    ls[a-1].append(b-1)
    ls[b-1].append(a-1)
que.append((0,-1))
vis = [False]*n
ans = [0]*n
while que:
    now,prev = que.popleft()
    if not vis[now]:
        vis[now] = True
        ans [now] = prev
        for nex in ls[now]:
            if not vis[nex]:
                que.append((nex,now))
print("Yes")
for i in range(1,n):
    print(ans[i]+1)

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


def bfs_opt(s):
    signs[s] = 0
    Q.append(s)
    while len(Q) > 0:
        u = Q.popleft()
        for v in rooms[u]:
            if signs[v] == INFTY:
                signs[v] = u
                Q.append(v)


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








Q = deque()

bfs_opt(0)







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

Solution (Python):
from collections import deque

def bfs(adj, sign):
  queue = deque([0])
  sign[0] = 0
  while queue:
    x = queue.popleft()
    for y in adj[x]:
      if sign[y] == -1:
        sign[y] = x
        queue.append(y)

if __name__ == "__main__":
  n, m = map(int, input().split())
  adj = [set() for _ in range(n)]
  for _ in range(m):
    a, b = map(int, input().split())
    adj[a-1].add(b-1)
    adj[b-1].add(a-1)
  sign = [-1]*n
  bfs(adj, sign)
  if all([x != -1 for x in sign]):
    print("Yes")
    for x in sign[1:]:
      print(x+1)
  else:
    print("No")

Solution (Python):
from collections import deque

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

tree=[[0] 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)

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

print("Yes")
for j in range(1,N):
    print(dist[j]+1)

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

from collections import deque
q = deque([1])
visited = [False]*(n+1)
visited[1] = True
signpost = [False]*(n+1)

while q:
    k = q.popleft()
    for j in d[k]:
        if visited[j] != False:
            continue
        visited[j] = True
        signpost[j] = k
        q.append(j)

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

Solution (Python):
from collections import namedtuple, deque

P = namedtuple('P', 'id prev')

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)
  

visited = [None] * (N + 1)
  
q = deque([P(1, None)])
  
while q:
  p = q.popleft()
  if visited[p.id] is not None:
    continue
    
  visited[p.id] = p.prev
  
  for e in G[p.id]:
    if visited[e] is not None:
      continue
    q.append(P(e, p.id))
  
print('Yes')  

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

Solution (Python):
(n,m),*e=[[*map(int,t.split())]for t in open(0)]
t=[[]for _ in range(n+1)]
for a,b in e:t[a]+=[b];t[b]+=[a]
q=[1]
a=[0]*-~n
while q:q=[a[j]==0and(a.__setitem__(j,i)or j)for i in q for j in t[i]]
print('Yes',*a[2:])

Solution (Python):
from collections import deque
N,M=map(int,input().split())
S=[[] for _ in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    S[a].append(b)
    S[b].append(a)
q=deque()
dist=[-1]*N
dist[0]=0
q.append(0)
while q:
    now=q.popleft()
    for j in S[now]:
        if dist[j] != -1:continue 
        dist[j]=now+1
        q.append(j)
print('Yes')
[print(dist[i]) for i in range(1,N)]

Solution (Python):
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_edges_from(s)
di=nx.predecessor(g,source=1)

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

Solution (Python):
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_edges_from(s)

print("Yes")
for x in sorted(nx.bfs_predecessors(g,1)):
    print(x[1])

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


from collections import deque
sys.setrecursionlimit(pow(10, 6))

def set_route(start, goal):
	global routes
	
	routes[goal].append(start)


def search(que):
	global routes
	global guides

	if len(que) > 0:
		goal = que.popleft()

		for start in routes[goal]:
			if guides[start] == 0:
				guides[start] = goal
				que.append(start)
		
		search(que)
	else:
		return 


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


for i in range(1, n + 1):
	routes[i] = []


for i in range(m):
	a, b = map(int, input().split())
	set_route(a, b)
	set_route(b, a)


guides = [0] * (n + 1)

que = deque()
que.append(1)
search(que)

ans = guides[2:]

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

Solution (Python):
from collections import deque

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
par = [0] * (n+1)

for _ in range(m):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

visited = [0] + [1] + [0] * (n-1)
q = deque()
q.append(1)
while q:
    now = q.popleft()
    
    visited[now] = 1
    for next in G[now]:
        
        
        if visited[next]:
            continue
        q.append(next)
        par[next] = now
        visited[next] = 1
print("Yes")
print("\n".join(map(str, par[2:])))

Solution (Python):
N, M = map(int, input().split())
A = []
B = []
pt = [[] for i in range(N)]
for i in range(M):
	a, b =  map(int, input().split())
	a -=1
	b -=1
	pt[a].append(b)
	pt[b].append(a)
n=N
res_list = [-1] * N
def bfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
                    res_list[j]=i
        q=q1
        c+=1
    return d
res = bfs(0)

no = 'No'
yes ='Yes'
if -1 in res:
	print(no)
else:
	print(yes)
	
for i,x in enumerate(res_list):
	if i==0:
		continue
	print(x+1)

Solution (Python):

from collections import deque
import sys

readline = sys.stdin.readline


def main():
    n_rooms, n_passages = map(int, input().split())
    passages = (map(int, readline().strip().split()) for _ in range(n_passages))

    connections = [set() for _ in range(n_rooms+1)]  
    for a, b in passages:
        connections[a].add(b)
        connections[b].add(a)

    que = deque()
    que.append((0, 1))  

    signs = [-1] * (n_rooms + 1)

    while que:
        parent, current = que.popleft()

        if signs[current] != -1:
            continue

        signs[current] = parent

        for room in connections[current]:
            if signs[room] == -1:
                que.append((current, room))

    print('Yes')
    for sign in signs[2:]:
        print(sign)


if __name__ == "__main__":
    main()

Solution (Python):
import queue
import sys

readline = sys.stdin.readline


def main():
    n_rooms, n_passages = map(int, input().split())
    passages = (map(int, readline().strip().split()) for _ in range(n_passages))

    

    connections = [set() for _ in range(n_rooms+1)]  
    for a, b in passages:
        connections[a].add(b)
        connections[b].add(a)

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

    signs = [-1] * (n_rooms + 1)

    while not que.empty():
        parent, current = que.get()

        if signs[current] != -1:
            continue

        signs[current] = parent

        for room in connections[current]:
            if signs[room] == -1:
                que.put((current, room))

    print('Yes')
    print('\n'.join(map(str, signs[2:])))


if __name__ == "__main__":
    main()

Solution (Python):
import queue
import sys

readline = sys.stdin.readline


def main():
    n_rooms, n_passages = map(int, input().split())
    passages = (map(int, readline().strip().split()) for _ in range(n_passages))

    connections = [set() for _ in range(n_rooms+1)]  
    for a, b in passages:
        connections[a].add(b)
        connections[b].add(a)

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

    signs = [-1] * (n_rooms + 1)

    while not que.empty():
        parent, current = que.get()

        if signs[current] != -1:
            continue

        signs[current] = parent

        for room in connections[current]:
            if signs[room] == -1:
                que.put((current, room))

    print('Yes')
    for sign in signs[2:]:
        print(sign)


if __name__ == "__main__":
    main()

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

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

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

from collections import deque
q = deque()

dist = [-1]*n
ans = [0]*n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] += 1
        q.append(to)
        ans[to] = now 
    
print("Yes")
for i in range(1, n):
    print(ans[i] + 1)

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

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

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

from collections import deque
q = deque()

dist = [-1] * n
ans = [0] * n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now 
    
print("Yes")
for i in range(1, n):
    print(ans[i] + 1)

Solution (Python):
n, m = map(int ,input().split())
 
adj = [[] for _ in range(n)]
 
for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    adj[a].append(b)
    adj[b].append(a)
 
from collections import deque
q = deque()
 
dist = [-1] * n
ans = [0] * n
 
q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now
 
print("Yes")
for i in range(1, n):
    print(ans[i] + 1)

Solution (Python):
from collections import deque
def main():
    N, M = map(int, input().split())
    d = [-1 for i in range(N)]
    par = [-1 for i in range(N)]
    adj = [list() for i in range(N)]

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

    dq = deque()
    dq.append(0)
    d[0] = 0

    while(len(dq) > 0):
        n = dq.popleft()
        for i in range(len(adj[n])):
            if d[adj[n][i]] != -1:
                continue
            else:
                dq.append(adj[n][i])
                d[adj[n][i]] = d[n] + 1
                par[adj[n][i]] = n

    print("Yes")
    for i in range(1, len(par)):
        print(par[i]+1)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def main():
    N, M = map(int, input().split())
    d = [-1 for i in range(N)]
    par = [-1 for i in range(N)]
    adj = [list() for i in range(N)]

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

    dq = deque()
    dq.append(0)
    d[0] = 0

    while(len(dq) > 0):
        n = dq.popleft()
        for i in range(len(adj[n])):
            if d[adj[n][i]] != -1:
                continue
            else:
                dq.append(adj[n][i])
                d[adj[n][i]] = d[n] + 1
                par[adj[n][i]] = n

    reachable = True

    for i in range(1, len(par)):
        if par[i] == -1:
            reachable = False

    if reachable :
        print("Yes")
    else:
        print("No")

    for i in range(1, len(par)):
        print(par[i]+1)

if __name__ == "__main__":
    main()

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

node = [float('inf')] * N
node[0] = 0 
route = [0]*N 
rooms = [1] 
st = {1}

for r1 in rooms:
    for r2 in dic[r1]:
        if node[r1-1] + 1 <= node[r2-1]:
            node[r2-1] = node[r1-1] + 1
            route[r2-1] = r1
            if not r2 in st:
                rooms.append(r2)
                st.add(r2)
            try:
                dic[r2].remove(r1)
            except:
                continue

if float('inf') in node:
    print('No')
else:
    print('Yes')
    for i in route[1:]:
        print(i)