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.



Sample input:
4 4
1 2
2 3
3 4
4 2


Sample output:
Yes
1
2
2

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
lis = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    lis[a].append(b)
    lis[b].append(a)
queue = deque([1])
dist_list = [-1]*(n+1)
dist_list[1] = 0
while len(queue) != 0:
    now = queue.popleft()
    for v in lis[now]:
        if dist_list[v] == -1:
            dist_list[v] = dist_list[now] + 1
            queue.append(v)
print("Yes")
for i in range(2, n+1):
    for v in lis[i]:
        if dist_list[v] == dist_list[i]-1:
            print(v)
            break

Submission status: Accepted

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

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

kakutei = [1]

answer_li = [0]*n

while kakutei:
    k = kakutei.pop(0)
    for r in root[k-1]:
        if answer_li[r-1] == 0:
            kakutei.append(r)
            answer_li[r-1] = k

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

Submission status: Accepted

Solution code:
import queue

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

for i in range( M ):
  A, B = map( int, input().split() )
  A, B = A - 1, B - 1
  L[ min( A, B ) ].append( max( A, B ))
  L[ max( A, B ) ].append( min( A, B ))
  
R = [ -1 ] * N
Q = queue.Queue()
Q.put( 0 )
while not Q.empty():
  n = Q.get()
  for l in L[ n ]:
    if R[ l ] == -1:
      R[ l ] = n + 1
      Q.put( l )

is_Flag = True 
for i in R:
  if i < 0:
    is_Flag = False
if is_Flag:
  print( "Yes" )
else:
  print("No")

for i in range( 1, N ):
  print( R[ i ] )

Submission status: Accepted

Solution code:
from collections import deque

print("Yes")

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

q = deque([0])
b = [0] * n
while q:
    x = q.popleft()
    for i in g[x]:
        if b[i] != 0:
            continue
        b[i] = x + 1
        q.append(i)

print(*b[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

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

d = {}

for i in range(N):
    d[i+1] = set()

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

que = deque([1])
checked = set()
ans = {1:-1}

while que:
    now = que.popleft()
    for h in d[now]:
        if not h in ans:
            ans[h] = now
            que.append(h)
    if len(ans) == N:
        break
    
if len(ans) == N:
    print('Yes')
    for i in range(N-1):
        print(ans[i+2]) 
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque as d

N, M = map(int, readline().split())
m = map(int, read().split())
AB = zip(m, m)
graph = [[] for _ in range(N + 1)]

for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)

que = d([1])
ans = [0]*(N+1)
while que:
  x = d.popleft(que)
  for i in graph[x]:
    if i == 1 or ans[i] != 0:
        continue
    ans[i] = x
    que.append(i)

if 0 in ans[2:]:
    print('No')
    exit()
print('Yes')
print('\n'.join(map(str, ans[2:])))

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int,input().split()) # nは部屋の数、mは通路の数
path = [[] for _ in range(n)] # 隣接リスト

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

ans=[None]*n
ans[0]=0


queue = deque([1])
while queue:
    v = queue.popleft()
    for i in path[v-1]:
        if ans[i-1] is None:
            ans[i-1] = v
            queue.append(i)

if None in ans:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(ans[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N, M, *AB = map(int, sys.stdin.buffer.read().split())

dict_path = {i+1: [] for i in range(N)}

for i in range(M):
  A,B = AB[2*i:2*i+2]
  dict_path[A].append(B)
  dict_path[B].append(A)

list_bfs = [1]
list_flg = [0 for _ in range(N+1)]
list_flg[1] = 1

while len(list_bfs)>0:
  list_tmp = []
  for i in list_bfs:
    for j in dict_path[i]:
      if list_flg[j]==0:
        list_tmp.append(j)
        list_flg[j] = i
  list_bfs = list_tmp

print('Yes')
for i in list_flg[2:]:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

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

queue = deque([1])
while queue:
    now = queue.popleft()
    for i in S[now]:
        if ans[i] == 0:
            ans[i] = now
            queue.append(i)
            
if 0 in ans[2:]:
    print('No')
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n, m = _ia()
    edge = [[] for _ in range(n)]
    for _ in range(m):
        ai, bi = map(lambda x: x-1, _ia())
        edge[ai].append(bi)
        edge[bi].append(ai)

    now = []
    nxt = [0]
    idx = {0: 0}
    while len(idx) < n:
        now = nxt
        nxt = []
        for ai in now:
            for bi in edge[ai]:
                if idx.get(bi, -1) >= 0:
                    continue
                idx[bi] = ai
                nxt.append(bi)

    print("Yes")
    return "\n".join(map(str, [v+1 for k, v in sorted(idx.items(), key=itemgetter(0)) if k > 0]))


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())
    
    l = [[] for _ in range(n+1)]
    for i, j in zip(*[iter(ab)] * 2):
        l[i].append(j)
        l[j].append(i)

    ll = [0 for _ in range(n+1)]
    vis = [0 for _ in range(n+1)]
    que = deque()
    que.append(1)
    vis[1] = 1
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if vis[i]:
                continue
            vis[i] = 1
            ll[i] = now
            que.append(i)
    if all(vis[1:]):
        print("Yes")
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print("No")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
AB = [[] for _ in range(N+1)]
for i in range(M):
    A_tmp , B_tmp = map(int, input().split())
    AB[A_tmp].append(B_tmp)
    AB[B_tmp].append(A_tmp)

ans = [0]*(N+1)
visited = [False] * (N + 1)

q = deque()
q.append((1, -1))
while len(q) > 0:
    node, past = q.popleft()
    if visited[node]:
      continue
    ans[node] = past
    visited[node] = True
    for t in AB[node]:
        if visited[t]:
            continue
        q.append((t, node))
print("Yes")
for i in range(2, N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())
    r = range(n+1)
    l = [[] for _ in r]
    for i, j in zip(*[iter(ab)] * 2):
        l[i].append(j)
        l[j].append(i)

    ll = [0 for _ in r]
    vis = [False for _ in r]
    que = deque()
    que.append(1)
    vis[1] = True
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if vis[i]:
                continue
            vis[i] = True
            ll[i] = now
            que.append(i)
    if all(vis[1:]):
        print("Yes")
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print("No")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A, B = [], []
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    graph[a].append(b)
    graph[b].append(a)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = set()
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.update(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = set()
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.add(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    r.append(R(i+1, set(graph[i+1])))

l = r.search()
print("Yes")
for room in l:
    print(room)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N, M = MII()
    l = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = MII()
        l[a].append(b)
        l[b].append(a)

    ll = [0 for _ in range(N+1)]
    visited = [False for _ in range(N+1)]

    que = deque()
    que.append(1)
    visited[1] = True
    while que:
        now = que.popleft()
        nx = l[now]
        for i in nx:
            if not visited[i]:
                visited[i] = True
                ll[i] = now
                que.append(i)


    if all(visited[1:]):
        print('Yes')
        s = "\n".join(map(str, ll[2:]))
        print(s)
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

# グラフ生成
for i in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
 
ans = [0]*(n+1)
 
stk = deque([1])
 
# BFS 幅優先探索
while stk:
    v = stk.pop()
    for s in G[v]:
        # 未到達ノードであれば、キューに追加
        if ans[s] == 0:
            ans[s] = v
            stk.appendleft(s)
ans = ans[2:]
 
if 0 in ans:
    print("No")
else:
    print("Yes")
    for i in ans:
        print(i)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
g = [[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
p = [0]*n
from collections import deque
q = deque([0])

while q:
  v = q.popleft()
  for c in g[v]:
    if p[c]<1:p[c]=v+1;q.append(c)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')

Submission status: Accepted

Solution code:
import collections
n,m = [int(x) for x in input().split()]
ab = [[] for _ in range(n)]
for _ in range(m):
    u,v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    ab[u].append(v)
    ab[v].append(u)

D = collections.deque([0])
visited = [False]*n
visited[0] = True
ans = [0] * n

while D:
    v = D.popleft()
    for i in ab[v]:
        if visited[i]:
            continue
        visited[i] = True
        ans[i] = v
        D.append(i)
print("Yes")
for i in ans[1:]:
    print(i+1)

Submission status: Accepted

Solution code:
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())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

q = deque([0])
b = [0] * n
while q:
    x = q.popleft()
    for i in g[x]:
        if b[i] != 0:
            continue
        b[i] = x + 1
        q.append(i)

if 0 in b[1:]:
    print("No")
else:
    print("Yes")
    print(*b[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
def main():
  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)
    e[b].append(a)
  ans=[-1]*n
  dq=deque([0])
  while dq:
    g=dq.popleft()
    for v in e[g]:
      if ans[v]==-1:
        ans[v]=g+1
        dq.append(v)
  ans[0]="Yes"
  print(*ans)
main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
L=[set() for i in range(n)]
for i in range(m):
    a, b =  map(int, input().split())
    L[a-1] |= {b}
    L[b-1] |= {a}
Y = {range(1, n+1)}
Z = [0]*(n-1) 
S = {1}
def f(X):
    global S, Z
    X_next = set()
    for j in X:
        R = L[j-1]-S
        S |= L[j-1]
        X_next |= R
        for k in R:
            Z[k-2] += j
    if X_next == set():
        print("Yes")
        print('\n'.join(map(str, Z)))
    else:
        return  f(X_next)
f({1})

Submission status: Accepted

Solution code:
import collections

if __name__ == '__main__':
    n, m = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(m)]

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

    for i in l:
        ways[i[0]].append(i[1])
        ways[i[1]].append(i[0])

    #print(ways)

    q = collections.deque()

    ans = [-1] * n # 道案内
    ans[0] = 0

    q.append(1)

    while(len(q) != 0):
        item = q.popleft()
        for i in ways[item]:
            if ans[i-1] == -1:
                ans[i-1] = item
                q.append(i)
                #print(ans , i , item)

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

Submission status: Accepted

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

from collections import defaultdict, deque

G = defaultdict(set)


results = [-1]*N
flags   = [False]*N

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

seen    = [False]*N
partner = [0]*N

q = deque([0])
seen[0] = True


while q:
    now = q.popleft()
    for i in G[now]:
        if seen[i]:
            continue
        seen[i] = True
        partner[i] = now
        q.append(i)

if len(seen) != N:
    print('No')
else:
    print('Yes')
    for i in partner[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
edges = [[]*n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
#print(edges)
q = deque()
q.append(0)
ans = [-1]*n
while q:
    x = q.popleft()
    for child in edges[x]:
        if ans[child] == -1:
            ans[child] = x+1
            q.append(child)
        #print("child=", child)
        #print("ans=", ans)
print("Yes")
for i in range(1, n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

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

adj = [[] for i 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)

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
        ans[to] = now
        q.append(to)

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

Submission status: Accepted

Solution code:
from queue import Queue


n, m = list(map(int, input().split()))
g = {i: [] for i in range(1, n + 1)}
for i in range(m):
    ai, bi = list(map(int, input().split()))
    if min(ai, bi) == 1:
        g[1].append(max(ai, bi))
    else:
        g[ai].append(bi)
        g[bi].append(ai)

q = Queue()
q.put(1)
m = {}
while not q.empty():
    x = q.get()
    for t in g[x]:
        if t not in m:
            m[t] = x
            q.put(t)

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

Submission status: Accepted

Solution code:
import sys 
from collections import defaultdict 
 
class Graph: 
 
    def __init__(self): 
        global n
        self.graph = defaultdict(list) 
        self.parent = [None for i in range(0,n+1)]
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
    def BFS(self, s): 
        visited = [False] * (len(self.graph)+1) 
        queue = [] 
        queue.append(s)   
        while queue: 
            s = queue.pop(0) 
            
            # print (s, end = " ") 
            for i in self.graph[s]: 
                
                if visited[i] == False: 
                    self.parent[i]=s
                    queue.append(i) 
                    visited[i]=True
            

[n,m]=[int(i) for i in input().split(' ')]
g = Graph() 
for i in range(0,m):
    [a,b]=[int(i) for i in input().split(' ')]
    g.addEdge(a,b)
    g.addEdge(b,a)
# print(g.graph)
g.BFS(1)
flag=0
for i in range(2,n+1):
    if g.parent[i]==None:
        print('No')
        flag=1
        break

if flag==0:
    print('Yes')
    for i in range(2,n+1):
        print(g.parent[i])
        9

Submission status: Accepted

Solution code:
from collections import deque
q = deque([0])
Dequeue = lambda: q.popleft()
Enqueue = lambda x: q.append(x)

n, m = map(int, input().split())
g = [[] for _ in [0]*n]

for _ in [0]*m:
    a, b = map(int, input().split())
    a -= 1;b -= 1
    g[a] += [b]
    g[b] += [a]

p = [0]*n
while q:
    v = Dequeue()
    for c in g[v]:
        if p[c] < 1:
            p[c] = v+1
            Enqueue(c)
if 0 in p:
    print("No")
else:
    print("Yes")
    for i in p[1:]:
        print(i)

Submission status: Accepted

Solution code:
def main():

    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    import heapq
    h = [(0, 0)]
    heapq.heapify(h)
    d = [10**10]*n
    while h:
        dis, i = heapq.heappop(h)
        if d[i] == 10**10:
            d[i] = dis
            for j in g[i]:
                if d[j] == 10**10:
                    heapq.heappush(h, (dis+1, j))

    print("Yes")
    for i in range(1, n):
        minimum = 10**9
        dire = None
        for j in g[i]:
            if d[j] < minimum:
                minimum = d[j]
                dire = j
        print(dire+1)


main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
rinsetsu_lis = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    rinsetsu_lis[a].append(b)
    rinsetsu_lis[b].append(a)
l= deque([1])
unvisit= [True]*(n+1)
unvisit[1] = False
anslis = [0]*(n+1)
while len(l) != 0:
    now = l.popleft()
    for r in rinsetsu_lis[now]:
        if unvisit[r]:
            unvisit[r] = False
            l.append(r)
            anslis[r] = now
print("Yes")
for i in range(2,len(anslis)):
    print(anslis[i])

Submission status: Accepted

Solution code:
(r, p)=[int(n) for n in input().split()]
route_list=[[] for i in range(r)]
for i in range(p):
  (x, y)=[int(n)-1 for n in input().split()]
  route_list[x].append(y)
  route_list[y].append(x)

upstair=[0]
ans=[-1]*r
while upstair:
  tmp=[]
  for i in upstair:
    for j in route_list[i]:
      if ans[j] == -1:
        ans[j] = i + 1
        tmp.append(j)
  upstair=tmp

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

N, M = map(int, readline().split())
ans = [0] * (N+1)
graph = [[] for _ in range(N+1)]

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

root = 1
q = [root]
checked = [0] * (N + 1)
checked[root] = 1

while q:
    x = q.pop(0)
    for y in graph[x]:
        if checked[y]:
            continue
        ans[y] = x
        checked[y] = 1
        q.append(y)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[Tuple[int, int]], n: int) -> List[int]:
    passages = defaultdict(set)
    for a, b in values:
        passages[a].add(b)
        passages[b].add(a)
    if len(passages) < n:
        return []
    to_visit = [(0, 1, 0)]
    visited = set()
    # 0 idx is not used
    signs = [1] * (n + 1)
    while to_visit:
        min_dist, cur, prev = heapq.heappop(to_visit)
        if cur in visited:
            continue
        signs[cur] = prev
        for neighbour in passages[cur]:
            if neighbour in visited:
                continue
            heapq.heappush(to_visit, (min_dist + 1, neighbour, cur))
        visited.add(cur)
    LOG.debug((visited))
    LOG.debug((signs))
    if len(visited) < n:
        return []
    return signs[2:]


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    N, M = map(int, stdin.readline().split())
    if M < N - 1:
        print("No", file=stdout)
        return
    values = []
    for _ in range(M):
        a, b = map(int, stdin.readline().split())
        values.append((a, b))
    result = solve(values, N)
    if not result:
        print("No", file=stdout)
    else:
        print("Yes", file=stdout)
        print("\n".join(map(str, result)), file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    # pylint: disable=super-init-not-called
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Accepted

Solution code:
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)
from heapq import *
pq=[]
heapify(pq)
heappush(pq,(0,0))# dist,node id
vis=[0]*n
inf=float('inf')
dist=[inf]*n
dist[0]=0
par=[-1]*n
while pq:
    cur=heappop(pq)
    u=cur[1]
    if vis[u]==1:continue
    vis[u]=1
    for v in g[u]:
        if vis[v]==1:continue
        dist[v]=min(dist[v],1+dist[u])
        if dist[u]+1==dist[v]:
            par[v]=u
        heappush(pq,(dist[v],v))
flag=True
for i in range(1,n):
    if par[i]==-1:
        print('No')
        exit()
print('Yes')
for i in range(1,n):
    print(1+par[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 7)

# 1 ✕ N
N, M = list(map(int, input().rstrip().split()))

# N ✕ M
A = list(tuple(map(int, input().rstrip().split())) for _ in range(M))

array = [[] for _ in range(N)]
for x, y in A:
    array[x - 1].append(y - 1)
    array[y - 1].append(x - 1)

before = [None] * N
before[0] = -1
q = collections.deque([0])

while len(q):
    node = q.popleft()
    for nxt in array[node]:
        if before[nxt] is not None:
            continue
        q.append(nxt)
        before[nxt] = node

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

# # print(array)
# ans = dict((_, 1e9) for _ in range(N))
#
# # visit = [[] for _ in range(N)]
# queue = []
# queue.extend(array[0])
#
# # depth = 0
# while queue:
#     tmp = []
#     q = queue.pop()
#     for x in array[q]:
#         for n in array[x]:
#             if ans[n] != 1e9:
#                 ans[n] = x
#                 tmp.append(ans[n])
#
# if len(tmp) > 0:
#     queue.extend(tmp)
#
# print(ans)

Submission status: Accepted

Solution code:
import queue
N,M = map(int, input().split())
r = [[] for _ in range(N)]
for i in range(M):
    A,B=map(int, input().split())
    r[A-1].append(B)
    r[B-1].append(A)
ans =[0]*(N+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    qg = q.get()
    for ri in r[qg-1]:
        if ans[ri] == 0:
            ans[ri] = qg
            q.put(ri)
print("Yes")
for i in range(2,N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edge_list = [[] for i in range(n)]
prev_list = [1]
ans = [0] * n

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

while len(prev_list) > 0:
    next = []
    for prev in prev_list:
        for edge in edge_list[prev - 1]:
            if ans[edge - 1] == 0:
                next.append(edge)
                ans[edge - 1] = prev
    prev_list = next

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
graph={i:[] for i in range(1,N+1)}
for _ in range(M):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
visited=[False for i in range(N+1)]
par=[-1 for i in range(N+1)]
from collections import deque
d=deque()
visited[1]=True
d.append(1)
e=deque()
while d:
    while d:
        x=d.popleft()
        for node in graph[x]:
            if visited[node]==False:
                par[node]=x
                visited[node]=True
                e.append(node)
    if e:
        d=e
        e=deque()
    else:
        d=deque()
flag=True
for i in range(2,N+1):
    if par[i]<0:
        flag=False
        break
if flag:
    print("Yes")
    for i in range(2,N+1):
        print(par[i])
else:
    print("No")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
r=[[] for x in range(n)]
for c in range(m):
    a,b=map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
s=[-1]*n
u=[0]
v=[]
k=1
while k<n:
    for d in u:
        for e in r[d]:
            if s[e]==-1:
                s[e]=d
                k+=1
                v.append(e)
    u=v
print('Yes')
for c in range(n-1):
    print(s[c+1]+1)