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 bfs(graph, n, start):
    visited = [0] * (n+1)
    visited[start] = 1
    start = min(graph.keys())
    queue = deque([])
    queue.append(start)
    pos = {}
    pos[start] = 0

    while queue:
        u = queue.popleft()
        for v in graph[u].keys():
            if  visited[v]:
                continue
            visited[v] = u
            queue.append(v)

    print('Yes')
    [print(i) for i in visited[2:]]
    return True

def resolve():
    n,m = map(int,input().split())
    graph = {i: {} for i in range(1,n+1)}

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

    bfs(graph, n, 1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    ans = [-1] * (n + 1)
    ans[s] = 0
    q = deque()
    q.append(s)
    while q:
        p = q.popleft()
        for i in G[p]:
            if ans[i] == -1:
                ans[i] = p
                q.append(i)
    return ans

n, m = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
a = bfs(1)
print("Yes")
for i in range(2, n + 1):
    print(a[i])

Submission status: Accepted

Solution code:
import sys
from collections import deque


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, read().split())
    al = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, read().split())
        al[a - 1].append(b - 1)
        al[b - 1].append(a - 1)
    ne = deque([(0, 0)])
    s = set()
    t = [(0, 10**6) for _ in range(n)]
    t[0] = (0, 0)
    while ne:
        p, f = ne.popleft()
        if p in s:
            continue
        s.add(p)
        if t[f][1] + 1 < t[p][1]:
            t[p] = (f, t[f][1] + 1)
        for ni in al[p]:
            ne.append((ni, p))
    print("Yes")
    for ti, _ in t[1:]:
        print(ti + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, sys.stdin.readline().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, **kwargs):
	return np.fromiter(inputs(type, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, **kwargs)
	return data

from collections import deque
import numpy as np

N, M = inputs(int)
rooms_from = [[] for _ in range(N)]
for i in range(M):
	A, B = inputs(int)
	A -= 1
	B -= 1
	rooms_from[A].append(B)
	rooms_from[B].append(A)

INF = N

nexts = deque()
distance = np.full(N, INF, dtype=int)
direction = np.full(N, -1, dtype=int)

nexts.append((0, 0, -1))

while nexts:
	here, d, to = nexts.popleft()
	if distance[here] == INF:
		distance[here] = d
		direction[here] = to
		for room in rooms_from[here]:
			nexts.append((room, d + 1, here))

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

# BFS
dist = [-1] * (N + 1)
dist[1] = 0
ans = [-1] * (N + 1)
q = deque([1])
while q:
    u = q.popleft()
    for v in graph[u]:
        if dist[v] >= 0:
            continue
            
        dist[v] = dist[u] + 1
        ans[v] = u
        q.append(v)

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

Submission status: Accepted

Solution code:
# 木グラフの直径
from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                arrow[child] = v + 1
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

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

graph = [[] for _ in range(n)]
arrow = [0] * n

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))
    
dijkstra(n, graph, 0)

print("Yes")
for a in arrow[1:]:
  print(a)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    root =[[] for _ in range(N+1)]
    for _ in range(M):
        a,b = LI()
        root[a].append(b)
        root[b].append(a)

    node = [INF] * (N+1)
    ans = [-1] * (N+1)

    q = collections.deque()
    node[1] = 0
    q.append((0,1,-1))

    while q:
        d,v,f = q.popleft()
        node[v] = d
        ans[v] = f
        for u in root[v]:
            if node[u] <= d+1: continue
            node[u] = d+1
            q.append((d+1,u,v))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist=[float("inf")]*size_v
  used=[False]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w,i in graph[s]:
    heapq.heappush(hq_edge,(w,v,i))

  while hq_edge:
    min_w,min_v,i=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    prev[min_v]=i
    for v,w,i2 in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,i2))

  return dist

ablist=[]
graph=[[] for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  graph[a].append((b,1,i))
  graph[b].append((a,1,i))
  ablist.append((a,b))
#print(graph)

size_v=N+1
prev=[None]*size_v
dist=dijkstra_heap(1)
#print(dist)
#print(prev)

print("Yes")
for i in range(2,N+1):
  prev_e=ablist[prev[i]]
  if i==prev_e[0]:
    print(prev_e[1])
  else:
    print(prev_e[0])

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
neighbor = [[] for _ in range(n)]

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

minv = [-1] * n
minv[0] = 0
length = [-1] * n
length[0] = 0


def dfs():
    global neighbor, length
    queue = deque([[0, 0]])
    while len(queue) > 0:
        v = queue.popleft()

        for nv in neighbor[v[0]]:
            if length[nv] == -1:
                length[nv] = v[1] + 1
                minv[nv] = v[0] + 1
                queue.append([nv, v[1] + 1])


dfs()

f = True
for i in minv:
    f &= i != -1

if not f:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(minv[i])

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().strip().split())
to = [[] for _ in range(n)]

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

q=deque([0,])
ans=[None]*n
while q:
    cur=q.popleft()
    for nxt in to[cur]:
        if ans[nxt] is not None: # visited
            continue
        ans[nxt]=cur+1
        q.append(nxt)

if None in ans:
    print("No")
else:
    print("Yes")
    print(*ans[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)

infi = 10 ** 20
que = deque([(1, 0, -1)])
par = [-1] * (n + 1)
dist = [infi] * (n + 1)

while que:
    v, d, p = que.popleft()
    if dist[v] <= d:
        continue
    dist[v] = d
    par[v] = p
    for u in graph[v]:
        if par[u] == v:
            continue
        que.append((u, d + 1, v))

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

Submission status: Accepted

Solution code:
N,M = [int(x) for x in input().split()]
from collections import deque
l = [[] for i in range(N+1)]
d = deque()
for i in range(M):
    p,q = [int(x) for x in input().split()]
    l[p].append(q)
    l[q].append(p)
dist = [-1] * (N+1)
dist[1] = 0
d.append(1)
ans = [0]*(N+1)
while d:
    v = d.popleft()
    for i in l[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        ans[i] = v
        d.append(i)
if dist.count(-1) != 1:
    print("No")
else:
    print("Yes")
    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())

path = [[] for i in range(N)]
indicator = [None] * N
indicator[0] = (0, 0)
for i in range(M):
    a, b = map(int, input().split())
    a-=1
    b-=1
    path[a].append(b)
    path[b].append(a)

def solve(N, path, indicator):
    visit = [False]*N
    visit[0] = True
    p = 0
    l = 0
    q = deque()
    q.append((0, 0))

    while q:
        (p, l) = q.popleft()
        for room in path[p]:
            if visit[room]:
                continue
            if indicator[room] is None:
                indicator[room] = (p, l+1)
                q.append((room, l+1))
                visit[room] = True
            elif indicator[room][1] > l+1:
                return []

L = solve(N, path, indicator)
if L == []:
    print("No")
else:
    print("Yes")
    for p, l in indicator[1:]:
        print(p+1)

Submission status: Accepted

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

que = deque([1])
ans = [0 for i in range(N)]
while True:
    cur = que.popleft()
    for item in data[cur-1]:
        if ans[item-1] == 0:
            que.append(item)
            ans[item-1] = cur
    if len(que) == 0: break

if 0 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
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
A=[]
B=[]
road=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  road[a-1].append(b-1)
  road[b-1].append(a-1)
visit=[0]*N

q=deque([0])
ans=[0]*N
visit[0]=1
def bfs(q):
  while(q):
    v=q.popleft()
    #print(v)
    for x in road[v]:
      if(visit[x]==0):
        q.append(x)
        #print(q)
        visit[x]=1
        ans[x]=v+1
        #print(x)
bfs(q)
print("Yes")
for i in range(N-1):
  print(ans[i+1])

Submission status: Accepted

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

from collections import deque
vis=[0]*(1+n)

q=deque([1])
while q:
    now=q.popleft()
    for next in G[now]:
        if vis[next]==0:
            vis[next]=now
            q.append(next)
print('Yes')
for i in range(2,n+1):
    print(vis[i])

Submission status: Accepted

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


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

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

todo = deque([[0, 0]])
seen = [-1] * n
seen[0] = 0
while todo:
    node, parent = todo.popleft()

    for to in edges[node]:
        if seen[to] != -1:
            continue

        todo.append([to, node])
        seen[to] = node

print('Yes')
for parent in seen[1:]:
    print(parent+1)

Submission status: Accepted

Solution code:
import queue
n,m=map(int, input().split())
q = queue.Queue()
edgelist = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    edgelist[a-1].append(b-1)
    edgelist[b-1].append(a-1)
res = [-1]*n
visited = [-1]*n
for v in edgelist[0]:
    q.put([v,0])
res[0]=1
while not q.empty():
    x = q.get()
    #print(x)
    if visited[x[0]]==1:
        continue
    else:
        visited[x[0]]=1
        res[x[0]]=x[1]+1
        for i in edgelist[x[0]]:
            if visited[i]==-1:
                q.put([i, x[0]])
print("Yes")
for i in range(1,n):
    print(res[i])

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m=MI()
tree=[[] for i in range(n)]
for i in range(m):
    a,b=MI()
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
q=deque([0])
ind=[-1 for i in range(n)]
#print(tree)
ind[0]=0
while q:
    u=q.popleft()
    #print(u)
    for j in tree[u]:
        if ind[j]<0:
            ind[j]=u
            q.append(j)
#print(ind)
print("Yes")
for i in range(1,n):
    print(ind[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
mark = [-1] * n
mark[0] = 0
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)

que = deque([0])
while len(que) != 0:
    i = que.popleft()
    for j in graph[i]:
        if mark[j] == -1:
            mark[j] = i + 1
            que.append(j)

if -1 in mark:
    print('No')
else:
    print('Yes')
    for i in mark[1:]:
        print(i)

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)]

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

for i in range(m):
    routes[ab[i][0]-1].append(ab[i][1]-1)
    routes[ab[i][1]-1].append(ab[i][0]-1)

#%%
signs = [-1 for _ in range(n)]
seen = [False for _ in range(n)]
seen[0] = True

todo = deque()
todo.append(0)

while len(todo) > 0:
    looking = todo.popleft()
    for i in range(len(routes[looking])):
        if seen[routes[looking][i]] == False:
            seen[routes[looking][i]] = True
            todo.append(routes[looking][i])
            signs[routes[looking][i]] = looking

print("Yes")
for i in range(n-1):
    print(signs[i+1] + 1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


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

    g[0].append(1)

    ans = [-1] * (N + 1)
    que = deque()
    que.appendleft(0)

    while len(que) > 0:
        parent = que.pop()
        for child in g[parent]:
            if ans[child] == -1:
                ans[child] = parent
                que.appendleft(child)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def bfs(graph, start=0):
    used = [False] * len(graph)
    used[start] = True
    q = [start]

    depth = [-1] * len(graph)
    post = [-1] * len(graph)

    depth[0] = 0

    for v in q:
        for w in graph[v]:
            if depth[w] != -1 and (depth[w] < depth[v] or depth[v] == -1):
                depth[v] = depth[w] + 1
                post[v] = w

            if not used[w]:
                used[w] = True
                q.append(w)

    return post


def main():
    n, m = map(int, input().split())

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

    post = bfs(graph)[1:]

    if -1 in post:
        print("No")
        return

    print("Yes")
    for i in post:
        print(i + 1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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


class Dijkstra(object):
    """ ある特定の点からそのほかの頂点への最小距離を求める
    最短区間を実現するルートについては、prevに格納していく
    """
    def __init__(self, n:int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = {}

    def add_edge(self, v1: int, v2: int, w: float, undirected=False):
        self.adjacency_dict[v1][v2] = w
        if undirected:
            self.adjacency_dict[v2][v1] = w

    def run(self, start: int) -> (list, list):
        """ startから初めてそれ以外のノードへの最短距離をダイクストラ法で求める """
        # sからの距離とその前のノードを管理する
        dist = [float('inf')] * self.n
        prev = [None] * self.n
        heap_q = []

        dist[start] = 0

        # プライオリティキューでstartから各ノードの(最短距離, ノードindex)を管理する
        heappush(heap_q, (0, start))

        while len(heap_q) > 0:
            # 未確定な中から最小のノードを取得し、確定する
            d, l = heappop(heap_q)

            # 最小のノードから直接リンクしているノードについて、距離が縮まるようであれば更新する
            for node in self.adjacency_dict[l].keys():
                new_dist = dist[l] + self.adjacency_dict[l][node]
                if dist[node] > new_dist:
                    dist[node] = new_dist
                    heappush(heap_q, (new_dist, node))
                    prev[node] = l

        return dist, prev


g = Dijkstra(N)
for _ in range(M):
    v1, v2 = map(int, input().split())
    g.add_edge(v1 - 1, v2 - 1, 1, undirected=True)

# print(g.adjacency_dict)

dist, prev = g.run(start=0)
# print(dist)

print('Yes')
for p in prev[1:]:
    print(p+1)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import collections

N, M = rl()
edges = collections.defaultdict(list)
for i in range(M):
	a, b = rl()
	edges[a-1].append(b-1)
	edges[b-1].append(a-1)

queue = collections.deque()
queue.append(0)

visited = {}
while queue:
	n = queue.popleft()
	for e in edges[n]:
		if e in visited: continue
		visited[e] = n
		queue.append(e)

for i in range(N):
	if i not in visited:
		print('No')
		exit()
print('Yes')
for i in range(1,N):
	print(visited[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
rol = [[] for _ in range(N)]
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  rol[a].append(b)
  rol[b].append(a)
  
q = deque()
q.append([0,0,0])
minr = [[10**10,0] for _ in range(N)]

while len(q)>0:
  el = q.popleft()
  room = el[0]
  step = el[1]
  oya = el[2]
  if minr[room][0] <= step:
    continue
  minr[room] = [step,oya]
  for el in rol[room]:
    q.append([el,step+1,room])
  
for i in range(1,N):
  if minr[i] == [10**10,0]:
    print("No")
    exit()
    
print("Yes")
for i in range(1,N):
  print(minr[i][1]+1)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    prev = [-1 for _ in range(N)]
    prev[0] = 0
    que = queue.Queue()
    que.put(0)
    while not que.empty():
        cn = que.get()
        for e in edges[cn]:
            if prev[e] == -1:
                prev[e] = cn
                que.put(e)

    print("Yes")
    for p in prev[1:]:
        print(p + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, e =MAP()  #頂点数、辺数
G = [[]for i in range(n)]
for i in range(e):
    fr, to = MAP()#辺の端点、重み
    G[fr-1].append([1,to -1])
    G[to-1].append([1,fr -1])

def djkstra(s,G):
    visited = [False]*n#すでに計算したかどうか 
    d = [INF]*n#最短距離
    former = [INF]*n#経路の一つ前の頂点を記憶
    que = []
    heapq.heappush(que, (0,s,-1))
    while(len(que)>0):
        vs = heapq.heappop(que)
        distance = vs[0]
        vertex = vs[1]
        f = vs[2]
        if visited[vertex]:
            continue
        d[vertex] = distance
        visited[vertex] = True
        former[vertex] = f
        for Gs in G[vertex]:
            if d[Gs[1]] <= distance+Gs[0]:
                continue
            heapq.heappush(que,(distance+Gs[0], Gs[1], vertex))

    return d,former

d, former = djkstra(0,G)
print('Yes')
for i in range(n-1):
    print(former[i+1]+1)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
G = [[] for i in range(N+1)]
for i in range(M):
  a,b = map(int,input().split())
  G[a].append(b)
  G[b].append(a)

ans = "Yes"
ansl = [0 for i in range(N+1)]
l = deque([1])
seen = [False for i in range(N+1)]
seen[1] = True
while len(l)>0:
  v = l.popleft()
  for i in G[v]:
    if seen[i] == False:
      seen[i] = True
      ansl[i] = v
      l.append(i)
###
if ans == "No":
  print(ans)
else:
  print(ans)
  for i in range(2,N+1):
    print(ansl[i])

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
連結無向グラフ
道標をおいた時に、全ての部屋からの最短路となる必要がある。
"""
n,m = map(int,readline().split())
#隣接リスト
g = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    g[x].append(y)
    g[y].append(x)
ans = [-1]*n

deq = deque([0])
while deq:
    fr = deq.popleft()
    for go in g[fr]:
        if ans[go] == -1:
            ans[go] = fr
            deq.append(go)
        

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

Submission status: Accepted

Solution code:
import queue

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

dic = {}

for ab in AB:
    ab[0]-=1
    ab[1]-=1
    if ab[0] in dic:
        dic[ab[0]].append(ab[1])
    else:
        dic[ab[0]] = [ab[1]]

    if ab[1] in dic:
        dic[ab[1]].append(ab[0])
    else:
        dic[ab[1]] = [ab[0]]

# print(dic)

mm = [-1 for i in range(N)]
mm2 = [-1 for i in range(N)]
q = queue.Queue()
q.put(0)



while not(q.empty()):
    a = q.get()
    
    mm2[a] = 1

    for plc in dic[a]:
        if mm[plc] != -1:
            continue
        
        mm[plc] = a+1
        
        q.put(plc)

print("Yes")

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

Submission status: Accepted

Solution code:
from collections import deque
from typing import List, Union


class Dijkstra:
  """Dijkstra Algorithm returns the shortest path at graph.

  Args:
    edge (List[List[int]]): adjacent list
  """
  def __init__(self, edge):
    self.edge = edge
    n = len(edge)
    self.prev = list(range(n))
    self.dist = [n] * n

  def fit(self):
    self.dist[0] = 0
    queue = deque([0])
    while queue:
      vertex = queue.popleft()
      for destination in self.edge[vertex]:
        tmp = self.dist[vertex] + 1
        if self.dist[destination] > tmp:
          self.dist[destination] = tmp
          self.prev[destination] = vertex
          queue.append(destination)

  def get_path(self, vertex: int) -> List[int]:
    previous = self.prev[vertex]
    path = [vertex]
    while vertex != previous:
      vertex = previous
      previous = self.prev[vertex]
      path.append(vertex)
    return path[::-1]
  

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
dijkstra = Dijkstra(edge)
dijkstra.fit()
print('Yes')
for previous in dijkstra.prev[1:]:
  print(previous + 1)

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

D = [float('inf')] * n
P = [None] * n
D[0] = 0
qt = deque()
qt.append(0)
while qt:
    v = qt.popleft()
    for n_v in adj[v]:
        if D[n_v] > D[v] + 1:
            P[n_v] = v + 1
            D[n_v] = D[v] + 1
            qt.append(n_v)

for i in range(n):
    if D[i] == float('inf'):
        print('No')
        sys.exit(0)
print('Yes')        
print('\n'.join(list(map(str, P[1:]))))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
mark = [-1]*N
INF = float('inf')
dist = [-1] * N

mark[0] = 0
from collections import deque
q = deque()
q.append((0,0))

while q:
    v,pv = q.popleft()
    # print(v,pv)
    if dist[v] == -1: # hajimete
        dist[v] = dist[pv] + 1
        mark[v] = pv
        for nv in G[v]:
            q.append((nv,v))
    # print(dist)
    # print(mark)

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