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:
# 2020/05/17
# AtCoder Beginner Contest 168 - D

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

plist = [[] for k in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    plist[a].append(b)
    plist[b].append(a)

visited = [0] * (n+1)
visited[0] = 10 ** 9

beforeidx = [0] * (n+1)

# BFS
q = list()
q.append(1)

while(len(q) > 0):
    stidx = q.pop(0)
    for j in range(len(plist[stidx])):
        nextidx = plist[stidx][j]
        if visited[nextidx] == 0:
            q.append(nextidx)
            beforeidx[nextidx] = stidx
            visited[nextidx] = 1

if min(visited) > 0:
    print('Yes')
    for i in range(2, n+1):
        print(beforeidx[i])
else:
    print('No')

Submission status: Accepted

Solution code:
#input = raw_input

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

graph = {}
for node in range(1, n+1):
    graph[node] = []

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

#print("graph", graph)

michi = [None] * (n+1)
uses = [False] * (n+1)

def set(x):
    return x

uses[1] = True

cur_node = 1
cur_nodes = {}
child_nodes = graph[cur_node]
for child_node in child_nodes:
    cur_nodes[child_node] = cur_node
depth = 1
while True:
    next_nodes = {}
    done = False
    for cur_node, pnode in cur_nodes.items():
        if not uses[cur_node]:
            michi[cur_node] = pnode
            uses[cur_node] = True
            for child_node in graph[cur_node]:
                if child_node == pnode or uses[child_node]:
                    continue
                next_nodes[child_node] = cur_node
            done = True

    if not done:
        break
    depth += 1
    cur_nodes = next_nodes
    #print("michi", michi[1:])

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  G[a-1].append([b-1,1])
  G[b-1].append([a-1,1])
# print(G)
point=[-1]*n
dist=[-1]*n
from collections import deque
q=deque()
q.append(0)
dist[0]=0
while q:
  cur=q.popleft()
  for nx,nd in G[cur]:
    if dist[nx]!=-1:continue
    dist[nx]=dist[cur]+nd
    point[nx]=cur
    q.append(nx)
# print(dist)
# print(point)
for i in range(1,n):
  if point[i]==-1:
    print("No")
    exit(0)
print("Yes")
for i in range(1,n):
  print(point[i]+1)

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)


def main():
    n,m=map(int,input().split())
    a=[[] for _ in range(n+1)]
    for i in range(m):
        x,y=map(int,input().split())
        a[x].append(y)
        a[y].append(x)
#    print(a)
    moto=[-1 for _ in range(n+1)]
    def bfs(a, visited, s):
        queue = deque([])
        visited[s] = 0
        for i in a[1]:
            queue.append(i)
            visited[i] = visited[1] + 1
            moto[i] = 1
        while queue:
            if len(queue) <= 0:
                return
            now = queue.popleft()

            for i in a[now]:
                if visited[i]<0:
                    visited[i]=visited[now]+1
                    queue.append(i)
                    moto[i]=now
    visited=[-1 for _ in range(n+1)]
    bfs(a,visited,1)
#    print(visited)
    if min(moto[2:])>=0:
        print("Yes")
        for i in range(2,n+1):
            print(moto[i])
    else:
        print("No")


if __name__ == "__main__":

    main()

Submission status: Accepted

Solution code:
from collections import deque

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

route = [[] for _ in range(N)]
used = [False] * N
used[0] = True

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

queue= deque([(route[0],0)])
# print(queue)

def bfs(queue):
    while queue:
        next,before = queue.popleft()
        for i in next:
            if used[i] != False:
                continue
            used[i] = before+1
            queue.append((route[i], i))

bfs(queue)

for i, v in enumerate(used):
    if i == 0:
        print("Yes")
    else:
        print(v)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, M = getNM()
dist = [[] for i in range(N + 1)]
for i in range(M):
    a, b = getNM()
    dist[a].append(b)
    dist[b].append(a)

pos = deque([[1, 0]])
ignore = [-1] * (N + 1)
ans = [-1] * (N + 1)
ignore[1] = 0

while len(pos) > 0:
    u, time = pos.popleft()
    for i in dist[u]:
        if ignore[i] != -1:
            continue
        ignore[i] = time + 1
        ans[i] = u
        pos.append([i, time + 1])
ans.pop(0)
ans.pop(0)
flag = True
for i in ans:
    if i < 0:
        flag = False
if flag:
    print('Yes')
    for i in ans:
        print(i)
else:
    print('No')

Submission status: Accepted

Solution code:
import math


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

    routes = {i:[] for i in range(N)}
    directions = [None for _ in range(N)]
    queue = [0]
    current_time = 1

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

    # print(routes)
    directions[0] = 0
    while len(queue) != 0:
        i = queue.pop(0)
        # print("pop: ", i)
        go = routes[i]
        # print("go:", go)
        for j in go:
            if directions[j] == None:
                # 訪れたことのない
                directions[j] = i
                queue.append(j)
                # print("pushed: ", j)
                # print("queue: ", queue)

    # print(directions)
    if None in directions:
        print("No")
        return
    else:
        print("Yes")
        for i in range(1,N):
            print(directions[i]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

from collections import deque

def bfs(graph, queue, dist, prev):
    while queue:
        current = queue.popleft()

        for c in graph[current]:
            if dist[c] != -1:
                continue
            dist[c] = dist[current] + 1
            prev[c] = current
            queue.append(c)

queue = deque([1])
dist = [0] + [-1] * n
prev = [0] + [-1] * n
dist[1] = 0
prev[1] = 0
bfs(graph, queue, dist, prev)
if -1 in prev:
    print('No')
else:
    print('Yes')
    for p in prev[2:]:
        print(p)

Submission status: Accepted

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

graph = [deque([]) for _ in range(N + 1)]
for _ in range(M):
    u, v = [int(x) for x in input().split()]
    graph[u].append(v)
    graph[v].append(u)  # 無向グラフ


sirube = [-1] * (N + 1)


def bfs(root):
    if root is None:
        return
    sirube[1] = 1
    q = deque()
    q.append(root)
    while q:
        r = q.popleft()
        qq = graph[r]
        while qq:
            n = qq.popleft()
            if sirube[n] == -1:
                sirube[n] = r
                q.append(n)

bfs(1)  # スタート

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

Submission status: Accepted

Solution code:
[N,M]=[int(i)for i in input().split()]
#setの配列を持つ
edge=[set() for _ in range(N+1)]
#print(edge,shortestPath)
for i in range(M):
  [a,b]=[int(i)for i in input().split()]
  #print(a,b)
  edge[a].add(b)
  edge[b].add(a)
#print(edge)

shortestPath=[N+1]*(N+1)
shortestPath[1]=0
nextEdgeKouho=set([1])
#1番目の部屋から最短距離を更新して行く
while(len(nextEdgeKouho)>0):
  nextNextEdgeKouho = set([])
  for start in nextEdgeKouho:
    tmpshortestpath=shortestPath[start]
    for end in edge[start]:
      if shortestPath[end] == N+1:
        shortestPath[end] = start
        nextNextEdgeKouho.add(end)
  #print(nextNextEdgeKouho)
  nextEdgeKouho=nextNextEdgeKouho
#print()
#print(shortestPath[2:])
if N + 1 in shortestPath[1:]:
  print("No")
else:
  print("Yes")
  [print(i) for i in shortestPath[2:]]

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')

n_nodes, m_edges = map(int, input().split())
edges = [[] for _ in range(n_nodes)]
for _ in range(m_edges):
    u, v = map(int, input().split())
    edges[u - 1].append([v - 1, 1])
    edges[v - 1].append([u - 1, 1])
# pprint(edges)

parents = [-1] * n_nodes


def dijkstra(n_nodes, edges, start):
    que = deque()
    dist = [INF] * n_nodes
    dist[start] = 0
    que.append([start, 0])
    while len(que) > 0:
        v, v_cost = que.popleft()
        if dist[v] < v_cost:
            continue
        for u, u_cost in edges[v]:
            if v_cost + u_cost < dist[u]:
                dist[u] = v_cost + u_cost
                parents[u] = v
                que.append([u, dist[u]])
    return dist


start = 0
dist = dijkstra(n_nodes, edges, start)
# print(dist)
# print(parents)

print('Yes')
for i in range(1, n_nodes):
    print(parents[i] + 1)

Submission status: Accepted

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

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

from collections import deque

s = [0 for _ in range(n)]
seen = [False for _ in range(n)]
seen[0] = True
queue = deque([1])
while queue:
    now = queue.popleft()
    for i in g[now-1]:
      if(not seen[i-1]):
        seen[i-1] = True
        s[i-1] = now
        queue.append(i)
s = s[1:]
if(0 in s):
  print("No")
else:
  print("Yes")
  for s_i in s:
    print(s_i)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
from collections import defaultdict
for i in range(M):
    a.append(list(map(int,input().split())))
dic = defaultdict(list)
res = {}
res_set =set()
res_set.add(1)
for i in range(M):
    dic[a[i][0]].append(a[i][1])
    dic[a[i][1]].append(a[i][0])
queue = [1]
while queue:
    tmp = queue.pop(0)
    for i in range(len(dic[tmp])):
        if dic[tmp][i] not in res_set:
            res_set.add(dic[tmp][i])
            queue.append(dic[tmp][i])
            res[dic[tmp][i]] = tmp
if len(res_set) < N:
    print("No")
else:
    print("Yes")
    for i in range(2, N + 1):
        print(res[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)]

"""
グラフの最短経路問題
１からたどる
最短経路の時，たどる前にいた点を答えとして収納すれば良い
"""
ans = [0] * (N + 1)
neighbor = [[] for _ in range(N+1)]

for a,b in AB:
    neighbor[a].append(b)
    neighbor[b].append(a)

que = deque([1])
while len(que) > 0:
    s = que.popleft()
    
    for i in neighbor[s]:
        if ans[i] == 0:
            ans[i] = s
            que.append(i)

if 0 not in ans[2:]:
    print("Yes")
else:
    print("No")
    exit()

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

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
a_list=[]
for i in range(M):
    a_list.append(list(map(int,input().split())))
V_list=[[] for i in range(N)]

for item in a_list :
    V_list[item[0]-1].append(item[1])
    V_list[item[1] - 1].append(item[0])

from collections import deque
s_list=[0]*N
current_V=deque()
current_V.append(1)

while (current_V!=deque([])) :
    a=current_V.popleft()
    current_list=V_list[a-1]
    for item in current_list :
        if s_list[item-1]==0 :
            current_V.append(item)
            s_list[item-1] =a
print('Yes')
for item in s_list[1:] :
    print(item)

Submission status: Accepted

Solution code:
import queue

def func():
    n, m = map(int, input().split())
    m_list = [[] for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        m_list[a-1].append(b-1)
        m_list[b-1].append(a-1)
    q = queue.Queue()
    q.put(0)
    ans = [-1 for i in range(n)]
    ans[0] = -2
    while not q.empty():
        before_room = q.get()
        for i in m_list[before_room]:
            if ans[i] != -1:
                continue
            ans[i] = before_room
            q.put(i)
    for i in ans:
        if i == -1:
            print('No')
            return
    print ('Yes')
    for i in ans:
        if i == -2:
            continue
        print (i+1)

if __name__ == '__main__':
    func()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
visited = [-1 for _ in range(n)]
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)
pos = 0
que = deque([])
if g[0]:
    visited[0] = 0
    for nx in g[0]:
        que.append((nx, 0))
while que:
    to, now = que.popleft()
    if visited[to] != -1:
        continue
    else:
        visited[to] = now
        for nx in g[to]:
            que.append((nx, to))
visited = visited[1:]
if -1 in visited:
    print('No')
else:
    print('Yes')
    for k in visited:
        print(k+1)

Submission status: Accepted

Solution code:
def task(n, m, a, b):
    graph = []
    for i in range(0, n + 1):
        graph.append(set())

    for i in range(0, m):
        graph[a[i]].add(b[i])
        graph[b[i]].add(a[i])
    # print(graph)

    stack = [1]
    ans = 0
    traversed = {}
    traversed[1] = True

    while len(stack):
        nxtstack = set()
        ans += 1
        while len(stack):
            nxt = stack.pop()
            for value in graph[nxt]:
                if not value in traversed:
                    nxtstack.add(value)
                    traversed[value] = nxt
        stack = nxtstack

    for i in range(1, n + 1):
        if not i in traversed:
            print("No")
            return

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


n, m = map(int, input().split())
a = []
b = []
for i in range(0, m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
task(n, m, a, b)

Submission status: Accepted

Solution code:
# N = int(input())

import numpy as np

N,M = list(map(int, input().split()))
paths = []
connection_dic = {}

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

for i in range(M):
    A,B = list(map(int, input().split()))
    connection_dic[A].add(B)
    connection_dic[B].add(A)

# print(connection_dic)

ans_list = np.zeros(N-1, dtype = np.int)

current_distance = 0

parents = set([1])
next_parents = set()

while len(parents) > 0:
    # print()
    # print(parents)
    
    current_distance += 1
    while len(parents) > 0:
        parent = parents.pop()
        for node in connection_dic[parent]:
            if node >= 2 and ans_list[node-2] == 0:
                ans_list[node-2] = parent
                next_parents.add(node)
    parents = next_parents
    next_parents = set()
    # print(ans_list)

for ans in ans_list:
    if ans == 0:
        print("No")
        exit()

print("Yes")
for ans in ans_list:
    print(int(ans))

Submission status: Accepted

Solution code:
import sys
import  math
from heapq import *
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

    
N,M=nm()
INF=10**18
def bfs(start,edge):
    d=[INF]*(N+1)
    ans=[0]*(N+1)
    d[start]=0
    q=[(0,start)]
    while(len(q)!=0):
        ci,i=heappop(q)
        for j in edge[i]:
            if(d[j]>d[i]+1):
                d[j]=d[i]+1
                heappush(q,(d[j],j))
                ans[j]=i

    return ans




edge=[[]for _ in range(N+1)]
for i in range(M):
    A,B=nm()
    edge[A].append(B)
    edge[B].append(A)

ans=bfs(1,edge)


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

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

Submission status: Accepted

Solution code:
import collections as c
class graph:
    def __init__(self, n):
        self.n = n
        self.node = [[] for _ in range(n)]
        self.unexplored = [True] * n
        self.landmark = [-1] * (n-1)

    def unit(self, a, b):
        self.node[a].append(b)
        self.node[b].append(a)
    
    def bfs(self):
        queue = c.deque([self.node[0]])
        land = c.deque([0])
        self.unexplored[0] = False
        while queue:
            v = queue.popleft()
            l = land.popleft()
            for d in v:
                if self.unexplored[d]:
                    self.landmark[d-1] = l+1
                    queue.append(self.node[d])
                    land.append(d)
                    self.unexplored[d] = False
    
    def get_land(self):
        return self.landmark

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

g.bfs()
land = g.get_land()
if -1 in land:
    print('No')
else:
    print('Yes')
    for x in land:
        print(x)

Submission status: Accepted

Solution code:
from collections import deque

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

#print(L)

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

#print(L)
d=[float('inf') for i in range(n)]
m=[0 for i in range(n)]

def bfs():

    que=deque([])
    que.append(0)
    d[0]=0
    
    while que:
        p=que.popleft()
        for np in L[p]:
            if d[np]==float('inf'):
                que.append(np)
                d[np]=d[p]+1
                m[np]=p+1

bfs()
if sum(d)==float('inf'):
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(m[i])

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}

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

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

dist = [10**15 for _ in range(N)]
dist[0] = 0

queue = deque([1])
visited = [False for _ in range(N)]

while queue:
    v = queue.popleft()
    if(visited[v-1]):
        continue
    visited[v-1] = True
    for value in graph[v]:
        if(visited[value-1]):
            continue
        if(dist[value-1] > dist[v-1]+1):
            dist[value-1] = dist[v-1]+1
            num[value-1] = v
        queue.append(value)

if(0 not in num):
    print("Yes")
    for i in range(1, len(num)):
        print(num[i])
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

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

res = [-1]*N
res[0] = N
d = deque()
d.append(0)

while True:
    now = d.popleft()
    
    for n in miti[now]:
        if not res[n] < 0:
            continue
        res[n] = now

        d.append(n)

    if not len(d):
        break

if -1 in res:
    print("No")
else:
    print("Yes")
    print("\n".join(str(r+1) for r in res[1:]))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
A = []
B = []
for i in range(M):
  a, b = map(int,input().split())
  A.append(a)
  B.append(b)
  
link_dic = {}
for i in range(M):
  if A[i] not in link_dic.keys():
  	link_dic[A[i]] = [B[i]]
  else:
  	link_dic[A[i]].append(B[i])
  if B[i] not in link_dic.keys():
  	link_dic[B[i]] = [A[i]]
  else:
  	link_dic[B[i]].append(A[i])

sign = [0] * N
j = 1
current_room = [1]

def search_room(l):
  global current_room
  did = 0
  next_cr = []
  for i in l:
    li = link_dic[i]
    for k in range(len(li)):
      if sign[li[k]-1] == 0:
        sign[li[k]-1] = i
        next_cr.append(li[k])
        did += 1
        
  current_room = list(next_cr)
        
  if did == 0:
  	return 1
  else:
  	return 0
  	
while j > 0:
  result = search_room(current_room)
  if result:
    break

sign_ans = sign[1:N]
if min(sign_ans) == 0:
  print('No')
else:
  print('Yes')
  for i in sign_ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
def D():
    n, m = map(int, input().split())
    G = {}
    for i in range(n+1):
        G[i] = []
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    visited = [False] * (n+1)
    visited[1] = True
    mark = [0] * (n+1)
    dq = deque()
    for node in G[1]:
        mark[node] = 1
        visited[node] = True
        dq.append(node)
    while len(dq) != 0:
        node = dq.popleft()
        for next_node in G[node]:
            if not visited[next_node]:
                mark[next_node] = node
                visited[next_node] = True
                dq.append(next_node)
    print("Yes")
    for i in range(n-1):
        print(mark[i+2])
D()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from heapq import heappop,heappush 

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)

mark=[-1]*(N-1)

inf=float("inf")

di=[inf]*N
di[0]=0
hq=[(0,0)]

while hq:
    t,r=heappop(hq) #time room
    if t>di[r]:
        continue
    for x in graph[r]:
        t_new=t+1
        r_new=x
        if t_new<di[r_new]:
            di[r_new]=t_new
            heappush(hq,(t_new,r_new))
            if mark[r_new-1]==-1:
                mark[r_new-1]=r
            else:
                print("No")
                exit()
    
print("Yes")
for i in mark:
    print(i+1)

Submission status: Accepted

Solution code:
from collections import  deque

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

used = [False for _ in range(N)]
INF = int(1e20)
shirube = [0 for _ in range(N-1)]


def bfs(e):
    d = deque()
    used[e] = True
    d.append(e)
    while len(d) != 0:
        ne = d.pop()
        for elm in graph[ne]:
            if not used[elm]:
                shirube[elm-1] = ne
                used[elm] = True
                d.appendleft(elm)


bfs(0)
if all(used):
    print("Yes")
    for el in shirube:
        print(el+1)
else:
    print("No")

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    next = [[] for i in range(N)]
    for i in range(M):
        temp1,temp2 = map(int,input().split())
        next[temp1-1].append(temp2)
        next[temp2-1].append(temp1)

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

    res = [0 for i in range(N)]
    res[0] = 'No'

    temp = next[0]
    queue = deque(next[0])
    for i in temp:
        res[i-1] = 1
        visited.add(i)

    while queue:
        v = queue.popleft()
        temp = next[v-1]
        for i in temp:
            if i not in visited:
                res[i-1] = v
                queue.append(i)
                visited.add(i)

    # print(visited)
    # print(test)

    if test != visited:
        print(res[0])
    else:
        res[0] = 'Yes'
        for i in range(N):
            print(res[i])



main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
tree=[[] for i in range(N)]
ans=[0]*N
ischecked=[0]*N
ischecked[0]=1
for i in range(M):
    A,B=map(int,input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)
q=[0]
while q:
    now=q.pop(0)
    for i in tree[now]:
        if ischecked[i]==1:
            continue
        ans[i]=now+1
        ischecked[i]=1
        q.append(i)
flag=0
for i in range(1,N):
    if ans[i]==0:
        flag=1
        break
if flag==0:
    print("Yes")
    for i in range(1,N):
        print(ans[i])
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
d = dict()
for m in range(M):
    a, b = map(int, input().split())
    d.setdefault(a-1, []).append(b-1)
    d.setdefault(b-1, []).append(a-1)
n = [-1] * N
n[0] = 0
q = deque()
q.append(0)
if 0 in d:
    while len(q) > 0:
        i = q.popleft()
        for dd in d[i]:
            if n[dd] == -1:
                n[dd] = i
                q.append(dd)
if -1 not in n:
    print('Yes')
    for x in range(1, N):
        print(n[x] + 1)
else:
    print('No')

Submission status: Accepted

Solution code:
import heapq


def qqq(path, par, reached):
    queue = []
    heapq.heappush(queue, 0)
    reached[0] = True

    while queue:
        queue_next = []
        for _ in range(len(queue)):
            p = heapq.heappop(queue)

            for i in path[p]:
                if reached[i] is False:
                    reached[i] = True
                    par[i] = p
                    heapq.heappush(queue_next, i)
        queue = queue_next

        if all(reached):
            break


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

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

    for a, b in AB:
        path[a - 1].append(b - 1)
        path[b - 1].append(a - 1)

    par = [-1 for _ in range(N)]
    reached = [False for _ in range(N)]

    qqq(path, par, reached)

    if all(reached):
        print('Yes')
        for i in par[1:]:
            print(i + 1)
    else:
        print('No')


main()

Submission status: Accepted

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

graph = [[] for _ in range(n)]
for a,b in path:
    graph[a-1].append(b-1); graph[b-1].append(a-1)

parents = [-1]*n
tmparr = []
children = [0]
flags = [True] * n
flags[0] = False

while any(flags):
    while children:
        tmp = children.pop()
        for node in graph[tmp]:
            if flags[node]:
                flags[node] = False
                parents[node] = tmp
                tmparr.append(node)
    children = tmparr[:]
    tmparr = []
    
print("Yes")
for i in parents[1:]:
    print(i+1)

Submission status: Accepted

Solution code:
import numpy as np

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

root = []
for i in range(n):
    root.append(set())

for ab in AB:
    root[ab[0]-1].add(ab[1]-1)
    root[ab[1]-1].add(ab[0]-1)

sign = [0]*n
sign[0]=-1
list = [0]

while True:
    x = list.pop(0)

    for next in root[x]:
        if sign[next]==0:
            sign[next]=x+1
            list.append(next)

    if len(list)==0:
        break

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

Submission status: Accepted

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

table = [-1]*N
queue = deque([1])
table[0] = 0
count = 0
while queue:
    n = queue.popleft()
    for c in path[n-1]:
        if table[c-1] == -1:
            table[c-1] = n
            queue.append(c)
            count += 1
        
if count < N - 1:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(table[i])