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

inf = float('inf')
distance = [[-1, inf] for i in range(n)] #目印、距離
queue = deque([])

distance[0] = [0, 0]
queue.appendleft(0)

while len(queue) > 0:
  v = queue.popleft() 
  for next_v in graph[v]:
    judge = False
    if distance[next_v][0] == -1 or distance[v][1]+1 < distance[next_v][1]:
      distance[next_v] = [v, distance[v][1]+1]
      judge = True
    if judge:    
      queue.append(next_v)

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

Submission status: Accepted

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

for i in range(m):
    ta,tb = map(int,input().split())
    ta-=1
    tb -=1
    l[ta].append(tb)
    l[tb].append(ta)
Q = deque()
Q.append([0,0])
dp = [-1]*n
dp[0] = 0
while Q:
    q,p = Q.popleft()
    # print(q,p)
    # print(l[q])
    for i in l[q]:
        # print(i,dp)
        # print(dp[i])
        if dp[i]==-1:
            dp[i] = q
            Q.append([i,p+1])
if -1 in dp:
    print('No')
else:
    print('Yes')
    for i in dp[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]

Mark = [0 for _ in range(N+1)]
path = {k: [] for k in range(1, N+1)}
for i in range(M):
    A, B = [int(i) for i in input().split()]
    path[A].append(B)
    path[B].append(A)
next = [1]
while True:
    n = next.pop(0)
    for x in path[n]:
        # n -> x
        if Mark[x] == 0:
            Mark[x] = n
            next.append(x)
    if not next: break
if 0 in Mark[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join([str(i) for i in Mark[2:]]))

Submission status: Accepted

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

# AB = []
for i in range(M):
    a, b = map(int, input().split())
    root[a].append(b)
    root[b].append(a)
    # if a > b:
    #     a, b = b, a
    # AB.append((a, b))

# ans = [(float('inf'), 0)] * (N+1)
ans = [10**9] * (N+1)
ans[0] = 0
ans[1] = 0
# ans[0] = (0, 0)
# ans[1] = (0, 0)
# # done = [set() for _ in range(N+1)]

# print(root)
from collections import deque
q = deque([1])

while q:
    p = q.popleft()
    for i in root[p]:
        if ans[i] == 10**9:
            # ans[i] = ans[p]+1
            ans[i] = p
            q.append(i)
            # print(q)
            # print(i, ans)

# print(ans)

if 10**9 in set(ans):
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(ans[i])

Submission status: Accepted

Solution code:
import heapq

inf = 10 ** 9


def dijkstra(a):
    color = ["white" for _ in range(n + 1)]
    D = [inf for _ in range(n + 1)]
    P =[-1 for _ in range(n+1)]

    P[a]=-1
    D[a] = 0
    color[a] = "gray"
    queue = [[0, a]]
    heapq.heapify(queue)

    while len(queue) > 0:
        u = heapq.heappop(queue)[1]
        if color[u] == "black": continue
        color[u] = "black"

        V = [[i, j] for i, j in M[u] if color[j] != "black"]
        if len(V) > 0:
            for i, j in V:
                if D[u] + i < D[j]:
                    D[j] = D[u] + i
                    color[j] = "gray"
                    P[j]=u
                    heapq.heappush(queue, [D[j], j])

    return P,D


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
M=[[] for _ in range(n+1)]
for a,b in AB:
    M[a].append([1,b])
    M[b].append([1,a])
P,D=dijkstra(1)
if inf not in D[1:]:
    print("Yes")
    for i in P[2:]:
        print(i)
else:print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

roots = [0] * N
visited = set([])
table = [[] for i in range(N)]

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

visited.add(0)
que = deque([0])

while que:
    cur = que.popleft()
    for target in table[cur]:
        if target in visited:
            continue
        visited.add(target)
        que.append(target)
        roots[target] = cur

print('Yes')
for r in roots[1:]:
    print(r+1)

Submission status: Accepted

Solution code:
import queue


n, m = map(int, input().split())
to_room = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    to_room[a].append(b)
    to_room[b].append(a)
visited = [False for i in range(n+1)]
visited[0] = True
ans = [0 for i in range(n+1)]

q = queue.Queue()

def putting(t):
    global q
    for i in to_room[t]:
        if visited[i] == False:
            q.put((t, i))
            visited[i] = True

putting(1)
visited[1] == True
while not q.empty():
    prog = q.get()
    ans[prog[1]] = prog[0]
    putting(prog[1])


if all(visited):
    print("Yes")
    for i in range(n+1):
        if not (i == 0 or i == 1):
            print(ans[i])
else:
    print("No")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def bfs(graph, initial):
    n = len(graph) - 1
    dist = [-1] * (n + 1)
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]

        for i, e in enumerate(nxt):
            if visited[e] is False:
                q.append(e)
                dist[e] = edge
                visited[e] = True

    return dist


def main():
    N, M = MI()
    graph = [[] for i in range(N+1)]

    for i in range(M):
        x, y = MI()
        graph[x].append(y)
        graph[y].append(x)

    ret = bfs(graph, 1)

    for i in range(2, len(ret)):
        if ret[i] == -1:
            print('No')
            return

    print('Yes')
    for i in range(2, len(ret)):
        print(ret[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
tree=[[] for _ in range(n+1)]
ans=[0]*n 
for _ in range(m):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
checked=[False]*(n+1)
checked[1]=True
stack=deque([1])
while stack:
    p=stack.popleft()
    for i in tree[p]:
        if checked[i]:
            continue
        ans[i-1]=p
        checked[i]=True
        stack.append(i)

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

Submission status: Accepted

Solution code:
import sys
import heapq
from typing import Callable, List, NoReturn, Set


def dijkstra(n, path) -> List[int]:
    total_cost: List[int] = [10**5] * (n + 1)
    total_cost[1] = 0

    pointers: List[int] = [-1] * (n + 1)
    pointers[1] = 0

    not_checked: Set[int] = set(range(1, n + 1))
    checked: Set[int] = set()
    cur_node: int = 1
    h: List = []

    while not_checked:
        checked.add(cur_node)
        not_checked -= {cur_node}

        for next_node in path[cur_node]:
            if next_node in not_checked:
                heapq.heappush(h, (total_cost[cur_node] + 1, next_node, cur_node))

        if not_checked:
            cost, next_node, prev_node = heapq.heappop(h)  # type: int, int, int

            while next_node in checked:
                cost, next_node, prev_node = heapq.heappop(h)

            cur_node = next_node
            total_cost[cur_node] = cost
            pointers[cur_node] = prev_node

    return pointers


def main() -> NoReturn:
    readline: Callable[[], str] = sys.stdin.readline

    n, m = map(int, readline().rstrip().split())  # type: int, int
    path: List[List[int]] = []
    for _ in range(n + 1):
        path.append([])
    for _ in range(m):
        a, b = map(int, readline().rstrip().split())  # type: int, int
        (path[a]).append(b)
        (path[b]).append(a)

    print("Yes")
    pointers: List[int] = dijkstra(n, path)
    for i in range(2, n + 1):
        print(pointers[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split(' '))
chk = [0 for i in range(N+1)]
chk[0]=chk[1]=1
maze = [[] for i in range(N+1)]
for i in range(M):
    a,b=list(map(int,list(input().split(' '))))
    maze[a].append(b)
    maze[b].append(a)
l = deque([1])
while l:
    n = deque.popleft(l)
    for i in maze[n]:
        if not chk[i]:
            chk[i]=n
            l.append(i)
if 0 in chk:
    print('No')
    exit()
print('Yes')
for i in chk[2:]:
    print(i)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    path_list = [[int(item) for item in input().split()] for _ in range(M)]

    to_list = [[] for _ in range(N+1)]
    from_list = [[] for _ in range(N+1)]
    order_list = [[] for _ in range(N+1)]

    for path in path_list:
        to_list[path[0]] += [path[1]]
        to_list[path[1]] += [path[0]]

    # print(to_list)

    que = collections.deque([1])
    cnt = 0

    while que:
        temp = que.popleft()
        cnt += 1

        order_list[temp] = 1

        if len(to_list[temp])>=1:
            for to in to_list[temp]:
                if from_list[to] == []:
                    from_list[to] = temp
                    que.append(to)

    print('Yes')
    for item in from_list[2:]:
        print(item)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
N, M = [int(x) for x in sys.stdin.readline().split()]
edges = defaultdict(list)
for i in range(M):
    A, B = [int(x) for x in sys.stdin.readline().split()]
    edges[A].append(B)
    edges[B].append(A)

answer = [None] * (N + 1)
visited = [1]
while True:
    new_visited = []
    for v in visited:
        for w in edges[v]:
            if answer[w] == None:
                answer[w] = v
                new_visited.append(w)
    visited = new_visited
    if not visited:
        break

answer = answer[2:]
if None in answer:
    print("No")
else:
    print("Yes")
    for a in answer:
        print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict

n,m=map(int,input().split(' '))
paths=defaultdict(list)
for _ in range(m):
    a,b=map(int,input().split(' '))
    paths[a].append(b)
    paths[b].append(a)

parents=[1]
visited=[0]*(n+1)
visited[1]=1

def children(parents):
    children=[]
    for p in parents:
        for c in paths[p]:
            if visited[c]==0:
                children.append(c)
                visited[c]=p
    return children

while True:
    parents=children(parents)
    if parents==[]:
        break
print('Yes')
for i in range(2,n+1):
    print(visited[i])

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
pathway = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split(" "))
    pathway[A-1].append(B-1)
    pathway[B-1].append(A-1)
visit = [0 for i in range(N)]
guide = [-1 for i in range(N)]
point = [0]
while True:
    next_point = []
    for i in point:
        for j in pathway[i]:
            if visit[j]==0:
                guide[j] = i
                visit[j] = 1
                next_point.append(j)
    point = next_point
    if len(point) == 0:
        break
print("Yes")
for i in range(1,N):
    print(guide[i]+1)

Submission status: Accepted

Solution code:
n,m,*ab=map(int,open(0).read().split())
path={}
for i in range(n):
  path[i]=[]
for i in range(m):
  a,b=ab[i*2]-1,ab[i*2+1]-1
  path[a].append(b)
  path[b].append(a)
direction=[i for i in range(n)]
fin=[False for i in range(n)]
fin[0]=True
i=0
queue=[0]
while i<n:
  i+=1
  queue2=queue.copy()
  queue.clear()
  if len(queue2)==0:
    break
  for j in queue2:
    fin[j]=True
    for k in path[j]:
      if not fin[k]:
        direction[k]=j
        fin[k]=True
        queue.append(k)
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())
AB = [list(map(int, input().split())) for i in range(M)]

graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)
    
r = [-1 for i in range(N+1)] 
Q = deque([1])
r[1] = 0
while Q:
    x = Q.popleft()
    for to in graph[x]:
        if r[to] == -1:
            r[to] = x 
            Q.append(to)

print("Yes")
for i in r[2:]:
    print(i)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

n, m = na()
ab = nan(m)

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

ans = [-1 for _ in range(n)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        p, l = q.popleft()
        if ans[p] != -1:
            continue
        ans[p] = l
        for v in g[p]:
            q.append((v, p))

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, readline().split())
        A -= 1; B -= 1
        graph[A].append(B)
        graph[B].append(A)
    trace = [-1]*N
    trace[0] = 0

    que = deque([0])
    while True:
        fr = que.popleft()
        for to in graph[fr]:
            if trace[to] != -1:
                continue
            trace[to] = fr
            que.append(to)
        if len(que) == 0:
            break

    if -1 in trace:
        print('No')
        return

    print('Yes')
    for t in trace[1:]:
        print(t+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
d=dict()
for i in range(M):
  a,b=map(int,input().split())
  d.setdefault(a,set()).add(b)
  d.setdefault(b,set()).add(a)
s=set()#ラベルを貼った場所に置く
label=dict()
A=deque()
A.append(1)
while A:
  a=A.popleft()
  b=d[a]
  b-=s
  for i in b:
    if i not in label:
      label[i]=a
      A.append(i)
k=deque(sorted(label.keys()))
a=k.popleft()
print("Yes")
for i in k:
  print(label[i])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline().rstrip('\n')

def calc(N, M, G):
    d = {i: [] for i in range(1, N + 1)}
    for a, b in G:
        m = min(a, b)
        n = max(a, b)
        d[m] += [n]
        d[n] += [m]
    s = d[1]
    ans = {i: 1 for i in s}
    ans[1] = 0
    while s:
        new_s = set()
        for t in s:
            for k in d[t]:
                if not k in ans:
                    ans[k] = t
                    new_s.add(k)
        s = new_s
    return 'Yes\n' + '\n'.join([str(ans[i]) for i in range(2, N + 1)])

    

(N, M) = tuple([int(s) for s in input().split()])
G = [tuple([int(s) for s in input().split()]) for _ in range(M)]
print(calc(N, M, G))

Submission status: Accepted

Solution code:
# D - .. (Double Dots)

from collections import deque

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

ans_arr = [-1] * (N)
q = deque()
ans_arr[0] = 0 
q.append(0)

while len(q)>0:
    n = q.popleft()
    for i in tree[n]:
        if ans_arr[i] == -1:
            ans_arr[i] = n+1
            q.append(i)

ans = 'Yes'
for i in ans_arr[1:]:
    if i == -1:
        ans = 'No'
        break

if ans == 'No':
    print(ans)
else:
    print(ans)
    for i in ans_arr[1:]:
        print(i)

Submission status: Accepted

Solution code:
import heapq

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

def getAdjListFromEdgePairs(list_EdgePairs, nodenum):
    #0番目の値→1番目の値という優先順位でソート
    list1 = sorted(list_EdgePairs)
    list_Adjlist = [[] for _ in range(nodenum)] 
    
    for list2 in list1:
        list_Adjlist[list2[0]-1].append(list2[1])
        list_Adjlist[list2[1]-1].append(list2[0])

    return list_Adjlist

adj = getAdjListFromEdgePairs(list_EdgePairs, n)


T = [0 for _ in range(n)]
D = [n for _ in range(n)]
D[0] =0
S = [(0, 1)]
heapq.heapify(S)
check = [False for _ in range(n)]


while len(S) > 0:
    u = heapq.heappop(S)
    if check[u[1]-1] == False:
        check[u[1]-1] == True
        for i in adj[u[1]-1]:
            if D[i-1] > D[u[1]-1] + 1:
                D[i-1] = D[u[1]-1] + 1
                T[i-1] = u[1]
                heapq.heappush(S, (D[i-1], i))

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

Submission status: Accepted

Solution code:
from collections import deque

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

mapping = {}
for n in range(N):
    mapping[n+1] = []

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

dest = {}
distance = {}
for n in range(N):
    distance[n+1] = -1
    dest[n+1] = -1

stack = deque()
stack.append(1)
distance[1] = 0

while len(stack) != 0:
    number = stack.popleft()
    next_distance = distance[number]+1

    for m in mapping[number]:
        if distance[m] >= 0:
            continue
        else:
            dest[m] = number
            distance[m] = next_distance
            stack.append(m)

for n in range(N):
    if distance[n+1] < 0:
        print("No")
        exit()

print("Yes")
for n in range(1, N):
    print(dest[n+1])

Submission status: Accepted

Solution code:
import math

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

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

for i in range(M):
    a, b = map(int, input().split())

    path[a-1] += [b-1]
    path[b-1] += [a-1]

length = [-1]*N
last = [-1]*N

Q = [0]
while Q:
    n = Q.pop(0)
    for x in path[n]:
        if length[x] == -1:
            length[x] = length[n] + 1
            last[x] = n
            Q += [x]
        elif length[x] > (length[n] + 1):
            length[x] = length[n] + 1
            last[x] = n

print("Yes")
print("\n".join([str(n+1) for n in last[1:]]))

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    next_n = [0] * n
    used[s] = False
    edgelist = []
    for e in edge[s]:
        e.append(s)
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        next_n[v] = minedge[2]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1],v])
    return d, next_n

################################
n,w = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    a,b = map(int,input().split())
    edge[b-1].append([1,a-1])
    edge[a-1].append([1,b-1]) 
res_list, next_list = dijkstra_heap(0)
if float('inf') in res_list:
  print("No")
else:
  print("Yes")
  for res in next_list[1:]:
    print(res+1)

Submission status: Accepted

Solution code:
from collections import deque

n, m = [0] * 2
a = []
b = []

def format_input(filename = None):
	global n, m
	global a, b
	if filename == None:
		n, m = list(map(int, input().split()))
		ab = [list(map(int, input().split())) for i in range(m)]
		for i in ab:
			a.append(i[0])
			b.append(i[1])

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 10**5)
		m = rng(1, 2 * 10**5)
		a = [rng(1, n) for i in range(m)]
		b = [rng(1, n) for i in range(m)]
		print(n, m)
		[print(a[i], b[i]) for i in range(m)]

def get_answer():
	answer = 'No'
	parent = [0] * (n+1)
	child = [[] for i in range(n+1)]
	for i in range(m):
		child[a[i]].append(b[i])
		child[b[i]].append(a[i])

	visited = [False] * (n+1)
	q = deque()
	q.append(1)
	visited[1] = True
	while len(q) > 0:
		node = q.popleft()
		for i in child[node]:
			if not visited[i]:
				visited[i] = True
				q.append(i)
				parent[i] = node

	if parent.count(0) == 2:
		answer = 'Yes'

	print(answer)
	if answer == 'Yes':
		for i in range(n-1):
			print(parent[i+2])
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = []
import numpy as np
par = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  par[a-1].append(b-1)
  par[b-1].append(a-1)
d = [-1 for i in range(n)]
d[0] = 0

import queue
q = queue.Queue()
q.put(0)
while not q.empty():
  current = q.get()
  
  for p in par[current]:
    if d[p] == -1:
      q.put(p)
      d[p] = current
if -1 in d:
  print("No")
else:
  print("Yes")
  for p in d[1:]:
    print(p+1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

n,m = map(int, input().split())
path = defaultdict(set)
for _ in range(m):
   a, b = map(int, input().split())
   path[a] |= {b}
   path[b] |= {a}

queue = deque([(1, 0)])

visited = set()
res = {1: 0}
while queue != deque([]):
   pos, depth = queue.popleft()
   for p in path[pos]:
      if p in res:
         continue
      res[p] = pos
      queue.append((p, depth+1))
   
print('Yes')
for k,v in sorted(res.items(), key=lambda x: x[0]):
   if k != 1:
      print(v)

Submission status: Accepted

Solution code:
from collections import deque
class UnionFind:
    def __init__(self, N):
        self.parents = [-1 for i in range(N)]
        self.unit = [0 for i in range(N)]
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if x > y:
            x, y = y, x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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


lists = [False for i in range(N)]
lists[0] = True
a = N - 1
dicts = {i:[] for i in range(N)}
d = deque([0])

for i in range(M):
    tmpa, tmpb = map(lambda x: int(x) - 1, input().split()) 
    dicts[tmpa] += [tmpb]
    dicts[tmpb] += [tmpa]
    uf.union(tmpa, tmpb)

if -uf.parents[0] == N:
    print('Yes')
    while a > 0:
        tmp = d.popleft()
        for i in dicts[tmp]:
            if not lists[i]:
                if tmp != 0:
                    lists[i] = tmp
                else:
                    lists[i] = -1
                d.append(i)
                a -= 1
    
    for i in range(1, N):
        print(lists[i] + 1 if lists[i] != -1 else 1)
else:
    print('No')

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

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

q = deque()
q.append(0)
b = [0] * n
while q:
    r = q.popleft()
    for i in g[r]:
        if b[i] != 0:
            continue
        if i == 0:
            continue
        b[i] = r + 1
        q.append(i)

for i in b[1:]:
    if i == 0:
        print("No")
        exit()
print("Yes")
print(*b[1:], sep="\n")

Submission status: Accepted

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

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

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

res = [0]*(n-1)
used = [False]*n

tank = deque([0])
while tank:
    q = tank.popleft()
    if used[q]:
        continue
    used[q] = True

    for go in edge[q]:
        if go == 0 or res[go-1] != 0:
            continue
        res[go-1] = q+1
        tank.append(go)
print("Yes")
print(*res,sep='\n')

Submission status: Accepted

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

R = [-1 for i in range(n)]
Q = deque([(0, -2)])
while len(Q) > 0:
    t = Q[0][0]
    b = Q[0][1]
    #print(t)
    #print(b)
    Q.popleft()
    if R[t] == -1:
        R[t] = b
        for i in range(len(M[t])):
            if R[M[t][i]] == -1:
                Q.append((M[t][i], t))
            else:
                pass
    else:
        pass
#print(R)

f = 0
for i in range(n):
    if R[i] == -1:
        f = 1
        break  
    else:
        pass

if f == 1:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        print(R[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
road=[[] for _ 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)

def bfs(u):
    queue=deque([u])
    d=[0]*n
    ans=[0]*n
    while queue:
        v=queue.popleft()
        for i in road[v]:
            if d[i]==0 and i!=0:
                d[i]=d[v]+1
                ans[i]=v+1
                queue.append(i)
    return d,ans

def main():
    d,ans=bfs(0)
    flg=1
    for i in range(1,n):
        if d[i]==0:
            flg=0
            break
    if flg==0:
        print("No")
    else:
        print("Yes")
        for i in range(1,n):
            print(ans[i])
if __name__=="__main__":
    main()

Submission status: Accepted

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

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

start_points = [1]
sirushi = {1: 0}

while len(sirushi.keys()) < N:
    next_points = []
    for start_point in start_points:
        for next_point in henn[start_point]:
            if next_point not in sirushi:
                sirushi[next_point] = start_point
                next_points.append(next_point)
    start_points = next_points

print('Yes')
for i in range(2, N+1):
    print(sirushi[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)]
e = [[] for _ in range(N)]
for a, b in AB:
    e[a-1].append(b-1)
    e[b-1].append(a-1)

ans = [-1 for _ in range(N)]
def bfs(root):
    if root is None:
        return 
    q = deque()
    q.append(e[root])
    q.append(root)
    while q:
        r = q.popleft()
        i = q.popleft()
        for n in r:
            if ans[n] == -1:
                ans[n] = i + 1
                q.append(e[n])
                q.append(n)
bfs(0)
is_exit = True
for i in ans:
    if i == -1:
        is_exit = False
        break
if is_exit:
    print("Yes")
    for i in ans[1:]:
        print(i)
else:
    print("No")

Submission status: Accepted

Solution code:
from queue import Queue
n, m = map(int, input().split())
graph = {i:[] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
ans = [None]*n
visited = [False]*n
visited[0] = True
q = Queue()
q.put(0)
while not q.empty():
    root = q.get()
    for r in graph[root]:
        if not visited[r]:
            ans[r] = root
            visited[r] = True
            q.put(r)
print('Yes')
for a in ans[1:]:
    print(a+1)