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())
graph=[[] for _ in range(N)]

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

dist=[-1]*N
pre=[-1]*N
dist[0]=0

q=deque()
q.append(0)

while q:
    v=q.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        else:
            dist[i]=dist[v]+1
            pre[i]=v
            q.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
sign = [-1] * N

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

d = deque([0])

while d:
    cur = d.popleft()
    for adj in edge[cur]:
        if sign[adj] == -1:
            sign[adj] = cur
            d.append(adj)

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

Submission status: Accepted

Solution code:
def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		route[A - 1] += [B]
		route[B - 1] += [A]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)

	for r in route[0]:
		checked[r - 1] = 1

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		signal[src - 1] = str(checking["dst"])
		rooms = route[src - 1]
		for r in rooms:
			if checked[r - 1] == 0:
				to_check.append({"src": r, "dst": src})
				checked[r - 1] = 1

	if signal.count(0) > 0:
		print("No")
	else:
		print("Yes")
		print("\n".join(signal[1:]))

main()

Submission status: Accepted

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

import heapq

def dijkstra(s):
    d = 1
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for u in e[v]:
            tmp = 1 + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    e[a].append(b)
    e[b].append(a) # 有向グラフでは削除

d = dijkstra(0)
# print(d)
# print(e)
ans = [0]*(n)
for i in range(1,n):
    for j in e[i]:
        # print(i,j)
        if d[j] == d[i] - 1:
            ans[i] = j + 1
            continue

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [None] + [[] for _ in range(n)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)

    explored = {1}
    queue = collections.deque([1])
    ans = [None for _ in range(n+1)]
    while len(queue)!=0:
        nxt = queue.popleft()
        for nbh in route[nxt]:
            if nbh not in explored:
                ans[nbh] = nxt
                queue.append(nbh)
                explored.add(nbh)
    print("Yes")
    print(*ans[2:],sep="\n")
        
main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
n,m = map(int,input().split())
d = defaultdict(list)
for i in range(m):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)

visited = [False]*(n+1)
que = deque([1])
visited[1] = True
ans = [-1]*(n+1)

while que:
    v = que.popleft()
    vlist = d[v]
    for next in vlist:
        if not visited[next]:
            que.append(next)
            visited[next] = True
            ans[next] = v

if -1 in ans[2:]:
    print('No')
    exit()
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Accepted

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

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

conne = [[] for _ in range(n+1)]
dist = [999999]*(n+1)
par = [0] * (n+1)

for i in range(m):
    a,b = map(int,input().split()) 
    conne[a].append(b)
    conne[b].append(a)
    
q=queue.Queue()
dist[1] = 0
q.put((1,0))

while not q.empty():
    
    x,d = q.get()
    
    for i in conne[x]:
        if dist[i]==999999:
            q.put((i,d+1))
            par[i] = x
            dist[i] = d+1

if max(dist[1:]) == 999999:
    print("No")
    
else:
    print("Yes")    
    
    for i in par[2:]:
        print(i)

Submission status: Accepted

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

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

conne = [[] for _ in range(n+1)]
dist = [99999]*(n+1)
par = [0] * (n+1)

for i in range(m):
    a,b = map(int,input().split()) 
    conne[a].append(b)
    conne[b].append(a)
    
q=queue.Queue()
dist[1] = 0
q.put((1,0))

while not q.empty():
    
    x,d = q.get()
    
    for i in conne[x]:
        if dist[i]==99999:
            q.put((i,d+1))
            par[i] = x
            dist[i] = d+1


print("Yes")    

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

Submission status: Accepted

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

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

conne = [[] for _ in range(n)]
dist = [99999]*(n)
par = [0] * (n)

for i in range(m):
    a,b = map(int,input().split()) 
    conne[a-1].append(b-1)
    conne[b-1].append(a-1)
    
q=queue.Queue()
dist[0] = 0
q.put((0,0))

while not q.empty():
    
    x,d = q.get()
    
    for i in conne[x]:
        if dist[i]==99999:
            q.put((i,d+1))
            par[i] = x
            dist[i] = d+1

print("Yes")    

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

Submission status: Accepted

Solution code:
import copy
N, M = map(int, input().split())
res = [[] for i in range(N+5)]


for i in range(M) :
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    res[a].append(b)
    res[b].append(a)
    
pre = [-1] * N
dist = [-1] * N
d = 1
dl = []
pre[0] = 0
dist[0] = 0
dl.append(0)

while(len(dl) != 0) :
    a = dl[0]
    dl.pop(0)
    for i in res[a] :
        if(dist[i] != -1):
            continue
        dist[i] = dist[a] + 1
        pre[i] = a
        dl.append(i)
        
for i in range(N) :
    if(i == 0) :
        print("Yes")
        continue
    print(pre[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
k=[0]*(n+1)
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            k[i]=p
            data.append(i)
    r[p]=[]
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        print(k[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
    r[p]=[]
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in R[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
    r[p]=[]
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in R[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
    
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in R[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)

if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in r[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Submission status: Accepted

Solution code:
import numpy as np
from sys import stdin

def getval():
    n,m = map(int,input().split())
    path = [[] for i in [0]*(n+1)]
    for i in [0]*m:
        a,b = map(int, stdin.readline().split())
        path[a].append(b)
        path[b].append(a)
    return n,m,path

def solve(n,m,p):
    prev = np.zeros((n+1))
    q = [1]
    while q:
        idx = q.pop(0)
        adj = p[idx]
        for i in adj:
            if prev[i]:
                continue
            prev[i] = idx
            q.append(i)
    print("Yes")
    for i in range(2,n+1):
        print(int(prev[i]))

if __name__=="__main__":
    n,m,p = getval()
    #print(p)
    solve(n,m,p)

Submission status: Accepted

Solution code:
import sys
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 = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

q = [0] * (n+1)
q[0] = -1

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = v
        d.append(i)

ans = dist[2:]
if -1 in ans:
    print('No')
    exit()
else:
    print('Yes')
    print(*ans, sep="\n")
    exit

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
dis = [n+2]*(n)
dis[0] = 0
near = [[] for _ in range(n)]
mark = [-1]*(n)
mark[0] = 0
que = deque()
for _ in range(m):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  near[a].append(b)
  near[b].append(a)
  if a==0:
    que.appendleft(b)
    mark[b] = 0
    dis[b] = 1
  if b==0:
    que.appendleft(a)
    mark[a] = 0
    dis[a] = 1
while que:
  i = que.popleft()
  for j in near[i]:
    if dis[i]+1<dis[j]:
      dis[j] = dis[i]+1
      mark[j] = i
      que.append(j)
if n+2 not in dis:
  print('Yes')
  for i in mark[1:]:
    print(i+1)
else:
  print('No')

Submission status: Accepted

Solution code:
from collections import deque

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

if len(c[0]) == 0:
    print('No')
    exit()

l = [0]*n
l[0] = 1
q = deque()
for i in c[0]:
    q.append(i)
    l[i] = 1
while q:
    p = q.pop()
    for i in c[p]:
        if l[i] == 0:
            l[i] = p+1
            q.appendleft(i)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

  
dist=[-1]*(N+1)
d=deque([1])

while d:
  x = d.popleft()
  for i in range(len(edge[x])):
    if dist[edge[x][i]]==-1:
      dist[edge[x][i]]=x
      d.append(edge[x][i])

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

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
load = [list(map(int,input().split())) for _ in range(m)]
goal = [[] for _ in range(n)]
for i in load:
    goal[i[0]-1].append(i[1]-1)
    goal[i[1]-1].append(i[0]-1)

q = deque([0])
ans = [-1 for _ in range(n)]
ans[0] = 0
while q:
    check = q.popleft()
    for j in goal[check]:
        if ans[j] == -1:
            ans[j] = check+1
            q.append(j)
if -1 in ans:
    print("No")
else:
    print("Yes")
    for p in range(1,n):
        print(ans[p])

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(M):
    link[L[i][0]-1].append(L[i][1]-1)
    link[L[i][1]-1].append(L[i][0]-1)

checked = [-1 for _ in range(N)]
checked[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(len(link[now])):
        if checked[link[now][i]] == -1:
            checked[link[now][i]] = now + 1
            d.append(link[now][i])


flag = False
for i in range(1, N):
    if checked[i] == -1:
        flag = True
        break

if flag:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(checked[i])

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
G = [None] + [[] for i in range(N)]
dist = [None]+[-1]*N
ans = [None]+[10**6]*N

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

deq = deque()

dist[1] = 0
deq.append(1)

while len(deq) != 0:
    v = deq.popleft()
    
    for i in G[v]:
        if dist[i] != -1:
            if dist[v]-dist[i] == 1:
                ans[v] = i
            continue
        dist[i] = dist[v]+1
        deq.append(i)

print("Yes")

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

Submission status: Accepted

Solution code:


# ABC168D
# https://atcoder.jp/contests/abc168/tasks/abc168_d

n,m=map(int, input().split())
ab=[[]for _ in range(n)]
for i in range(m):
    a,b = list(map(int, input().split()))
    a,b = a-1, b-1
    ab[a].append(b)
    ab[b].append(a)
    '''
    まず両方を追加する考えがなかった。
    浅い部屋からも深い部屋からも参照できる。
    その代わりに visitedで考えなくて良い部屋を記録している。
    部屋１につながっているのはもっとも浅い部屋でそこから考えることがきっかけになる？
    '''
#print(ab)
ans = [0]*n
visited={0}
stack=[0]
for i in stack:
    '''
    現在考えている部屋を stack、そこにつながる部屋 ab[i]として考える。
    stack=[0]なので1の部屋から始める。なので深さ1の部屋が ab[i](ab[0])で分かる。
    i==0の始めの一周では、ab[i]は深さ１の部屋のリストであり、それぞれの部屋を jとして順番に考える。
    (このように深さ1から考えられる＋次に深さ2の部屋を求めるというのが上手くいく)
    その現在考えている部屋 i(stackの循環)とそこにつながる部屋 j(abの循環)なので、
    部屋 jはより浅い部屋 iを道しるべにすればよい。
    しかし、ab[a], ab[b]と両方を追加しているので、浅い部屋も深い部屋も abには含まれている。
    浅い部屋から順に考えているので、過去に調べた abの値は無視するために visitedを導入する。たぶん。
    '''
    for j in ab[i]:
        #print(i,j,'----------------------')
        if j in visited:
            continue
        stack.append(j)
        visited.add(j)
        ans[j]=i+1
        #print('stack', stack)
        #print('visited', visited)
        #print('ans', ans)
'''check=0
for i in ans[1:]:
    if i==0:check==1
if check:
    print('No')
else:
    print("Yes")
    print(*ans[1:])'''
print("Yes")
print(*ans[1:])

Submission status: Accepted

Solution code:


# ABC168D
# https://atcoder.jp/contests/abc168/tasks/abc168_d

n,m=map(int, input().split())
ab=[[]for _ in range(n)]
for i in range(m):
    a,b = list(map(int, input().split()))
    a,b = a-1, b-1
    ab[a].append(b)
    ab[b].append(a)
    '''
    まず両方を追加する考えがなかった。
    浅い部屋からも深い部屋からも参照できる。
    その代わりに visitedで考えなくて良い部屋を記録している。
    部屋１につながっているのはもっとも浅い部屋でそこから考えることがきっかけになる？
    '''
#print(ab)
ans = [0]*n
visited={0}
stack=[0]
for i in stack:
    '''
    現在考えている部屋を stack、そこにつながる部屋 ab[i]として考える。
    stack=[0]なので1の部屋から始める。なので深さ1の部屋が ab[i](ab[0])で分かる。
    i==0の始めの一周では、ab[i]は深さ１の部屋のリストであり、それぞれの部屋を jとして順番に考える。
    (このように深さ1から考えられる＋次に深さ2の部屋を求めるというのが上手くいく)
    その現在考えている部屋 i(stackの循環)とそこにつながる部屋 j(abの循環)なので、
    部屋 jはより浅い部屋 iを道しるべにすればよい。
    しかし、ab[a], ab[b]と両方を追加しているので、浅い部屋も深い部屋も abには含まれている。
    浅い部屋から順に考えているので、過去に調べた abの値は無視するために visitedを導入する。たぶん。
    '''
    for j in ab[i]:
        #print(i,j,'----------------------')
        if j in visited:
            continue
        stack.append(j)
        visited.add(j)
        ans[j]=i+1
        #print('stack', stack)
        #print('visited', visited)
        #print('ans', ans)
check=0
for i in ans[1:]:
    if i==0:check==1
if check:
    print('No')
else:
    print("Yes")
    print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque
N, M = list(map(int, input().split()))
S = [set() for _ in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    S[a].add(b)
    S[b].add(a)
# print(S)

parents = [-1]*N
parents[0] = 0
L = deque([0])
while L:
    k = L.pop()
    s=S[k]
    for l in s:
        if parents[l] < 0:
            L.appendleft(l)
            parents[l] = k
    # print(L)

if -1 in parents:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(parents[i]+1)

Submission status: Accepted

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    AB = {}
    for _ in range(M):
        a, b = list(map(int, input().split()))
        a, b = a-1, b-1
        if a not in AB:
            AB[a] = []
        if b not in AB:
            AB[b] = []
        AB[a].append(b)
        AB[b].append(a)

    import collections
    q = collections.deque([0])
    passed = [-1 for i in range(N)]
    passed[0] = 0
    while q:
        node = q.pop()
        for nxt in AB[node]:
            if passed[nxt] == -1:
                passed[nxt] = node
                q.appendleft(nxt)
    #print(metrics)
    for m in passed:
        if m == -1:
            print("No")
            return
    print("Yes")
    for i in range(1, N):
        print(passed[i]+1)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import heapq
def dijkstra(s):
    p=[x for x in range(n)]#親の記憶
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                p[u]=v
                heapq.heappush(hq, (tmp, u))
    return p

n,m = map(int,input().split())
#重み付き有向グラフの隣接リストe(重み=1)
e = [[] for _ in range(n)]
t=1
for _ in range(m):
    a,b= map(int,input().split())
    a,b = a-1, b-1
    e[a].append((t, b))
    e[b].append((t, a))

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

Submission status: Accepted

Solution code:
#ダイクストラ法
import heapq
def dijkstra(s):
    p=[x for x in range(n)]#親の記憶
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                p[u]=v
                heapq.heappush(hq, (tmp, u))
    return p

n,m = map(int,input().split())
#重み付き有向グラフの隣接リストe(重み=1)
e = [[] for _ in range(n)]
t=1
for _ in range(m):
    a,b= map(int,input().split())
    a,b = a-1, b-1
    e[a].append((t, b))
    e[b].append((t, a))

ans = dijkstra(0)
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())

graph = [[] for _ in range(N)]
flag = [0] * 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()
D.append(0)
visited = [False] * N
visited[0] = True

while D:
  v = D.popleft()
  for nv in graph[v]:
    if visited[nv] == True:
      continue
    visited[nv] = True
    flag[nv] = v
    D.append(nv)
    
print("Yes")
for i in range(1,N):
  print(flag[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

dist = [-1] * (N+1)
dist[1] = 0
connection = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

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

que = deque()
que.append(1)

while que:
    v = que.popleft()

    for i in connection[v]:
        if dist[i] != -1:continue

        dist[i] = dist[v] + 1
        que.append(i)
        ans[i] = v

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
print('Yes')
root=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)
q=deque([0])
check=[0]*n
while q:
    e=q.popleft()
    for i in root[e]:
        if check[i]:
            continue
        check[i]=e+1
        q.append(i)
for i in range(1,n):
    print(check[i])

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
#隣接リスト
print("Yes")
g = [[] for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  #0-indexにします
  g[a-1].append(b-1)
  g[b-1].append(a-1)
q = deque([])
q.append(0)
check = [0] * n
while len(q) > 0:
  e = q.popleft()
  for i in g[e]:
    if check[i] > 0:
      continue
    check[i] = e + 1
    q.append(i)
for i in range(1,n):
  print(check[i])

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
#隣接リスト
print("Yes")
g = [[] for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  #0-indexにします
  g[a-1].append(b-1)
  g[b-1].append(a-1)
q = deque([])
q.append(0)
check = [0] * n
while len(q) > 0:
  e = q.popleft()
  for i in g[e]:
    if check[i] > 0:
      continue
    check[i] = e + 1
    q.append(i)
for i in range(1,n):
  print(check[i])

Submission status: Accepted

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

graph = [[] for _ in range(N)]
flag = [0] * 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])
visited = [False] * N
visited[0] = True

while D:
  v = D.popleft()
  for i in graph[v]:
    if visited[i]:
      continue
    visited[i] = True
    flag[i] = v
    D.append(i)
    
print("Yes")
for i in range(1, N):
  print(flag[i] + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import chain

# from itertools import combinations as comb
# form bisect import bisect_left, bisect_right, insort_left, insort_right
# from collections import Counter
# import numpy as np

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    routes = [set() for _ in range(N)]
    marks = [None for _ in range(N)]
    for a, b in zip(A, B):
        a = a - 1
        b = b - 1
        routes[a].add(b)
        routes[b].add(a)

    marks[0] = -1
    cur_rooms = [0]
    count = 1
    while count < N:
        new_cur_rooms = []
        for cur_room in cur_rooms:
            next_rooms = list(routes[cur_room])
            for next_room in next_rooms:
                if marks[next_room] is None:
                    marks[next_room] = cur_room
                    new_cur_rooms.append(next_room)
                    count += 1
        cur_rooms = new_cur_rooms

    answer = "Yes\n" + "\n".join((str(n + 1) for n in marks[1:]))

    return answer


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    # N, M, A, B = map(int, line.split())
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    answer = solve(N, M, A, B)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue
n,m=map(int,input().split())
l=[[] for i in range(n)]

for _ in range(m):
    tempa,tempb=map(int,input().split())
    tempa-=1
    tempb-=1
    l[tempa].append(tempb)
    l[tempb].append(tempa)
que=queue.Queue()
dist=[-1]*n

dist[0]=0
que.put(0)
ans=[0]*n

while not que.empty():
    v=que.get()

    for nv in l[v]:
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+1
        que.put(nv)
        ans[nv]=v
if -1 in dist:
    print('No')
else:
    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())
haba=[[] for i in range(N+1)]
for i in range(M):
    A,B=map(int,input().split())
    haba[A].append(B)
    haba[B].append(A)
kyori=[-1]*(N+1)
kyori[0]=0
kyori[1]=0

que=deque()
que.append(1)

while que:
    kari=que.popleft()
    for i in haba[kari]:
        if kyori[i]!=-1:
            continue
        kyori[i]=kari
        que.append(i)

ans=kyori[2:]
print("Yes")
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

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

visited = [False] * N
par = [0] * N
visited[0] = True
d = deque(G[0])
for i in G[0]:
    visited[i] = True
    par[i] = 0
cur = 0
while d:
    cur = d.popleft()
    for i in G[cur]:
        if not visited[i]:
            visited[i] = True
            par[i] = cur
            d.append(i)

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

Submission status: Accepted

Solution code:
from collections import deque
infty = 10 ** 9

def BFS(graph, parent, u):
    queue = deque()
    queue.append(u)
    visited = [False for k in range(len(parent))] #探索が始まったか否か
    visited[u] = True
    while queue:
        v = queue.popleft()
        for j in graph[v]:
            if not visited[j]:
                queue.append(j)
                visited[j] = True
                parent[j] = v

n, m = map(int, input().split())
graph = [[] for i 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)
parent = [-1 for i in range(n)]
BFS(graph, parent, 0)
if -1 in parent[1:]:
    print("No")
else:
    print("Yes")
    for p in parent[1:]:
        print(p+1)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().strip().split())
l=[]
dp=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().strip().split())
    l.append((a,b))
    dp[a-1].append(b)
    dp[b-1].append(a)

d=deque([1])
visited=[0 for _ in range(N)]
visited[0]=1
cnt=1
while d:
    tmp=d.popleft()
    for e in dp[tmp-1]:
        if visited[e-1]==0:
            visited[e-1]=tmp
            cnt+=1
            d.append(e)
            
if cnt!=len(visited):
    print("No")
else:
    print("Yes")
    for n in range(1,N):
        print(visited[n])