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 q4():
    class Room:
        def __init__(self, i):
            self.id = i
            self.d = -1
            self.next = []
            self.sign = -1

        def add_next(self, n):
            self.next.append(n)

        def print(self, tab=0, printed=[]):
            if self.id in printed:
                return
            printed.append(self.id)
            print("  " * tab + str(self.id) + f"({self.sign})")
            for n in self.next:
                n.print(tab + 1, list(printed))
    
        
    N, M = [int(i) for i in input().split(" ")]
    room_dict = {}

    def get_room(i):
        if i in room_dict:
            return room_dict[i]
        else:
            room = Room(i)
            room_dict[i] = room
            return room

    for i in range(M):
        A, B = [int(i) for i in input().split(" ")]
        get_room(A).add_next(get_room(B))
        get_room(B).add_next(get_room(A))


    d = 0
    sign = -1
    queue = deque([[get_room(1), d, sign]])
    while queue:
        room, d, sign = queue.popleft()
        if room.sign != -1:
            continue
        room.sign = sign
        room.d = d
        for n in room.next:
            queue.append([n, d + 1, room.id])

    print("Yes")
    for i in range(2, N + 1):
        print(get_room(i).sign)

q4()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ans = [0] * N
ans[0] = -1
a = [1]
dis_to_goal = [0] * N
dis_to_goal[0] = 0
dis = 0
mem = set()
while True:
    b = []
    dis += 1
    for k in a:
        if k in mem:
            continue
        mem.add(k)
        for n in d[k]:
            if ans[n - 1] == 0:
                ans[n - 1] = k
                dis_to_goal[n - 1] = dis
                b.append(n)
    if len(mem) == N:
        break
    a = b.copy()

#print(ans)
#print(dis_to_goal)

for i, u in enumerate(ans[1:]):
    if dis_to_goal[i+1] - dis_to_goal[u-1] == 1:
        continue
    else:
        print('No')
        exit()
print('Yes')
for k in ans[1:]:
    print(k)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
nlist = [[] for i in range(N+1)]
# print(nlist)
for m in range(M):
    a, b = map(int,input().split())
    nlist[a].append(b)
    nlist[b].append(a)
    # min_, max_ = min(a,b), max(a,b)
    # nlist[min_].append(max_)
# print(nlist)

# 各部屋への最短経路

def bfs():
    nstep = 1
    queue = [1]
    min_dist = [0]*N
    # print(min_dist)
    while True:
        if len(queue)==0:
            break
        ncurrent = queue[0]
        queue.pop(0)
        # print(ncurrent, min_dist)
        for i in nlist[ncurrent]:
            if min_dist[i-1]!=0:
                continue
            queue.append(i)
            min_dist[i-1] = min_dist[ncurrent-1] + 1
    return min_dist
ret=bfs()

if 0 in ret:
    print("No")
else:
    print("Yes")
    dist2n = {r:i+1 for i, r in enumerate(ret)}
    for i in range(1,len(ret)):
        if ret[i]==1:
            print(1)
        else:
            print(dist2n[ret[i]-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
# aisle_lists = [list(map(int,input().split())) for _ in range(m)]

room_set = set()
aisle_dict = dict()

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

    if a in room_set:
        aisle_dict[a].append(b)
    else:
        room_set.add(a)
        aisle_dict[a] = [b]

    if b in room_set:
        aisle_dict[b].append(a)
    else:
        room_set.add(b)
        aisle_dict[b] = [a]


visit_room = {1}
signpost = dict()
now_rooms= [1]

while len(visit_room) < n:
    tmp_now_rooms = []

    for now_room in now_rooms:
        for connect_room in aisle_dict[now_room]:
            if connect_room not in visit_room:
                signpost[connect_room] = now_room
                tmp_now_rooms.append(connect_room)
                visit_room.add(connect_room)

    now_rooms = tmp_now_rooms

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

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
g = [[int(i) for i in input().split()] for j in range(M)]

G = [[] for i in range(N)]
for i in range(M):
    a, b = g[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

marks = [-1 for i in range(N)]
node = deque([[0, 0]])
while len(node) > 0:
    v = node.popleft()
    if marks[v[0]] == -1:
        marks[v[0]] = v[1]
        for i in G[v[0]]:
            if marks[i] == -1:
                node.append([i, v[0]])

if -1 not in marks:
    print("Yes")
    for i in range(1, N):
        print(marks[i]+1)
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

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

from collections import deque
def bfs(start):
    dist = [INF] * N
    dist[start] = 0
    seen = [0] * N
    shirube = [None] * N
    shirube[0] = 'Yes'
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for next_room in graph[v]:
            if seen[next_room]:
                continue
            if dv + 1 < dist[next_room]:
                dist[next_room] = dv + 1
                shirube[next_room] = v + 1
            seen[next_room] = 1
            q.append(next_room)
    if all(shirube):
        for x in shirube:
            print(x)
    else:
        # print(shirube)
        print('No')
bfs(0)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10


# N個の部屋とM本の通路
N, M = [int(x) for x in stdin.readline().rstrip().split()]

route = [[] for _ in range(N+1)]

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


kyori_to_1 = [INF for _ in range(N+1)]
kyori_to_1[1] = 0

miti = [0 for _ in range(N+1)]
miti[0] = -1
miti[1] = -1

is_visited = [False for _ in range(N+1)]

# 幅優先探索
# 試すべき位置をキューで管理
que = deque([1])

# キューが空じゃなければ
while len(que) != 0:
    now = que.popleft()
    
    if is_visited[now]:
        continue

    is_visited[now] = True

    for place in route[now]:
        que.append(place)

        if kyori_to_1[now]+1 < kyori_to_1[place]:
            kyori_to_1[place] = kyori_to_1[now]+1
            miti[place] = now

if 0 in miti:
    print("No")
else:
    for i in range(1, N+1):
        if i == 1:
            print("Yes")
        else:
            print(miti[i])

Submission status: Accepted

Solution code:
from collections import deque
import sys
if __name__ == "__main__":
    n, m = map(int, input().split())
    distance = [float('inf')] * n
    prev_node = [-1] * n
    visit = [False] * n
    graph = []
    for i in range(n):
        graph.append([])
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    
    que = deque()
    que.appendleft((0, 0))
    distance[0] = 0
    visit[0] = True

    while que:
        now, cost = que.pop()
        for nei in graph[now]:
            if not visit[nei]:
                prev_node[nei] = now
                distance[nei] = cost + 1
                que.appendleft((nei, cost + 1))
                visit[nei] = True

    for i in range(1, n):
        if distance == float('inf'):
            print("No")
            sys.exit(0)
    print("Yes")
    for i in range(1, n):
        print(prev_node[i] + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

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

graph = defaultdict(set)

check = set([i + 1 for i in range(N)])

for a, b in AB:
    graph[a].add(b)
    graph[b].add(a)

    if a in check:
        check.remove(a)
    if b in check:
        check.remove(b)

if len(check) != 0:
    print('No')
    exit()

dq = deque([])
dq.append(1)

# noの扱う
ans = [-1] * (N + 1)

visited = set()
visited.add(1)
while dq:
    node = dq.popleft()

    for c in graph[node]:
        if c in visited:
            continue

        ans[c] = node
        visited.add(c)
        dq.append(c)


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

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)]
r = [[] for _ in range(n)]
v = [0]*n
for ab in AB:
    r[ab[0]-1].append(ab[1])
    r[ab[1]-1].append(ab[0])
ans = [1]*(n-1)
d = deque()
d.append(1)
v[0] = 1
while d:
    p = d.popleft()
    for i in r[p-1]:
        if v[i-1]==0:
            d.append(i)
            ans[i-2] = p
            v[i-1] = 1
print('Yes')
for an in ans:
    print(an)

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(s) for s in input().split()]
edge = [[int(s) - 1 for s in input().split()] for _ in range(M)]
graph = [[] for _ in range(N)]
for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

dq = deque([0])
visited = [False] * N
visited[0] = True
parent = [0]*N
while(dq):
    search_obj = dq.pop()
    for candidate_obj in graph[search_obj]:
        if not visited[candidate_obj]:
            dq.appendleft(candidate_obj)
            parent[candidate_obj] = search_obj
            visited[candidate_obj] = True

total_visited = sum(visited)
if total_visited < N:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(parent[i]+1)

Submission status: Accepted

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc168/abc168_d
import sys
from collections import deque

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    tree = [set() for _ in range(N + 1)]
    sign = [None] * (N + 1)
    cnt = 0
    for _ in range(M):
        A, B = i2nn()
        tree[A].add(B)
        tree[B].add(A)
    que = deque([1])
    while que:
        # print(que)
        seek = que.popleft()
        for n in tree[seek]:
            if sign[n] is not None:
                continue
            cnt += 1
            sign[n] = seek
            tree[n].discard(seek)
            que.append(n)
    if cnt < N - 1:
        print('No')
        return
    print('Yes')
    for s in sign[2:]:
        print(s)
    return

main()

Submission status: Accepted

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

# 1_indexにする
dist = [-1] * (n + 1)
roots = [[] for i in range(n + 1)]

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

ans = [-1] * (n + 1)
ans[1] = 0
dist[1] = 0
q = deque()
q.append(1)

while q:
    now = q.popleft()

    for next_v in roots[now]:
        if not dist[next_v] == -1:
            continue
        dist[next_v] = dist[now] + 1
        ans[next_v] = now
        q.append(next_v)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(u):
    
    q = deque()
    q.append(u)
    while q:
        r = q.popleft()
        for v in R[r]:
            if S[v] == -1:
                S[v] = r
                q.append(v)

S = [-1] * N
S[0] = 0

bfs(0)

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

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    root_dict = dict()
    ans = [0] * N
    remaining_set = {i for i in range(2, N+1, 1)}
    for i in range(1, N+1, 1):
        root_dict[i] = set()
    for i in range(M):
        AB = list(map(int, input().split()))

        root_dict[AB[0]].add(AB[1])
        root_dict[AB[1]].add(AB[0])

    next_nodes = dict()
    next_nodes[1] = root_dict[1].copy()
    
    org_node = 1
    while(next_nodes):
        next_next_nodes = dict()
        if(len(remaining_set) == 0):
            break
        for org_node, nodes in next_nodes.items():
            for node in nodes:

                if(node in remaining_set):
                    ans[node-1] = org_node
                    remaining_set.remove(node)
                    if(node in next_next_nodes):
                        next_next_nodes.clear(node)
                    next_next_nodes_set = root_dict[node].intersection(remaining_set).difference(nodes)
                    if(len(next_next_nodes_set) != 0):
                        if(node in next_next_nodes):
                            next_next_nodes[node] = next_next_nodes[node].union(next_next_nodes_set)
                        else:
                            next_next_nodes[node] = next_next_nodes_set.copy()
                else:
                    continue
        next_nodes = next_next_nodes.copy()
    
    if(len(remaining_set) != 0):
        print("No")
    else:
        for i in range(N):
            if(i==0):
                print("Yes")
            else:
                print(ans[i])
    



main()

Submission status: Accepted

Solution code:
from collections import deque

''' Breadth First Search (BFS) '''
def bfs(x):
    q = deque([x])
    visited[x] = True
    while q:
        x = q.popleft()
        for y in adj[x]:
            if not visited[y]:
                q.append(y)
                visited[y] = True
                parent[y] = x

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
parent = [i for i in range(n + 1)]
visited = [False] * (n + 1)

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

bfs(1)
check = True
if i in range(2, n + 1):
  if parent[i] == i:
    check = False
if check:
  print("Yes")
  for i in range(2, n + 1):
    print(parent[i])
else:
  print("No")

Submission status: Accepted

Solution code:
import collections

n, m = map(int, input().split())
dic = collections.defaultdict(lambda:[])
for _ in range(m):
  a, b = map(int, input().split())
  dic[a].append(b)
  dic[b].append(a)
  
ans = [None] * n
bfs = [(1,dic[1])]
visited = set()
get = 0
while bfs and get < n:
  now, nexts = bfs.pop(0)

  for i in nexts:
    if i in visited:
      continue
    ans[i-1] = now
    get += 1
    bfs.append((i,dic[i]))
    visited.add(i)
      
print('Yes')  
for i in range(1, n):
  print(ans[i])

Submission status: Accepted

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# import numpy as np
# from itertools import permutations
# from itertools import combinations
# from itertools import combinations_with_replacement
import queue
# import heapq

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N, M = map(int, input().split())
    queries = (map(int, input().split()) for _ in range(M))

    tree = [set() for _ in range(N+1)]

    for a, b in queries:
        tree[a].add(b)
        tree[b].add(a)

    nn = 10 ** 9
    signs = [nn for _ in range(N+1)]
    visited = {0}

    que = queue.Queue()

    que.put((0, 1))  # parent, current

    while not que.empty():

        parent, current = que.get()

        if current in visited:
            continue

        visited.add(current)
        signs[current] = parent

        for t in tree[current]:
            if t in visited:
                continue
            else:
                que.put((current, t))

    return signs[2:]


def main():
    ans = solve()
    if 10**9 in ans:
        print('No')
    else:
        print('Yes')
        for a in ans:
            print(a)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
import heapq
# import time

n, m = list(map(int, input().split()))
a = [0] * m
b = [0] * m
path = [[] for i in range(n+1)]

for i in range(m):
    # a[i], b[i] = list(map(int, input().split()))
    a, b = list(map(int, input().split()))
    path[a].append(b)
    path[b].append(a)
# start = time.time()
# 部屋1から出発して、
ans = [0]*(n+1)
visited = []
que = deque([[1, 1]])  # 今の場所、前の場所
que_items = set([1])

# BFS
while len(que) > 0:
    now, prev = que.popleft()
    # print('pop', now)
    for can_go in path[now]:
        if(not (can_go in que_items)):  # ここが遅い
            # print('push', can_go)
            que.append([can_go, now])
            que_items.add(can_go)
    ans[now] = prev
    visited.append(now)
    # print(visited)

if (len(visited) != n):
    print('No')
else:
    print('Yes')
    for _ans in ans[2:]:
        print(_ans)

# print(time.time() - start)

Submission status: Accepted

Solution code:
from collections import deque
    
def bfs(graph,start): #def bfs(graph,start,limit): 
    dist = [-1] * (N)
    ans = [-1] *(N)
    dist[start]= 0
    q = deque([start])
    cnt = 0
    while q:
        x = q.popleft()
        for i in graph[x]:
            #if dist[x] >= limit:
            #    break
            if dist[i] == -1:
                dist[i] = dist[x] + 1
                ans[i] = x+1
                q.append(i)
    return dist, ans

N,M  = map(int,input().split())# 頂点数
X = [[] for i in range(N)] #辺リスト

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

dist,ans = bfs(X,0)
#print(dist,ans)
if -1 in dist:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(ans[i])

Submission status: Accepted

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

from collections import deque

def linput(_t=int):
    return list(map(_t, input().split()))

def gcd(n,m):
    while m: n,m = m, n%m
    return n

def lcm(n,m): return n*m//gcd(n,m)

def main():

    N,M = linput()
    # res = 0
    # print(N)
    mG = [[] for _ in [0,]*(N+1)]

    for _ in [0,]*M:
        a,b = linput()
        mG[a].append(b)
        mG[b].append(a)

    vR = [0,] * (N+1)
    vR[1] = 1

    vQ = deque([])
    vQ.append((mG[1],1))

    while vQ:
        vG, pp = vQ.popleft()
        # print(vG,pp,"vQ_pop")

        for g in vG:
            if vR[g] == 0:
                vR[g] = pp
                vQ.append((mG[g],g))

    print("Yes")
    print(*(r for r in vR[2:]), sep="\n")
    # print(res)
    # print(("No","Yes")[res%2])


main()

Submission status: Accepted

Solution code:
import threading, queue

N, M = map(int, input().split())
AB = [[] * N for _ in range(N)]
m = [0] * (N + 10)
q = queue.Queue()
q.put(0)

for _ in range(M):
  A, B = map(int, input().split())
  AB[A - 1].append(B - 1)
  AB[B - 1].append(A - 1)
  
while not q.empty():
  s = q.qsize()
  for _ in range(s):
    t = q.get()
    for p in AB[t]:
      if m[p] == 0:
        m[p] = t + 1
        q.put(p)

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

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop
N,M = map(int,input().split())
room = [[] for i in range(0,N+1,1)]
mitisirube = [-1]*(N+1)

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

D_INF = 10**10
d = [D_INF]*(N+1)
d[1] = 0
que =[]
heapify(que)
heappush(que,(d[1],1))

while(len(que)):
    time,place = heappop(que)
    if time > d[place]:
        continue
    for i in range(0,len(room[place]),1):
        if d[room[place][i]] > time + 1:
            d[room[place][i]]=time+1
            heappush(que,(time+1,room[place][i]))
            mitisirube[room[place][i]] = place
        
print("Yes")
for i in range(2,N+1,1):
    print(mitisirube[i])

Submission status: Accepted

Solution code:
from collections import deque

[N, M] = [ int(x) for x in input().split() ]

G = dict()
for i in range(1,N+1):
    G[i] = set()

for i in range(M):
    [A,B] = [ int(x) for x in input().split() ]
    G[A].add(B)
    G[B].add(A)

ans = dict()

Q = deque([1])
visited = set()
while Q:
    room = Q.popleft()
    
    if room not in visited:
        visited.add(room)
        
        for r in G[room]:
            if r not in ans:
                ans[r] = room
            Q.append(r)
for i in range(2, N+1):
    if i not in ans:
        print('No')
        exit()

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

Submission status: Accepted

Solution code:
def resolve():
    import collections
    n, m = map(int, input().split())
    hw = [[0] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        hw[a].append(b)
        hw[b].append(a)

    dis = [0] * (n+1)
    arr = [-1] * (n+1)
    que = collections.deque([1])
    while len(que) != 0:
        a = que.popleft()
        test = hw[a]
        for i in range(len(test)):
            if test[i] != 0:
                goal = test[i]
                if arr[goal] == -1:
                    arr[goal] = a
                    que.append(goal)
    if 0 in arr[2:]:
        print("No")
    else:
        print("Yes")
        for i in range(2, len(arr)):
            print(arr[i])
resolve()

Submission status: Accepted

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

for i in range(M):
  a,b=map(int,input().split())
  B[a-1].append(b-1)
  B[b-1].append(a-1)
  
visited=[0]*N
d = deque()
ans=[-1]*N
d.append(0)
visited[0]=1
while d:
  c=d.popleft()
  for e in B[c]:
    if visited[e]:
      continue
      
    d.append(e)
    visited[e]=1
    ans[e]=c
    
print("Yes")
for i in range(1,N):
  print(ans[i]+1)

Submission status: Accepted

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

n, m = [int(x) for x in input().split()] # nは頂点の数、mは辺の数
g = [[] for _ in range(n)] # 隣接リスト

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

from collections import deque

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

# 0からの各頂点の距離
d, p = bfs(0)
if None in d:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(p[i])

Submission status: Accepted

Solution code:
from queue import Queue

n, m = map(int, input().split())
to = {}
for i in range(m):
    a, b = map(int, input().split())
    from_a = to.get(a, set())
    from_a.add(b)
    to[a] = from_a
    from_b = to.get(b, set())
    from_b.add(a)
    to[b] = from_b
ans = [0] * (n + 1)
ans[1] = 1
nx = Queue()
nx.put(1)
while not nx.empty():
    cur = nx.get()
    nxts = to.get(cur, [])
    for nxt in nxts:
        if ans[nxt] != 0:
            continue
        ans[nxt] = cur
        nx.put(nxt)
if 0 in ans[2:]:
    print('No')
else:
    print('Yes')
    [print(i) for i in ans[2:]]

Submission status: Accepted

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

m = [list() for _ in range(N + 1)]
for _ in range(M):
    A, B = list(map(int, input().split()))
    m[A].append(B)
    m[B].append(A)

visited = [N + 100 for _ in range(N + 1)]
step = 0
visited[1] = step
que = [1]

os = [0 for _ in range(N + 1)]

while len(que) > 0:
    step += 1

    q = que.pop(0)

    for t in m[q]:
        if visited[t] == N + 100:
            que.append(t)
        if step <= visited[t]:
            visited[t] = step
            os[t] = q 

for o in os[2:]:
    if o == 0:
        print('No')
        break
else:
    print('Yes')
    for _o in os[2:]:
        print(_o)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

import queue

def main():
    N, M = map(int, input().split())

    connedted_room_list = [ [] for i in range(N)] # ここでNとMを書き間違えていた。
    for i in range(M):
        A, B = map(int, input().split())
        connedted_room_list[A-1].append(B-1)
        connedted_room_list[B-1].append(A-1)

    answer_list = [ -1 for i in range(N)]
    answer_list[0] = 0

    next_rooms_queue = queue.Queue()
    next_rooms_queue.put(0)
    now_room = int()
    while not next_rooms_queue.empty():
        now_room = next_rooms_queue.get()
        for i in connedted_room_list[now_room]:
            if answer_list[i] == -1:
                answer_list[i] = now_room
                next_rooms_queue.put(i)

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

    if is_escapable:
        print("Yes")
        for i in range(1, N):
            print(answer_list[i]+1)
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

def main():
    N, M = tuple(int(c) for c in input().split(' '))
    #A = [None]
    #B = [None]
    R = defaultdict(set)
    for _ in range(M):
        a, b = tuple(int(c) for c in input().split(' '))
        R[a].add(b)
        R[b].add(a)

    D = [0]*(N+1)  #これから決めていく方向
    D[1] = -1
    traced = set()
    traced.add(1)

    #幅優先探索
    q = deque((1, x) for x in R[1])
    #print(q)
    while(True):
        if(len(q) <= 0):
            #print('D:', D)
            #print('done.')
            break
        pos, x = q.popleft()
        if x == 1:
            continue
        if D[x] == 0:
            assert not x in traced
            D[x] = pos
            traced.add(x)
            #print(f'direction: {pos}<-{x}')
            t = [(x, y) for y in R[x]]
            for x, y in t:
                if not y in traced:
                    q.append((x, y))
            #print((pos, x), '->', q)
        elif D[x] == pos:
            assert x in traced
            continue
        else:
            #print(f'already {D[x]}<-{x}, so ignored {pos}<-{x}')
            continue
            #print('No')  #これでいいか？
            #exit()
    print('Yes')
    for i in range(2, len(D)):
        print(D[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

root = [[] for _ in range(N)]
#print(root)
for i in range(M):
    A, B = map(int, input().split())
    root[A-1].insert(len(root[A-1]), B)
    root[B-1].insert(len(root[B-1]), A)
room = [0]*N

q = Queue()
for k in root[0]:
    room[k-1] = 1
    q.put(k)
while not q.empty():
    a = q.get()
    for j in root[a-1]:
        if room[j-1] == 0:
            q.put(j)
            room[j-1] = a
if 0 in room[1:]:
    print("No")
else:
    print("Yes")
    for ans in room[1:]:
        print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

D = {} # 親；子
T = {}
for i in range(1, N+1):
    D[i] = []
    T[i] = 0

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

child = D[1]
parent = [1]


while len(parent) > 0:
    child2 = []
    for p in parent:
        for c in D[p]:
            if T[c] != 0: continue
            T[c] = p
            child2.append(c)
    parent = child2

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

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

Submission status: Accepted

Solution code:
import queue

q = queue.Queue()

N,M = map(int,input().split())
AB = []
dic = {}
for _ in range(M):
    AB = list(map(int,input().split()))
    dic.setdefault(AB[1], []).append(AB[0])
    dic.setdefault(AB[0], []).append(AB[1])

cnt = 1
ans = [0] * N

for i in range(len(dic[1])):
    ans[dic[1][i] - 1] = 1
    q.put(dic[1][i])

while q.empty() == False:
    current_number = q.get()
    for i in range(len(dic[current_number])):
        if ans[dic[current_number][i] - 1] == 0:
            ans[dic[current_number][i] - 1] = current_number
            q.put(dic[current_number][i])

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
marks = {i+1:-1 for i in range(n)}
marks[1] = 0
roots = {i+1:[] for i in range(n)}
count = 0
for i in range(m):
    a,b = map(int,input().split())
    roots[a].append(b)
    roots[b].append(a)

before_room = 1
searchs = [{'root':roots[1], 'mark':1}]
while searchs != []:
    next_search = []
    for search in searchs:
        for root in search['root']:
            new_root = []
            if marks[root] == -1:
                marks[root] = search['mark']
                count += 1
                new_root += roots[root]
            else:
                continue
            next_search.append({'root':roots[root], 'mark':root})
    searchs = next_search[:]

del marks[1]
print('Yes')
for v in marks.values():
    print(v)