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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

for i in range(n):
    if len(arr[i])==0:
        print('No')
        sys.exit()

def bfs(d):
    que=deque()
    que.append(0)
    ans=[0]*n
    while que:
        x=que.popleft()
        if x==0:
            for i in arr[x]:
                ans[i]=1
                que.append(i)
        else:
            for i in arr[x]:
                if ans[i]==0 and i!=0:
                    ans[i]=x+1
                    que.append(i)
    print('Yes')
    for i in range(1,n):
        print(ans[i])        

bfs(arr)

Submission status: Accepted

Solution code:
from collections import deque

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

line = [[] for _ in range(N+1)]
flag = True
ans = [0] * (N+1)

for A,B in AB:
    line[A].append(B)
    line[B].append(A)

def bfs(now):
    que = deque()
    que.append(now)
    while que.__len__() != 0:
        now = que.popleft()
        for ne in line[now]:
            if ans[ne] != 0:
                continue
            ans[ne] = now
            que.append(ne)

bfs(1)
if 0 in ans[2:]:
    print('No')
else:
    print('Yes')
    print("\n".join(str(i) for i in ans[2:]))

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict
import collections
import math
import sys
import queue
sys.setrecursionlimit(200000)
mod = 1000000007

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

graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

tf = [False] * (n + 1)
sirube = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v,0])
    tf[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        before = sub[1]
        for next in graph[now]:
            if tf[next]:
                continue
            tf[next] = True
            if sirube[next] == 0:
                sirube[next] = now
            q.put([next, now])

bfs(1)
for i in range(2, n + 1):
    if sirube[i] == 0:
        print("No")
        exit()

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
n,m = map(int,input().strip().split())
graph = defaultdict(list)
for _ in range(m):
    u,v = map(int,input().strip().split())
    graph[u].append(v)
    graph[v].append(u)

queue = deque()
queue.append(1)

mini_passage = defaultdict(list)
visited = defaultdict(int)
level = 0
while queue:
    temp = []
    while queue:
        x = queue.pop()
        visited[x] = 1
        for neighbour in graph[x]:
                #if not visited[neighbour]:
                if neighbour in mini_passage:
                    if level<mini_passage[neighbour][1]:
                        mini_passage[neighbour] = [x,level]
                        temp.append(neighbour)
                else:
                    mini_passage[neighbour] = [x, level]
                    temp.append(neighbour)
    queue = temp.copy()
    level += 1
#print(mini_passage)
if len(mini_passage)<n-1:
    print("No")
else:
    print("Yes")
    for key in range(2,n+1):
        print(mini_passage[key][0])

Submission status: Accepted

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


from collections import defaultdict
import queue
connection = defaultdict(lambda: defaultdict(int))

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

c = defaultdict(int)
q = queue.Queue()
d = defaultdict(int)
p = defaultdict(int)

c[0] = 1
d[0] = 0
q.put(0)

while not(q.empty()):
  u = q.get()
  for v in connection[u]:
    if c[v] == 0:
      c[v] = 1
      d[v] = d[u] + 1
      p[v] = u
      q.put(v)
  c[u] = 2
print("Yes")
for i in range(1,N):
  print(p[i] + 1)

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())
    a -= 1
    b -= 1
    node[a].append(b)
    node[b].append(a)

ans = [-1] * n
ans[0] = 0
stk = [[0] + node[0]]

while stk:
    s = stk.pop(0)
    fr = s[0]
    for i in s[1:]:
        if ans[i] == -1:
            ans[i] = fr + 1
            stk.append([i] + node[i])

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

Submission status: Accepted

Solution code:
from collections import deque

INF = 10**6
n, m = map(int, input().split())
path = {i: [] for i in range(1, n+1)}
for i in range(m):
    a, b = map(int, input().split())
    path[a].append(b)
    path[b].append(a)

dist = [INF for i in range(n+1)]
dist[1] = 0
ans = [0 for i in range(n+1)]
que = deque([1])

while len(que) > 0:
    p = que.popleft()
    for r in path[p]:
        if dist[r] == INF:
            dist[r] = dist[p] + 1
            ans[r] = p
            que.append(r)

print('Yes')
for a in ans[2:]:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque

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

adj_list = [[] for _ in range(n)]

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

distance = [-1] * n
prev = [-1] * n

q = deque()
q.append([0, 0, 0])  #[room, distance, prev]

while len(q) > 0:
    room, d, p = q.popleft()
    #if distance[room] == -1:
    #    distance[room] = d
    #    prev[room] = p

    for n_room in adj_list[room]:
        if distance[n_room] > 0:
            continue
        q.append([n_room, d + 1, room])
        distance[n_room] = d + 1
        prev[n_room] = room

flag = True
for i in range(n):
    if distance[i] < 0:
        flag = False
        break

if flag is True:
    print("Yes")
    for i in range(1, n):
        print(prev[i] + 1)
else:
    print("No")

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())
    AB = [set() for _ in range(n+1)]
    for a, b in map(lambda x: map(int, x.split()), args[1:]):
        AB[a].add(b)
        AB[b].add(a)

    inf = 10**9
    D = [inf]*(n+1)
    B = [0]*(n+1)

    Q = deque()
    Q.append((1, 0, 0))  # room, distance, previous room
    while Q:
        r, d, p = Q.popleft()
        if d < D[r]:
            D[r] = d
            B[r] = p
            for nr in AB[r]:
                Q.append((nr, d+1, r))

    ret = ['Yes']
    for i in range(2, n+1):
        if D[i] == inf:
            ret = ['No']
            break
        ret.append(str(B[i]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

aisle_dict = {i+1:[] for i in range(N)}
direction = {1:0}

for i in range(M):
    A, B = list(map(int, input().split()))
    aisle_dict[A].append(B)
    aisle_dict[B].append(A)
    
def calc_next(current_rooms):
    all_next_rooms = []
    for current_room in current_rooms:
        next_rooms = aisle_dict[current_room]
        for room in next_rooms:
            if room not in direction:
                direction[room] = current_room
                all_next_rooms.append(room)
    return all_next_rooms
    
rooms = [1]
while len(direction) < N:
    rooms = calc_next(rooms)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
from collections import deque, defaultdict

N, M = [int(x) for x in stdin.readline().rstrip().split()]

par = [i for i in range(N+1)]
rank = [0] * (N+1)
size = [1] * (N+1)


def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
        size[y] += size[x]
        size[x] = 0

    else:
        par[y] = x
        size[x] += size[y]
        size[y] = 0
        if rank[x] == rank[y]:
            rank[x] += 1


def check_same(x, y):
    return find(x) == find(y)


def check_size(x):
    return size[find(x)]


adj = defaultdict(set)

for _ in range(M):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    union(A, B)
    adj[A].add(B)
    adj[B].add(A)

print("Yes")
ans = [0]*(N+1)
visit_p = deque()
visit_p.append((1, 0))
visited = [False]*(N+1)
visited[1] = True
dist = [10**18]*(N+1)

while visit_p:
    now_v, distance = visit_p.popleft()
    for v in adj[now_v]:
        if visited[v]:
            continue

        if distance < dist[v]:
            ans[v] = now_v
        dist[v] = min(dist[v], distance)

        visited[v] = True
        visit_p.append((v, 1+distance))

for k in ans[2:]:
    print(k)

Submission status: Accepted

Solution code:
class Room:
    def __init__(self, prev=-1, dist=1 << 64):
        self.prev = prev
        self.dist = dist


n, m = map(int, input().split())
passages = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    passages[a].add(b)
    passages[b].add(a)

opening = {0}
closing = {0}
guide_points = [-1] * n
while opening:
    next_opening = set()

    for curr_room in opening:
        for next_room in passages[curr_room]:
            if next_room in closing:
                continue

            guide_points[next_room] = curr_room
            next_opening.add(next_room)
            closing.add(next_room)

    opening = next_opening

print('Yes')
print('\n'.join(map(lambda x: str(x + 1), guide_points[1:])))

Submission status: Accepted

Solution code:
import queue

n, m = map(int, input().split())
ng_s = 10 ** 6

d = [[]] * (n+1)
s = [ng_s] * (n+1)
for i in range(1, n+1):
  d[i] = []

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

#print(n, m)
#print(d)
#print(s)

q = queue.Queue()
q.put(1)
s[0] = 0
s[1] = 0

while not q.empty():
  c = q.get()
  to_list = d[c]
  for j in range(len(to_list)):
    to = to_list[j]
    if s[to] == ng_s and to != 1:
      s[to] = c
      q.put(to)
    
s2 = s[2:]

if min(s2) == ng_s:
  print('No')
else:
  print('Yes')
  for i in range(2, n+1):
    print(s[i])

Submission status: Accepted

Solution code:
from collections import deque

def bfs(u):
    dist = [-1 for _ in range(n)]
    dist[u] = 0
    que = deque([])
    que.append(u)

    while que:
        v = que.popleft()
        for nv in G[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v] + 1
            que.append(nv)
            D[nv] = v
    return dist


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)

D = [-1]*n
bfs(0)
print('Yes')
for d in D[1:]:
    print(d+1)

Submission status: Accepted

Solution code:
import math
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import networkx as nx

import heapq
import sys

input = sys.stdin.readline


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

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    path = [-1] * N
    for a,b in edge[s]:
        path[b] = s
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:                
            if used[e[1]]:
                if path[e[1]] == -1:
                    path[e[1]] = v
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d, path

edge = [[] for i in range(N)]

for i in range(M):
    x,y = map(int,input().split())
    edge[x-1].append([1,y-1])
    edge[y-1].append([1,x-1]) 
    

d, path = dijkstra_heap(0, edge)

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

Submission status: Accepted

Solution code:
## coding: UTF-8
from collections import deque

n, m = map(int,input().split())
g = [[] for _ in range(n+1)] # 隣接リスト
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)
#print(g)


def bfs(u):
    queue = deque([u])
    d = [None] * (n+1) # uからの距離の初期化
    r = [None] * (n+1) #return list
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                r[i] = v
                queue.append(i)
    return d, r

# 0からの各頂点の距離
d, r = bfs(1)
#print(d)
#print(r)
print('Yes')
for i in range(2, n+1):
    print(r[i])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
r = [[] for _ in range(N)]
for _ in range(M):
    A_,B_ = map(int,input().split())
    r[A_-1].append(B_-1)
    r[B_-1].append(A_-1)

ans = [0]*N
t = [0]*N
p = [0]

def k(p,t,ans):
    s = []
    for i in p:
        a = r[i]
        for z in a:
            if t[z] == 0:
                s.append(z)
                ans[z] = i
                t[z] = 1
    p = s
    return p,t,ans

while len(p) > 0:
    p,t,ans = k(p,t,ans)

for i in range(N-1):
    if r[i+1] == 0:
        print('No')
        exit()
print('Yes')
for i in range(N-1):
    print(ans[i+1]+1)

Submission status: Accepted

Solution code:
from collections import deque

n,m=map(int,input().split())
l=[[] for i in range(n)]
ans=[-1]*n
flag=[False]*n
q=deque([0])
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    l[a].append(b)
    l[b].append(a)
flag[0]=True
while len(q)>0:
    now=q[0]
    q.popleft()
    for i in l[now]:
        if flag[i]:
            continue
        ans[i]=now
        flag[i]=True
        q.append(i)
if -1 in ans[1:]:
    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())


ar = [[] for _ in range(n)]

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

#print(ar)
#print(ans)
ans[0] = -1
d = deque()


for i in ar[0]:
    d.append(i)
    ans[i-1] = 1

#print("-----")
#print(d)
while d:
    i = d.popleft()
    #print(i)
    #print(d)
    for x in ar[i-1]:
        if(ans[x-1] == 0):
            ans[x-1] = i
            d.append(x)


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

Submission status: Accepted

Solution code:
from collections import deque
INF = 100001000100
n, m = [int(i) for i in input().split()]
room = [[] for _ in range(n)]
room_dis = [INF for _ in range(n)]
sign_post = [0 for _ in range(n)]


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


d = deque([0])
dist = 1
room_dis[0] = 0

while len(d) != 0:
	tmp = d.popleft()
	for next in room[tmp]:
		if room_dis[next] > room_dis[tmp]+1:
			sign_post[next] = tmp
			room_dis[next] = room_dis[tmp]+1
			d.append(next)

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

Submission status: Accepted

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys
nm = [int(s) for s in stdin.readline().rstrip().split()]
n = nm[0]
m = nm[1]
ab = []
for el in range(m):
    tmp = [int(s) for s in stdin.readline().rstrip().split()]
    ab.append(tmp)

data = []
for el in range(n):
    if el == 0:
        data.append({'index': el + 1, 'diff': 0, 'connection': [], 'num': 0})
    else:
        data.append({'index': el + 1, 'diff': 0, 'connection': []})
for el in ab:
    data[el[0]-1]['connection'].append(el[1])
    data[el[1]-1]['connection'].append(el[0])
poss = [1]
count = 1

for elt in range(n):
    tmp = []
    for el in poss:
        for el2 in data[el - 1]['connection']:
            if not 'num' in data[el2-1]:
                tmp.append(el2)
                data[el2-1]['num'] = el
    else:
        poss = tmp
        count += 1

check = True
for el in data:
    if not 'num' in el:
        check = False
if check:
    print('Yes')
    tmp = 0
    for el in data:
        if tmp != 0:
            print(el['num'])
        tmp += 1
if not check:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque
#import sys
#sys.setrecursionlimit(10**6)
#input = sys.stdin.buffer.readline
n,m=map(int,input().split())
g = [[] for j 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,-1)])
d=[-1]*n
d[0]=0
res={}
while len(q)>0:
    u,r = q.popleft()
    for v in g[u]:
        if d[v] == -1 and r != v:
            d[v] = d[u] + 1
            q.append((v,u))
            if not v-1 in res:
                res[v-1] = u+1
res = sorted(res.items())
if len(res) != n-1:
    print("No")
    exit()
print("Yes")
for i,j in res:
    print(j)

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):
        self.g = graph.graph

        # 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 sp(self, goal):
        path = []
        node = goal
        for _ in range(2):
            path.append(node)
            node = self.prev[node]
        return path[1]

n, m = map(int, input().split())
g = Graph()
for i in range(m):
    a, b = map(int, input().split())
    g.add_edge(a-1, b-1, 1)
    g.add_edge(b-1, a-1, 1)

d = Dijkstra(g, 0)
A = []
# print(d.sp(2))
for i in range(n):
    a = d.shortest_distance(i)
    if a == float('inf'):
        print("No")
        break
    else:
        A.append(d.shortest_distance(i))

if len(A) == n:
    print("Yes")
    for i in range(1, n):
        print(d.sp(i) + 1)

Submission status: Accepted

Solution code:
import numpy as np
import heapq

if __name__ == "__main__":
    N, M = map(int, input().split())
    nodes = [[] for i in range(N)]
    costs = [N+1 for i in range(N)]
    costs[0] = 0
    parents = [None for i in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        nodes[a-1].append(b-1)
        nodes[b-1].append(a-1)
    # (cost, node, parent)
    open_list = [(costs[0]+1, c, 0) for c in nodes[0]]
    heapq.heapify(open_list)

    while True:
        # print("="*10)
        # print('costs')
        # print(costs)
        # print('parents')
        # print(parents)
        # print('open_list')
        # print(open_list)
        # print("len", len(open_list))
        if len(open_list) == 0:
            break
        cost, node, parent = heapq.heappop(open_list)
        if parents[node] is not None:
            # 既に親が決まっているなら追加しない
            continue
        else:
            #print("Select:", node)
            costs[node] = cost
            parents[node] = parent
            for child in nodes[node]:
                # print(child)
                if child == 0 or parents[child] is not None:
                    continue
                else:
                    t = (costs[node]+1, child, node)
                    heapq.heappush(open_list, t)
        
    # print(costs)
    # print(parents)
    for i in range(N):
        if i == 0:
            print('Yes') # 'No' になるようなケースはある？
        else:
            print(parents[i]+1)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(100000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def xxx(t,memo,ans,kyori):
    for a in memo[t]:
        if ans[a] == -1 or kyori[a] > (kyori[t]+1):
            ans[a]=t
            kyori[a]=kyori[t]+1
            xxx(a,memo,ans,kyori)


def resolve():
    readline=sys.stdin.readline

    n,m=map(int, readline().rstrip().split())
    memo=[[] for i in range(n)]
    ans=[-1]*n
    kyori=[-1]*n
    ans[0]=0
    kyori[0]=0
    for i in range(m):
        a,b=map(int, readline().rstrip().split())
        memo[a-1].append(b-1)
        memo[b-1].append(a-1)
    #xxx(0,memo,ans,kyori)
    tt=[0]
    while 1:
        nx=[]
        for t in tt:
            for a in memo[t]:
                if ans[a] == -1 or kyori[a] > (kyori[t]+1):
                    nx.append(a)
                    ans[a]=t
                    kyori[a]=kyori[t]+1
        if len(nx)==0:
            break
        else:
            tt=nx
        
    #memo

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


    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
import collections

def BFS(G, s):
    visited = {s: None}
    unvisited = collections.deque([s])
    while unvisited:
        u = unvisited.popleft()
        for v in G[u - 1]:
            if not(v in visited):
                unvisited.append(v)
                visited[v] = u
    
    return visited

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

g = [set([]) for _ in range(n)]

for abi in ab:
    g[abi[0] - 1].add(abi[1])
    g[abi[1] - 1].add(abi[0])

ans = [0] * (n - 1)

for k, v in BFS(g, 1).items():
    if k == 1:
        continue
    else:
        ans[k - 2] = v

print("Yes")
for num in ans:
    print(num)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
R = [-1] * N
# D = [-1] * N
# D[0] = 0

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

d = deque()
d.append(0)

while d:
    v = d.popleft()
    for g in G[v]:
        if g != 0 and R[g] == -1:
            d.append(g)
            R[g] = v + 1

if -1 in R[1:]:
    print("No")
else:
    print("Yes")
    for r in R[1:]:
        print(r)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
n,m = map(int,input().split())
g = {key:[] for key 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)
#ans = {key:0 for key in range(1,n)}
d = deque([(0,g[0])])
C = {0:"Yes"}
#print(g)
while d != deque([]):
    #print(C,d)
    c = d.popleft()
    for i in c[1]:
        if i in C:
            continue
        else:
            d.append((i,g[i]))
            C[i] = c[0]+1
#print("Yes")
for i in range(n):
    if len(C) != n:
        print("No")
        break
    if i == 0:
        print("Yes")
    else:
        print(C[i])

Submission status: Accepted

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

n,m=map(int,input().split())
edges=[[] for i in range(n)]
table=[-1]*n
for i in range(m):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)
l=[0]
print()
from collections import deque as que
q=que([(-1,0)])
p=que()
flag=1
ok=0
while flag:
    flag=0
    while len(q):
        flag=1
        pre,now=q.pop()
        if table[now]==-1:
            ok+=1
            table[now]=pre+1
            for i in edges[now]:
                if table[i]==-1:
                    p.append((now,i))
    p,q=q,p






if ok==n:
    print("Yes")
    for i in range(1,n):
        print(table[i])
else:print("No")

Submission status: Accepted

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

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

linked_room = [[] for i in [1] * n]
sign = [0] * n
sign[0] = 1
arrivable_rooms = 0

for mi in range(m):
    tmp_a, tmp_b = map(int, input().split())
    linked_room[tmp_a-1].append(tmp_b)
    linked_room[tmp_b-1].append(tmp_a)

work_q = collections.deque([1])

while len(work_q) > 0:
    past_room = work_q.pop()
#    print("past room: " + str(past_room))
    next_rooms = linked_room[past_room-1]
    for nri in next_rooms:
        if sign[nri - 1] == 0:
            sign[nri - 1] = past_room
            arrivable_rooms += 1
            work_q.appendleft(nri)

if arrivable_rooms == n-1:
    print('Yes')
    for si in sign[1:n]:
        print(si)
else:
    print('No')

Submission status: Accepted

Solution code:
import math
from queue import Queue

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

gh = {}
for i in range(m):
    p1, p2 = map(int, input().split(" "))
    if p1 in gh:
        gh[p1].append(p2)
    else:
        gh[p1] = [p2]

    if p2 in gh:
        gh[p2].append(p1)
    else:
        gh[p2] = [p1]

_mp = [-1 for _ in range(n)]
_mp[0] = 0
q = Queue()
q.put(1)

while q.qsize() != 0:
    cp = q.get()
    for p in gh[cp]:
        if _mp[p - 1] != -1: continue
        q.put(p)
        _mp[p - 1] = cp

for k, v in gh.items():
    if len(v) == 0:
        print("No")
        exit()

print("Yes")
for mpi in _mp[1:]:
    print(mpi)

Submission status: Accepted

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


used = [False] * N
d = [0] * N
now_list = [(0,0,-1)]
next_list = set()
while len(now_list) > 0:
    for _ in range(len(now_list)):
        c, v, pv = now_list.pop()
        if used[v]: continue
        d[v] = pv
        used[v] = True
        for nc, nv in edge[v]:
            if used[nv]: continue
            if v == nv: continue
            next_list.add((nc+c, nv, v))
    now_list = list(next_list)
    next_list = set()

judge = all(d[i] > -1 for i in range(1,N))
if judge:
    print("Yes")
    for i in d[1:]:
        print(i+1)
else:
    print("No")