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, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# MOD = 10**9+7
# MOD = 998244353

n, m = map(int, input().split())
E = [list(map(int, input().split())) for i in range(m)]
graph = [[] for _ in range(n)]
for e in E:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

s = [-1]*n
que = deque([0])
while que:
    node = que.popleft()
    for nxt in graph[node]:
        if s[nxt] == -1:
            s[nxt] = node+1
            que.append(nxt)

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

Submission status: Accepted

Solution code:
import collections
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)
q = collections.deque()
q.append(0)
dist = [-1]*N
dist[0] = 0
while len(q) != 0:
    v = q.popleft()
    for w in graph[v]:
        if dist[w] > -1:
            continue
        dist[w] = v + 1
        q.append(w)
print('Yes')
for i in range(1,N):
    print(dist[i])

Submission status: Accepted

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

w=[0 for i in range(n)]
w[0]=1
a=[0]
b=[]
while True:
  for i in a:
    for j in r[i]:
      if w[j]==0:
        w[j]=i+1
        b.append(j)
  if len(b)==0:
    break
  a=b
  b=[]
print("Yes")
for i in range(1,n):
  print(w[i])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
from collections import defaultdict
G = defaultdict(list)
for _ in range(m):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)


# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*n
que = deque([0])
dist[0] = 0
before = [0] * n
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        before[w] = v
        que.append(w)

if -1 in dist:
    print("No")
    exit()
else:
    print("Yes")
    for d in before[1:]:
        print(d+1)

Submission status: Accepted

Solution code:
import sys
import queue
import math

sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    r1, r2 = map(int, input().split())
    edges[r1-1].append(r2-1)
    edges[r2-1].append(r1-1)

sign = [None for _ in range(n)]
q = queue.Queue()
q.put(0)
while True:
    if q.empty():
        break
    rm = q.get()
    for to in edges[rm]:
        if sign[to] is None:
            sign[to] = rm
            q.put(to)
if None in sign[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(sign[i]+1)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[];B=[]
for i in range(M):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
G=[set() for i in range(N)]
for i in range(M):
    G[A[i]-1].add(B[i]-1)
    G[B[i]-1].add(A[i]-1)
ans=[-1 for i in range(N)]
from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
        ans[w]=v
ex=True
for i in range(1,N):
    if ans[i]==-1:
        ex=False
if ex:
    print("Yes")
    for i in range(1,N):
        print(ans[i]+1)
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

que = deque([1])

while len(que) > 0:
    x = que.popleft()
    for r in rooms[x]:
        if ans[r] == 0:
            ans[r] = x
            que.append(r)

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

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = [int(x) for x in input().split()]
    AB = [[int(x) for x in input().split()] for _ in range(M)]

    A = [[] for j in range(N + 1)]
    ans = [0] * (N + 1)

    u = UnionFind(N)

    for a, b in AB:
        A[a].append(b)
        A[b].append(a)
        u.union(a - 1, b - 1)

    if u.group_count() > 1:
        print("No")
        return

    q = collections.deque()
    v = set()

    q.append(1)
    v.add(1)
    while q:
        c = q.popleft()

        for n in A[c]:
            if n not in v:
                v.add(n)
                q.append(n)
                ans[n] = c

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
edge = defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

done = {1}
ans = [None] * (N + 1)
queue = deque()
queue.append(1)
while queue and len(done) < N:
    v1 = queue.popleft()
    for v2 in edge[v1]:
        if v2 not in done:
            done.add(v2)
            ans[v2] = v1
            queue.append(v2)
print('Yes')
for i in range(2, N + 1):
    print(ans[i])

Submission status: Accepted

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

from collections import deque
def bfs():
    heap = deque()
    road = [0]*n

    heap.append((0, -1))
    used = set()
    while heap:
        cur, prev = heap.popleft()
        if cur in used:
            continue
        used.add(cur)
        road[cur] = prev+1
        for to in G[cur]:
            if to not in used and to != prev:
                heap.append((to, cur))
    return road

ans = bfs()
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())
tuuro = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    tuuro[a].append(b)
    tuuro[b].append(a)
ans = [-1 for i in range(n+1)]

print("Yes")

d = deque()
d.append(1)
ans[1] = 0
while d:
    now = d.popleft()
    for i in tuuro[now]:
        if ans[i] == -1:
            ans[i] = now
            d.append(i)

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

Submission status: Accepted

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

ans = [-1 for _ in range(n)]
d = deque()
d.append(0)
while len(d) > 0:
    now = d.popleft()
    for v in to[now]:
        if ans[v] > -1:
            continue
        ans[v] = now
        d.append(v)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N, M = list(map(int, input().split()))
graph = defaultdict(list)

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

ans = [-1] * N
# vertex, prev
queue = deque([(0, 0)])
visited = set([0])
while queue:
    v, prev = queue.popleft()
    ans[v] = prev
    for nv in graph[v]:
        if nv not in visited:
            visited.add(nv)
            queue.append((nv, v))

if -1 in ans:
    print('No')
    exit()
    
for i, v in enumerate(ans):
    if i == 0:
        print('Yes')
    else:
        print(v + 1)

Submission status: Accepted

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

#=== 幅優先探索　開始 ===#
queue = [0] # スタート地点をキューに入れる
ans=[0]*n
visited =[0]*n
visited[0] = 1  # 訪問したかどうかをメモする
while queue:
    x= queue.pop(0)
     # 訪問済みにする
    # 次に訪れる場所　左上右下
    for y in maiz[x]:
        if visited[y]==0 :
            visited[y] = 1
            # 進行可能でまだ訪問していなければキューに入れてかかった手数を記録する
            queue.append(y)
            ans[y]=x
if min(visited)==0:
    print("No")
    exit()
else:
    print("Yes")
for i in range(1,n):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
import os
import heapq

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

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

dist = [(INF, None)] * N
dist[0] = 0, None
heap = [(0, 0, None)]
while heap:
    d, v, p = heapq.heappop(heap)
    if dist[v][0] > d:
        continue
    for u in graph[v]:
        if d + 1 >= dist[u][0]:
            continue
        dist[u] = d + 1, v
        heapq.heappush(heap, (d + 1, u, v))
print('Yes')
for d, p in dist[1:]:
    print(p + 1)

Submission status: Accepted

Solution code:
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)
ans = [-1 for _ in range(n+1)]
ans[1] = 0
q = deque()
q.append(1)
while q:
    x = q.popleft()
    for y in graph[x]:
        if ans[y] == -1:
            q.append(y)
            ans[y] = x
print("Yes")
for i in range(2,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
path = [[] for i in range(n)]

for a,b in lis:
    path[a-1].append(b-1)
    path[b-1].append(a-1)
gone = [0] * n
gone[0] = 1
ans = [-1] * n
now = {0}
for i in range(10 ** 5):
    next = set()
    while now:
        a = now.pop()
        for go in path[a]:
            if gone[go] == 0:
                gone[go] = 1
                ans[go] = a
                next.add(go)
    now = next
print("Yes")
for i in range(1,n):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
import queue
import sys
sys.setrecursionlimit(1000000)

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)
    
P=[-1]*n #親格納配列
q=queue.Queue()
q.put(0)
while not q.empty(): #qが空になるまで(BFS:幅優先探索)
    now=q.get() #取り出す
    for i in G[now]:
        if P[i]==-1 and i!=0: #未探索の場合
            P[i]=now #親を記録
            q.put(i) #親としてqに入れる
print("Yes")
for i in range(1,n):
    print(P[i]+1)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
edge=[]
ans=[-1]*n
for i in range(n):
    edge.append([])
for i in range(m):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
q=deque([0])
while q:
    x=q.popleft()
    for i in range(len(edge[x])):
        if ans[edge[x][i]]==-1:
            ans[edge[x][i]]=x+1
            q.append(edge[x][i])
print('Yes')
for i in range(len(ans)-1):
    print(ans[i+1])

Submission status: Accepted

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

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

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

q = queue.Queue()
q.put(0)
point = [0] * n
seen = [0] * n
seen[0] = 1

while not q.empty():
    i = q.get()
    for j in graph[i]:
        if seen[j] == 0:
            point[j] = i + 1
            seen[j] = 1
            q.put(j)

print('Yes')
for x in range(1, n):
    print(point[x])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,M=mis()
    W = [None] + [set() for _ in range(N)]
    for _ in range(M):
        a, b = mis()
        W[a].add(b)
        W[b].add(a)
    ans = [None]*(N+1)
    ans[1] = True
    q = deque()
    q.append(1)
    while q:
        p = q.popleft()
        for np in W[p]:
            if ans[np] is None:
                ans[np] = p
                q.append(np)
    print('Yes')
    print(*ans[2:], sep='\n')


main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10**15

def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    prev = [-1] * n
    d[s] = 0
    heappush(que, (0, s))

    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                prev[w] = v
                heappush(que, (d[w], w))

    return d, prev

n, m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    ui, vi = map(int, input().split())
    ui, vi = vi-1, ui-1
    edges[ui].append((1, vi))
    edges[vi].append((1, ui))

d, prev = dijkstra(0, edges)
print('Yes')
for i in range(1, n):
    print(prev[i]+1)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())

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

q = deque([1])
ans = {}

visited = [False] * (n+1)
visited[1] = True

while q:
    now = q.popleft()
    for i in graph[now]:
        if not visited[i]:
            q.append(i)
            visited[i] = True
            ans[i] = now

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
adj = [list() for _ in range(N)]
for _ in range(M):
    a, b = MI()
    a, b, = a - 1, b - 1
    adj[a].append(b)
    adj[b].append(a)

q = deque()
q.append((0, -1))
seen = set()
seen.add(0)
ans = [0] * N
while len(q) > 0:
    v, p = q.popleft()
    ans[v] = p
    for nxt in adj[v]:
        if nxt not in seen:
            q.append((nxt, v))
            seen.add(nxt)
print('Yes')
for a in ans[1:]:
    print(a + 1)

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

# mod = int(1e9+7)
mod = 998244353
INF = 1<<29
lINF = 1<<35

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

def main():
    n,m = readInt()
    g = [[] for i in range(n)]
    for i in range(m):
        x,y = readInt()
        g[x-1].append(y-1)
        g[y-1].append(x-1)
    v = [[-1,-1] for i in range(n)]
    v[0] = [0,0]
    q = queue.Queue()
    q.put(0)
    while not q.empty():
        x = q.get()
        for y in g[x]:
            if v[y][0]!=(-1):
                continue
            q.put(y)
            v[y][0] = v[x][0] + 1
            v[y][1] = x
    print("Yes")
    for i in range(1,n):
        print(v[i][1]+1)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

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

class Graph(): #non-directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]-1].append(e[1]-1)
            self.graph[e[1]-1].append(e[0]-1)
            self.deg[e[0]-1] += 1
            self.deg[e[1]-1] += 1
    def BFS(self,s):
        dist = [None for _ in range(self.n)]
        dist[s] = 0
        queue = deque([s])
        self.par = [None for _ in range(self.n)]
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                if dist[adj] is not None:
                    continue
                dist[adj] = dist[node]+1
                self.par[adj] = node
                queue.append(adj)
        return dist

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

G = Graph(N, E)

G.BFS(0)
res = list()

print('Yes')

for i in range(N):
    if i == 0:
        continue
    res.append(G.par[i] + 1)

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
from queue import Queue
INF = 10 ** 6
N, M = map(int,input().split())
Q = Queue()
edges = [[] for _ in range(N+1)]
guidepost = [INF for _ in range(N+1)]
for _ in range(M):
    A, B = map(int,input().split())
    edges[A].append(B)
    edges[B].append(A)
Q.put(1)
while not Q.empty():
    parent = Q.get()
    for i in edges[parent]:
        if guidepost[i] == INF:
            guidepost[i] = parent
            Q.put(i)
print('Yes')
for i in range(2,N+1):
    print(guidepost[i])

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    ta, tb = map(int, input().split())
    E[ta].append(tb)
    E[tb].append(ta)

q = [1]

root = [0] * (N+1)
root[0], root[1] = -1, -1
flg = [0] * (N+1)
flg[0], flg[1] = 1, 1

while q:
    cp = q.pop(0)
    for np in E[cp]:
        if root[np] != 0:
            continue
        else:
            root[np] = cp
            q.append(np)

for i in range(2, N+1):
    if root[i] == 0:
        print('No')
        sys.exit()

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

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))  # (cost, 探索候補ノード)
        v = collections.defaultdict(bool)  # 確定済かどうか
        while len(q):
            # ノードuにおけるコストはk
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:  # cost is ud from u to uv
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    # def getDijkstraShortestPath(self, start, goal):
    #     """
    #     Parameters
    #     ----------
    #     start:int
    #         start node
    #     goal:int
    #         goal node

    #     Return
    #     ----------
    #     ShortestPath:list(int)
    #         shortest path
    #     """
    #     _, prev = self.Dijkstra_search(start)
    #     shortestPath = []
    #     node = goal
    #     while node is not None:
    #         shortestPath.append(node)
    #         node = prev[node]
    #     return shortestPath[::-1]


N, M = map(int, input().split())
graph = Dijkstra()
for i in range(M):
    a, b = map(int, input().split())
    # 0-indexじゃなくてもいい
    graph.add(a, b, 1, directed=False)
ans = []
_, prev = graph.Dijkstra_search(1)
for i in range(2, N + 1):
    if prev[i] is None:
        print("No")
        exit()
    else:
        ans.append(prev[i])
print("Yes")
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
connections = [[] for _ in range(N)]
for a, b in AB:
    connections[a - 1].append(b - 1)
    connections[b - 1].append(a - 1)

markers = [-1] * N

queue = [0]
steps = [-1] * N
steps[0] = 0
while len(queue) >= 1:
    room = queue.pop(0)
    for r in connections[room]:
        if steps[r] >= 0:
            continue
        queue.append(r)
        steps[r] = steps[room] + 1
        markers[r] = str(room + 1)

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

Submission status: Accepted

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

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)

vst = [-1] * N
q = [0]
vst[0] = 0
cnt = 0
for u in q:
    cnt += 1
    for v in adj[u]:
        if vst[v] < 0:
            vst[v] = u
            q.append(v)

if cnt == N:
    print('Yes')
    for k in vst[1:]:
        print(k + 1)

else:
    print('No')

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

ans = [0]*N
G = [set() for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

q = collections.deque([0])

r = set()
r.add(0)
while(q):
    x = q.popleft()
    for y in G[x]:
        if y in r:
            continue
        else:
            ans[y] = x+1
            r.add(y)
            q.append(y)

if len(r) < N:
    print('No')
else:
    print("Yes")
    print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
g = [[] for i in range(n)]
for i in range(m):
    a,b = na()
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

from collections import deque
d = deque([0])
dp = [100000000000]*n
ma = [0]*n
i = 1

while d:
    a = d.popleft()
    for j in g[a]:
        if dp[j] > i:
            dp[j] = i
            ma[j] = a
            d.append(j)
    i += 1

print('Yes')

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [deque() for _ in range(N+1)]
ans = [0]*(N+1)
for _ in range(M):
  a, b = map(int, input().split())
  G[a].append(b)
  G[b].append(a)
memo = [False]*(N+1)
q = deque()
q.append(1)
while q:
  x = q.popleft()
  if not memo[x]:
    memo[x] = True
    for y in G[x]:
      if ans[y] == 0:
        ans[y] = x
        q.append(y)
print("Yes")
print("\n".join([str(x) for x in ans[2:]]))

Submission status: Accepted

Solution code:
import sys
from collections import deque


N, M = map(int, input().split())
edge = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1; b -= 1
    edge[a].add(b)
    edge[b].add(a)

INF = 10 ** 8
path = [INF] * N
prev = [0] * N

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

while q:
    v, s = q.popleft()
    ns = s + 1
    for nv in edge[v]:
        if path[nv] > ns:
            path[nv] = ns
            prev[nv] = v
            q.append((nv, ns))

print('Yes')
for i in range(N - 1):
    print(prev[i + 1] + 1)