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):

from collections import deque


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


inf = 1001001001
dist = [inf for _ in range(n)]
pre = [-1 for _ in range(n)]
dist[0] = 0 
q = deque()
q.append(0)

while q:
    v = q.popleft()
    for u in to[v]:
        if dist[u] == inf:
            dist[u] = dist[v] + 1 
            pre[u] = v 
            q.append(u)

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

Solution (Python):

from collections import deque


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


inf = 1001001001
dist = [inf for _  in range(n)]
pre = [-1 for _ in range(n)]
dist[0] = 0 
q = deque()
q.append(0)

while q:
    v = q.popleft()
    for u in to[v]:
        if dist[u] != inf:
            continue
        dist[u] = dist[v]+1
        pre[u] = v 
        q.append(u)


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

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

graph = [[] for _ in range(n)]
for i in range(m):
    graph[a[i] - 1].append(b[i] - 1)
    graph[b[i] - 1].append(a[i] - 1)

pathway = [None for _ in range(n)]
queue = [0]
depth = [-1]*n
depth[0] = 0
pre = [-1]*n

while queue:
    now = queue.pop(0)
    for i in graph[now]:
        if depth[i] == -1:
            if pre[i] == -1:
                pre[i] = now
            depth[i] = depth[now] + 1
            queue.append(i)

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

Solution (Python):
n,m=map(int,input().split())
g=[[] for _ in range(n)]

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d=[-1]*n
    pre=[-1]*n
    d[u]=0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is -1:
                if pre[i] == -1:
                    pre[i]=v
                d[i]=d[v]+1
                queue.append(i)
    return d,pre
d,pre=bfs(0)
print('Yes')

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

Solution (Python):
from collections import deque


def 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)
    ans = [-1] * N
    q = deque([(0, 0)])
    while len(q):
        cur, prev = q.popleft()
        if ans[cur] != -1:
            continue
        ans[cur] = prev
        for nxt in adj[cur]:
            if ans[nxt] == -1:
                q.append((nxt, cur))
    print("Yes")
    for i in range(1, N):
        print(ans[i]+1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
inf = 10**9
sys.setrecursionlimit(inf)


def connect(signs, to_room, from_room):
    signs[to_room][2].add(from_room)
    signs[from_room][2].add(to_room)
    return signs


def update(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. 1から始める
    """
    
    
    
    
    signs[from_room][0] = signs[to_room][0] + 1
    signs[from_room][1] = to_room
    
    for from_from_room in signs[from_room][2]:
        if signs[from_room][0] < signs[from_from_room][0] - 1:
            signs = update(signs, from_room, from_from_room)
    
    
    
    
    for from_to_room in signs[from_room][2]:
        if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
            signs = update(signs, from_room, from_to_room)
        
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

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

    dist = [inf] * n
    pre = [None] * n
    queue = [0]
    while queue:
        v = queue.pop(0)
        for u in to[v]:
            if dist[u] != inf:
                continue
            dist[u] = dist[v] + 1
            pre[u] = v
            queue.append(u)

    pre = [i + 1 for i in pre]
    ans = '\n'.join([str(i) for i in ['Yes'] + pre[1:]])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

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

for a, b in AB:
  a, b = a-1, b-1
  es[a].append(b)
  es[b].append(a)

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

INF = float('inf')
dist = [INF] * N
dist[0] = 0
back = [-1] * N

while q:
  v = q.popleft()
  for to in es[v]:
    
    if dist[v] + 1 >= dist[to]: continue
    dist[to] = dist[v]
    back[to] = v+1
    q.append(to)

print("Yes")
print(*back[1:], sep='\n')

Solution (Python):
import collections
from collections import deque

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

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

michi = [None for i in range(n)]
q = deque([0])
while q:
    pop = q.popleft()
    for i in li[pop]:
        if michi[i] is None:
            michi[i] = pop
            q.append(i)
print("Yes")
for i in range(1,len(michi)):
    print(michi[i]+1)

Solution (Python):
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq

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



l = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)

ans = [None for i in range(n)]
q = deque([0])
while q:
    u = q.popleft()
    for i in l[u]:
        if ans[i] is None:
            ans[i] = u
            q.append(i)

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

Solution (Python):
from collections import deque
def bfn():
    q=deque([0])
    visit[0]=True
    while q:
        room_proper=q.popleft()
        for i in graph[room_proper]:
            if visit[i]==False:
                visit[i]=True
                shirube[i]=room_proper
                q.append(i)



if __name__ == "__main__":

    n,m=map(int,input().split())
    shirube=[0]*n
    b=[]
    visit=[False]*n
    graph=[[]*n for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        graph[a].append(b)
        graph[b].append(a)
    bfn()

    if all(visit)==True:
        print("Yes")
        for i in range(1,n):
            print(shirube[i]+1)
    else:
        print("No")

Solution (Python):
from collections import deque

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

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

def bfs(maze,start):
    queue=deque([start])
    d=[float("inf")]*N
    d[start]=0
    while queue:
        x=queue.popleft()
        for y in graph[x]:
            if d[y]==float("inf"):
                d[y]=d[x]+1
                queue.append(y)
    return d

d=bfs(graph,0)
ans=[0]*N
for i in range(1,N):
    flag=0
    for vertex in graph[i]:
        if d[vertex]==d[i]-1:
            ans[i]=vertex+1
            flag=1
            break
    if flag==0:
        print("No")
        exit()
print("Yes")
print(*ans[1:])

Solution (Python):
from collections import deque


N, M = map(int, input().rstrip().split())
G = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().rstrip().split())
    G[A].append(B)
    G[B].append(A)


sign = [-1]*(N+1)
sign[0] = None
sign[1] = 0

queue = deque([1])

while queue:
    node = queue.popleft()
    for next in G[node]:
        if sign[next] > -1:
            continue
        sign[next] = node
        queue.append(next)

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

Solution (Python):
import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
pre = nx.predecessor(G, 1)

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[None]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is None):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    print(i)

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    route = [[] for _ in range(n+1)]
    ans = [None]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        route[a].append(b)
        route[b].append(a)
    q = deque([1])
    while q:
        parent = q.pop()
        children = route[parent]
        for child in children:
            if ans[child] is None:
                ans[child] = parent
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    to = [[] for _ in range(n+1)]
    ans = [None]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        to[a].append(b)
        to[b].append(a)
    queue = deque([1])
    while queue:
        parent = queue.pop()
        children = to[parent]
        for child in children:
            if ans[child] is None:
                ans[child] = parent
                queue.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))

if __name__ == "__main__":
    main()

Solution (Python):



def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    n, m = map(int, input().split())
    p = [[] for _ in range(n)]
    d = deque()
    d.append(0)
    is_used = [False for _ in range(n)]
    is_used[0] = True
    ans = [0 for _ in range(n)]

    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1

        p[ai].append(bi)
        p[bi].append(ai)

    while d:
        di = d.popleft()

        for e in p[di]:
            if is_used[e]:
                continue

            is_used[e] = True
            ans[e] = di + 1

            d.append(e)

    print('Yes')
    print('\n'.join(map(str, ans[1:])))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque 
def main():
    n, m = map(int, readline().split())
    to = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, readline().split()) 
        a-=1
        b-=1
        to[a].append(b)
        to[b].append(a)

    dq = deque()    
    dq.append(0)
    done = [-1 for _ in range(n)]
    done[0] = 1 
    while len(dq)>0:
        v = dq.popleft()
        for nx in to[v]:
            if done[nx] != -1:
                continue
            done[nx] = v
            dq.append(nx)

    print('Yes')
    for i in done[1:]:
        print(i+1)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n,m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
def bfs(graph, N):
    que = deque([0])
    dist = [-1]*N
    dist[0]=0
    while que:
        i = que.popleft()
        for j in graph[i]:
            if dist[j] < 0:
                que.append(j)
                dist[j]=i+1
    return dist

dist = bfs(graph, n)[1:]

if all([x>=0 for x in dist]):
    print("Yes")
    for i in dist:
        print(i)
else:
    print("No")

Solution (Python):
import sys
import queue
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
adj = [[]for i in range(n+1)]
parent = [-1] * (n+1)
for line in sys.stdin:
    a,b = map(int, line.rstrip("\n").split())
    adj[a].append(b)
    adj[b].append(a)
q = queue.Queue()
q.put((1,0))
while(not q.empty()):
    x, p = q.get()
    if parent[x] != -1: 
        continue
    parent[x] = p
    for next in adj[x]:
        if parent[next] == -1: 
            q.put((next,x))
print ('Yes') 
for p in parent[2:]: 
    print(p)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
q = deque()
t = {i: set() for i in range(1, n + 1)}
v = [-1] * n

for _ in range(m):
    a, b = map(int, input().split())
    t[a].add(b)
    t[b].add(a)
q.append(1)
v[0] = 1
while q:
    next = q.popleft()
    for i in t[next]:
        if v[i - 1] == -1:
            q.append(i)
            v[i - 1] = next
print('Yes')
print(*v[1:], sep='\n')

Solution (Python):
from collections import deque
N,M=map(int,input().split())
numbers=[[] for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    numbers[A-1].append(B-1)
    numbers[B-1].append(A-1)
visited=[-1 for _ in range(N)]
visited[0]=1
stack=deque([0])
inf=pow(10,9)
distances=[inf for _ in range(N)]
distances[0]=0
visited=[0 for _ in range(N)]
while len(stack) > 0:
    x=stack.pop()
    for a in numbers[x]:
        if distances[a]>distances[x]+1:
            visited[a]=x+1
            distances[a]=distances[x]+1
            stack.appendleft(a)
distances[0]=0
print('Yes')
for a in range(1,N):
    print(visited[a])

Solution (Python):

from collections import deque


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


room = [0]*n


route = [[] for motsu in range(n)]
for ab in ab_list:
  a = ab[0]
  b = ab[1]
  route[a-1].append(b)
  route[b-1].append(a)

d = deque()
d.append(1)
while len(d) > 0:
  s = d.popleft()
  s_list = route[s-1]
  for h in s_list:
    if room[h-1] != 0:
      continue
    room[h-1] = s
    d.append(h)
ans = room[1:]
if 0 in ans:
  print('No')
else:
  print('Yes')
  for w in ans:
    print(w)

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

for _ in range(M):
    u, k=[int(x) for x in input().split()] 
    graph[u-1].append(k-1)
    graph[k-1].append(u-1) 


sign = [0]*(N-1)
dist=[N]*N
dist[0]=0

q=deque()
q.append(0)
while q:
    v=q.popleft()
    for x in graph[v]:
        if dist[x] > dist[v]+1:
            dist[x]=dist[v]+1
            sign[x-1]=v+1
            q.append(x)

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

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










stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def bfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited

def main():
    
    n,m = map(int, stdin.readline().rstrip().split())
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b = map(int, stdin.readline().rstrip().split())
        a-=1;b-=1 
        graph[a].append(b)
        graph[b].append(a)
    visited = bfs(graph, n, 0)
    print("Yes")
    for i in range(1,n):
        print(visited[i])

main()

Solution (Python):
N, M = list(map(int, input().split()))
g = [[] for _ in range(N + 1)]  
for m in range(M):
    a, b = list(map(int, input().split()))
    if a <= N and b <= N:
        g[a].append(b)
        g[b].append(a)

queue = [1]
d = [None] * (N + 1)
d[0] = 0
d[1] = 0
while queue:
    v = queue.pop(0)
    for i in g[v]:
        
        if d[i] is None:
            d[i] = v
            queue.append(i)
        
for i in range(N + 1):
    if d[i] is None:
        print('No')
        exit()
print('Yes')
for i in range(2, N + 1):
    print(d[i])

Solution (Python):
N, M = list(map(int, input().split()))
g = [[] for _ in range(N + 1)]  
for m in range(M):
    a, b = list(map(int, input().split()))
    if a <= N and b <= N:
        g[a].append(b)
        g[b].append(a)

queue = [1]
d = [None] * (N + 1)
d[0] = 0

while queue:
    v = queue.pop(0)
    for i in g[v]:
        
        if d[i] is None:
            d[i] = v
            queue.append(i)
        
for i in range(N + 1):
    if d[i] is None:
        print('No')
        exit()
print('Yes')
for i in range(2, N + 1):
    print(d[i])

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

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

ans = [-1] * N
q = [0]
while len(q) > 0:
    nq = []
    for t in q:
        for e in bridges[t]:
            if ans[e] < 0:
                nq.append(e)
                ans[e] = t
    q = nq

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

Solution (Python):
from collections import deque
n, m = list(map(int, input().split()))
connects = [[] * n for _ in range(n)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    connects[i - 1].append(j - 1)
    connects[j - 1].append(i - 1)
stack = deque([0, ])
visited = [-1] * n
while stack:
    x = stack.popleft()
    for dx in connects[x]:
        if visited[dx] == -1:
            visited[dx] = x + 1
            stack.append(dx)
        else:
            continue
print('Yes')
[print(i) for i in visited[1:]]

Solution (Python):
import queue


def bfs(index, before):
    if direct[index] != -1:
        return
    print(index, before)
    direct[index] = before
    for next in graph[index]:
        bfs(index=next, before=index)


def main():
    n, m = map(int, input().split())
    graph = [[]for i in range(n+2)]
    direct = [-1 for i in range(n+2)]
    q = queue.Queue()

    for i in range(m):
        
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    q.put([1, 1])
    while q.qsize() != 0:
        index, before = q.get()
        if direct[index] == -1:
            direct[index] = before
            for next in graph[index]:
                q.put([next, index])
    print("Yes")
    for i in range(2, n+1):
        print(direct[i])

    return


if __name__ == "__main__":
    main()

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

ans = [-1]*N
T = [0]
while len(T)>0:
  P = T
  T = []
  for x in P:
    for e in E[x]:
      if ans[e]==-1:
        T += [e]
        ans[e] = x

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

Solution (Python):
(n, m), *e = [[*map(int, t.split())] for t in open(0)]
q = [1]
ans = [0] * -~n
node = [[] for _ in range(-~n)]
temp = set()

for i, j in e:
    node[i].append(j)
    node[j].append(i)

while q:
    for x in q:
        for y in node[x]:
            if ans[y] == 0:
                ans[y] = x
                temp.add(y)
    q = list(temp)
    temp.clear()

if 0 in ans[2:]:
    print('No')
else:
    print('Yes', *ans[2:])

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

N,M = map(int,input().split())
concat = [ [] for i in range(N)]
que = deque([1])
check = [-1 for i in range(N)]
check[0] = 0 

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


def bfs():
    if len(que)==0:
        return
    out = que.popleft()
    for i in concat[out-1]:
        if check[i-1]==-1:
            check[i-1]=out
            que.append(i)
    bfs()

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

Solution (Python):

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

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

ll=[[]for i in range(n)]

for i in range(m):
    ll[l[i][0]-1].append(l[i][1])
    ll[l[i][1]-1].append(l[i][0])

lt=[0 for i in range(n)]
lll=[1]
for i in range(n):
    for j in ll[lll[i]-1]:
        if (j!=1 and lt[j-1]==0):
            lll.append(j)
            lt[j-1]=lll[i]

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

Solution (Python):
from collections import deque

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

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

dist = [0] * (n + 1)

d=deque()
d.append(1)

while d:
    v = d.popleft()
    
    for i in graph[v]:
        if not dist[i]:
            dist[i] = v
            d.append(i)

ans = dist[2:]
print('Yes')
print(*ans,sep='\n')

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):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *





































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,M = inputMap()

	ki = [[] for i in range(N)]
	for i in range(M):
		A,B = inputMap()
		ki[A-1].append(B-1)
		ki[B-1].append(A-1)

	ans = [-1 for i in range(N)]
	sign = [0]
	while True:
		signed = sign
		sign = []
		for i in signed:
			for room in ki[i]:
				if ans[room] == -1:
					ans[room] = i+1
					sign.append(room)
		if len(sign) == 0:
			break

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





def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)



if __name__ == "__main__":
	main()

Solution (Python):
from queue import Queue

n, m = map(int, input().split())
ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]
L = [-1]*n
neighbor =[[] for i in range(n)]
for i in range(m):
  neighbor[a[i]-1].append(b[i])
  neighbor[b[i]-1].append(a[i])
  
q = Queue()

q.put([1])
L[0] = 0

while not q.empty():
  pos = q.get()
  valid_pos =[]
  for p in pos:
    for m in neighbor[p-1]:
      if L[m-1] == -1:
        L[m-1] = p
        valid_pos.append(m)
  if len(valid_pos) != 0:
    q.put(valid_pos)

print('Yes')    
for i in range(n-1):
  print(L[i+1])

Solution (Python):


import collections


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.edges = []
    self.sign = None


def main():
  N, M = map(int, input().split())
  nodes = [Node(i + 1) for i in range(N)]

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

  nodes[0].sign = 0
  count = 1

  queue = collections.deque()
  queue.append(nodes[0])

  while len(queue) != 0:
    n = queue.popleft()

    for e in n.edges:
      if e.sign is None:
        e.sign = n.idx
        count += 1
        queue.append(e)

  if count == len(nodes):
    print('Yes')
    for n in nodes[1:]:
      print(n.sign)
  else:
    print('No')


if __name__ == '__main__':
  main()

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

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

graph=[[] for i in range(n)]

roomSign=[-1]*n

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

D=deque([0])

while D:
    v=D.popleft()
    for i in graph[v]:
        if roomSign[i] == -1:
          roomSign[i]=v
          D.append(i)

print("Yes")

for i in range(1,n):
    print(roomSign[i]+1)

Solution (Python):

from collections import deque

def parse():
  N, M = map(int, input().split(" "))

  rooms = [[] for n in range(N)]
  for m in range(M):
    a, b = map(int, input().split(" "))
    rooms[a - 1].append(b - 1)
    rooms[b - 1].append(a - 1)
  
  return N, M, rooms

def main():
  N, M, rooms = parse()
  

  
  q = deque([])
  q.append(0)

  
  guides = [None for n in range(N)]
  guides[0] = 0
  while len(q) > 0:
    room_num = q.popleft()
    

    
    for next_room_num in rooms[room_num]:
      
      if guides[next_room_num] == None:
        q.append(next_room_num)
        
      
        guides[next_room_num] = room_num
        

      
    
    
    
  
  for guide in guides[1:]:
    if guide == None:
      print("No")
      exit(0)
  print("Yes")
  for guide in guides[1:]:
    print(guide + 1)

if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque

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

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


res=[-1]*n
que=deque()
que.append(0)

while len(que)>0:
    i=que.popleft();
    for j in graph[i]:
        if res[j]==-1:
            res[j]=i
            que.append(j)
    

print("Yes")
for l in res[1:]:
    print(l+1)

Solution (Python):
from collections import deque

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

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


res=[-1]*n
que=deque()
que.append(0)

while len(que)>0:
    i=que.popleft();
    for j in graph[i]:
        if res[j]==-1:
            res[j]=i
            que.append(j)
    

print("Yes")
for l in res[1:]:
    print(l+1)

Solution (Python):
from collections import deque
n, m = map(int,input().split())
def vertex_node()  -> list:
    v_c = [[] for _ in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        v_c[a].append(b)
        v_c[b].append(a)
    return v_c

def bfs(l) -> list:
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 0
    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        for i in l[v]:
                if dist[i] != -1:
                    continue
                dist[i] = v
                d.append(i)
    return dist
if __name__ == "__main__":
    i = vertex_node()
    ans = bfs(i)[2:]
    print("Yes")
    for i in ans:
        print(i)