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 defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start,N):
        self.g = graph.graph
        self.N = N
        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
    
    def solve(self):
        res = []
        for i in range(1, self.N):
            res.append(self.prev[i]+1)
        return res

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
G = Graph()
for a,b in ab:
    G.add_edge(a-1,b-1)
    G.add_edge(b-1,a-1)
d = Dijkstra(G,0,n)
ans = d.solve()
print("Yes")
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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


que = collections.deque()
que.append(0)
visited = [-1] * n
visited[0] = 0
while que:
  way = que.popleft()
  for gi in G[way]:
    if visited[gi] == -1:
      visited[gi] = way + 1
      que.append(gi)
# print(*visited)
for vi in visited:
  if vi == -1:
    print("No")
    exit()
else:
  print("Yes")
  for i in range(1,n):
    print(visited[i])

Submission status: Accepted

Solution code:
from collections import deque
N , M =[int(hoge) for hoge in input().split()]
route = [[] for i in range(N)]
for i in range(M):
    A,B = [int(hoge)-1 for hoge in input().split()]
    route[A].append(B)
    route[B].append(A)
#全域部分木をほどよく作れるかどうか

#BFS
queue = deque()#append,popleft
went = [-1] * N
went[0] = True
queue.append(0)
while queue:
    cur = queue.popleft()
    for togo in route[cur]:
        if went[togo] == -1:
            went[togo] = cur
            queue.append(togo)

if any([x == -1 for x in went]):
    print("No")
else:
    print("Yes")
    for w in went[1:]:
        print(w+1)

Submission status: Accepted

Solution code:
from heapq import *

def dijkstra(s, edges):
    dist = [INF] * len(edges)
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u in edges[v]:
            if dv+1 < dist[u]:
                dist[u] = dv+1
                heappush(h, (dv+1, u))
    return dist

INF = 10**9
N, M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    es[a].append(b)
    es[b].append(a)
f = [-1]*N
d = dijkstra(0, es)
for v in range(1, N):
    dv = d[v]
    for u in es[v]:
        if d[u] < dv:
            f[v] = u+1
print('Yes')
print(*f[1:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

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

links = [[] for _ in range(N + 1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
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)
visited = [-1]*n
deq = deque([0])
c = 0
visited[0] = 0
while deq:
  cur = deq.popleft()
  c += 1
  for i in l[cur]:
    if visited[i] == -1:
      deq.append(i)
      visited[i] = cur
if c == n:
  print('Yes')
  for i in visited[1:]:
    print(i+1)
else:
  print('No')

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

#print(heya)

queue=deque()
queue.append(0)

mada=[True]*n
mada[0]=False

ans=[-1]*n

for i in range(10*n):
    #print(queue)
    if(len(queue)==0):
        break
    gen=queue.popleft()
    for h in heya[gen]:
        #print(h)
        if(mada[h]):
            mada[h]=False
            queue.append(h)
            ans[h]=gen+1

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

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

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

ans = np.zeros(n, dtype = np.int)
ans[0] = 1
check = 0
queue = deque([0])

while queue:
    pos = queue.popleft()
    check += pos
    for next_pos in root[pos]:
        if ans[next_pos] != 0:
            continue
        ans[next_pos] = pos + 1
        queue.append(next_pos)
if check != n * (n - 1) / 2:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

def bfs(E, s):
    N = len(E)
    order = [-1] * N # a bfs ordering of each vertex
    parent = [-1] * N # parent of each vertex in the bfs search tree
    depth = [-1] * N # the depth of each vertex
    q = deque([(s, -1, 0)]) # (vertex, parent, depth)
    num = 0 # current ordering
    while q:
        v, p, d = q.popleft()
        if order[v] < 0: # visited v for the first time
            order[v] = num; parent[v] = p; depth[v] = d
            num += 1
            for u in E[v]:
                if order[u] >= 0: continue
                q.append((u, v, d+1))
    return order, parent, depth

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1); E[b-1].append(a-1)
_, par, _ = bfs(E, 0)
print('Yes')
for p in par[1:]: print(p + 1)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    from collections import defaultdict, deque
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

    n, m = map(int, input().split())
    roads = defaultdict(deque)
    for _ in range(m):
        a, b = map(int, input().split())
        roads[a].append((b, a))
        roads[b].append((a, b))
    visited = [False]*(n+1)
    visited[1] = True
    ans = [0]*(n+1)
    neighbor = deque(roads[1])
    while neighbor:
        now, base = neighbor.popleft()
        if visited[now]:
            continue
        visited[now] = True
        ans[now] = base
        neighbor.extend(roads[now])
    print('Yes')
    for p_ans in ans[2:]:
        print(p_ans)

Submission status: Accepted

Solution code:
import queue

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

# BFS
q = queue.Queue()
q.put(0)
guide = [-1] * n
guide[0] = 0
while True:
    if q.empty():
        break
    node = q.get()
    next_nodes = paths[node]
    for next_node in next_nodes:
        if guide[next_node] > -1:
            continue
        guide[next_node] = node
        q.put(next_node)

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

Submission status: Accepted

Solution code:
class queue:
    listQ = []
    def push(self, x):
        self.listQ.append(x)
    def pop(self):
        a = self.listQ[0]
        del self.listQ[0]
        return a
    def length(self):
        return len(self.listQ)


n, m = map(int, input().split())
nodeMap = {}
doneL = [0]*(n+1)
doneL[1] = -1
for i in range(m):
    a, b = map(int, input().split())
    if a in nodeMap:
        nodeMap[a].append(b)
    else:
        nodeMap[a] = [b]
    if b in nodeMap:
        nodeMap[b].append(a)
    else:
        nodeMap[b] = [a]

q = queue()
q.push(1)
while q.length():
    poped = q.pop()
    popedL = nodeMap[poped]
    for r in popedL:
        if doneL[r] != 0:
            pass
        else:
            doneL[r] = poped
            q.push(r)
print("Yes")
for r in doneL:
    if r <= 0:
        pass
    else:
        print(r)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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)


parent = [-1] * N
q = deque()
q.append(0)
visited = set()
visited.add(0)

while len(q) != 0:
    cur = q.popleft()
    for n in graph[cur]:
        if n not in visited:
            visited.add(n)
            parent[n] = str(cur + 1)
            q.append(n)

print('Yes')
ans = '\n'.join(parent[1::])
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range (M)]
import sys
sys.setrecursionlimit(10**8)

edge = [[] for _ in range(N)]
for u,v in AB:
    edge[u-1].append([v-1,1])
    edge[v-1].append([u-1,1])


import heapq
def dijkstra(S, N, Edge):
    # S: start vertex
    # N: number of vertices
    # Edge: adjacent list [node, cost]
    
    INF = 10**20
    dist = [INF]*N
    dist[S] = 0
    que = [[0, S]]
    parent = [0]*N
    heapq.heapify(que)
    
    while que:
        c, v = heapq.heappop(que)
        if dist[v] < c: continue

        for nv, nc in Edge[v]:
            if c+nc < dist[nv]:
                dist[nv] = c+nc
                parent[nv] = v
                heapq.heappush(que, [c+nc, nv])
    
    return parent

parent = dijkstra(0, N, edge)
print('Yes')
for i in range(1,N):
    print(parent[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

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

q = deque()

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

while len(q) != 0:
    cur = q.popleft()

    for nx in maze[cur]:
        if not seen[nx] == 1:
            mile[nx] = cur+1
            seen[nx] = 1
            q.append(nx)

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

Submission status: Accepted

Solution code:
from collections import deque, Counter

N, M = map(int, input().split())
Road = [[] for _ in range(N)]
Ans = [-2] * N
Q = deque()
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    Road[A].append(B)
    Road[B].append(A)

now = 0
Ans[0] = -1
Q.append(now)

while len(Q) > 0:
    now = Q.popleft()
    for next in Road[now]:
        if Ans[next] == -2:
            Ans[next] = now
            Q.append(next)

Ans_S = set(Ans)

if -2 in Ans_S:
    print('No')
else:
    print('Yes')
    for i in Ans[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,m=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v=MI1()
        to[u].append(v)
        to[v].append(u)
    hp=[]
    ans=[-1]*n
    heappush(hp,(0,0,0))
    while hp:
        d,u,pu=heappop(hp)
        if ans[u]!=-1:continue
        ans[u]=pu
        for v in to[u]:
            if ans[v]!=-1:continue
            heappush(hp,(d+1,v,u))
    print("Yes")
    for a in ans[1:]:
        print(a+1)

main()

Submission status: Accepted

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

n, m = map(int, input().split())
g = [[] for _ 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)

from collections import deque
q = deque()
visit = [-1]*n
q.append(0)
visit[0] = 0
while q:
    v = q.popleft()
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = visit[v]+1
            q.append(u)

ans = [0]*n
for v in range(1, n):
    for u in g[v]:
        if visit[u] == visit[v]-1:
            ans[v] = u+1
print('Yes')
for i in range(1, n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N, M = map(int, input().split())

Es = dd(dict)
for _ in range(M):
    a, b = map(int, input().split())
    Es[a][b] = Es[b][a] = 1

parents = [None] * (N+1)
parents[1] = 1
q = set([1])
while q:
    nq = set()
    for node in q:
        for to in Es[node]:
            if parents[to] is None:
                parents[to] = node
                nq.add(to)
    q = nq
print('Yes')
for i in range(2, N+1):
    print(parents[i])

Submission status: Accepted

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

dist = [float('inf')]*n
dist[0] = 0

import queue
q = queue.Queue()
q.put([0,0])

while not q.empty():
    cost, nown = q.get()
    for nextn in g[nown]:
        if dist[nextn] != float('inf'):
            continue
        dist[nextn] = nown+1
        q.put([cost + 1,nextn])

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

Submission status: Accepted

Solution code:
import queue
import sys
input = sys.stdin.readline
from collections import defaultdict as dd
sys.setrecursionlimit(1000000)
N,M = map(int,input().split())
ab = [ tuple(map(int,input().split())) for i in range(M)]

edge = dd(list)

for i in range(M):
    tmp1 = ab[i][0]
    tmp2 = ab[i][1]
    edge[tmp1].append(tmp2)
    edge[tmp2].append(tmp1)
q = queue.Queue()
q.put((1,0))
res = [0]*N
mita = set()
mita.add(1)
# BFS
while not q.empty():
    tmp = q.get()
    now = tmp[0]
    depth = tmp[1]
    for elem in edge[now]:
        if elem not in mita:
            mita.add(elem)
            q.put((elem,depth+1))
            res[elem-1] = now
            

if 0 not in res[1:]:
    print('Yes')
    for val in res[1:]:
        print(val)
else:
    print('No')

Submission status: Accepted

Solution code:
# 0や1のケースに注意
# index out of range
# 貪欲

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    res = [-1]*n
    visited = [0]*n
    visited[0] = 1
    d = deque([0])
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if visited[nv] == 0:
                d.append(nv)
                res[nv] = v+1
                visited[nv] = 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, m = LI()
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

check = [True]*n
ans = [None]*n
que = deque()
que.append((0,-1))
while que:
    v, p = que.popleft()
    if not check[v]:
        continue
    check[v] = False
    for u in edges[v]:
        if u == p:
            continue
        que.append((u,v))
        if ans[u] == None:
            ans[u] = v+1

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

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(v) for v in input().split()]

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

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

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


queue = deque([0])

while queue:
    now = queue.pop()
    for n in ad_l[now]:
        if visited[n] != -1: continue
        visited[n] = now + 1
        queue.appendleft(n)

visited = visited[1:]

if -1 in visited:
    print("No")
else:
    print("Yes")
    for v in visited:
        print(v)

Submission status: Accepted

Solution code:
from collections import deque

int1 = lambda x: int(x) - 1

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

# bfs
ans_lst = [None] * N
ans_lst[0] = 0
D = deque([0])
while D:
    v = D.popleft()
    for x in G[v]:
        if ans_lst[x] is None:
            ans_lst[x] = v
            D.append(x)
print('Yes')
for x in ans_lst[1:]:
    print(x + 1)

Submission status: Accepted

Solution code:
import sys
import queue
input = sys.stdin.readline

N,M = map(int,input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    A,B = [int(i)-1 for i in input().split()]
    adj[A].append(B)
    adj[B].append(A)
blis = [True]*N
ans = [0]*N
q = queue.Queue()
cou = 1
q.put(0)
blis[0] = False

while cou != N:
    now = q.get()
    for ad in adj[now]:
        if blis[ad]:
            blis[ad] = False
            ans[ad] = str(now+1)
            cou += 1
            q.put(ad)

print("Yes")
print("\n".join(ans[1:]))

Submission status: Accepted

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

graph = [[] for _ in range(N)]
for i, (Ai, Bi) in enumerate(AB):
    graph[Ai - 1].append(Bi - 1)
    graph[Bi - 1].append(Ai - 1)

import heapq
    
MY_INF = 1000000007
q = [(0, 0)]
d = [MY_INF] * N
d[0] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_tmp = dist + 1
        if d[dst] > dist_tmp:
            d[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

for src in range(N):
    if src == 0:
        print('Yes')
        continue
    #
    dist_min = MY_INF
    ans = 0
    for dst in graph[src]:
        if dist_min > d[dst]:
            dist_min = d[dst]
            ans = dst + 1
    #
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
routes = [set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    A -= 1
    B -= 1
    routes[A].add(B)
    routes[B].add(A)

pool = deque([0])
ans = [-1] * N
ans[0] = 0
while pool:
    n = pool.popleft()
    for c in routes[n]:
        if ans[c] < 0:
            ans[c] = n
            pool.append(c)
print('Yes')
for i in range(1,N):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
A = [set() for x in range(N)]
B = [-1]*N

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

B[0] = 0
D = deque()
D.append(0)
while len(D) != 0:
    d = D.popleft()
    for a in A[d]:
        if B[a] != -1:
            continue
        B[a] = d
        D.append(a)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
connection=[[] for i in range(n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

b=bfs(0)
ans=[0]*n
print('Yes')
for i in range(1,n):
  for j in range(len(connection[i])):
    if b[connection[i][j]]==b[i]-1:
      print(connection[i][j]+1)
      break

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline

N, M = map(int, readline().split())
AB = [list(map(int, readline().split())) for i in range(M)]
AB = [(a-1, b-1) for a,b in AB]

adj = [[] for i in range(N)]
for a,b in AB:
    adj[a].append(b)
    adj[b].append(a)

ans = [-1] * N

q = deque()
q.append(0)

while q:
    n = q.popleft()
    for c in adj[n]:
        if ans[c] == -1:
            ans[c] = n
            q.append(c)

if all(v != -1 for v in ans[1:]):
    print('Yes')
    for c in ans[1:]:
        print(c + 1)
else:
    print('No')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
node=[[]for _ in range(n)]
for _ in range(m):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
from collections import deque
sign=[-1]*n
sign[0]=0
queue=deque([0])
while queue:
	r=queue.popleft()
	for x in node[r]:
		if sign[x]==-1:
			sign[x]=r+1
			queue.append(x)
if -1 in sign:
	print("No")
else:
	print("Yes")
	for i in range(n-1):
		print(sign[i+1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def main():
    N, M = inpl()
    AB = [inpl() for _ in range(M)]

    edges = {}
    for a, b in AB:
        if a not in edges:
            edges[a] = []
        if b not in edges:
            edges[b] = []

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

    Q = deque()
    Q.append(1)
    assigned = set()
    assigned.add(1)
    cost = {}
    cost[1] = 0
    previous_v = {}

    while Q:
        v = Q.popleft()
        for nv in edges[v]:
            if nv not in assigned:
                assigned.add(nv)
                Q.append(nv)

            tmp = cost[v] + 1
            if nv not in cost:
                cost[nv] = tmp
                previous_v[nv] = v
            elif tmp < cost[nv]:
                cost[nv] = tmp
                previous_v[nv] = v

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

    return


if __name__ == '__main__':
    main()