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:
N,M = map(int,input().split())

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

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

from collections import deque

que = deque([1])

ans = [-1 for i in range(N+1)]
dist = [0 for i in range(N+1)]
ans[1] = 0
dist[1] = 0

while que:
    now = que.popleft()
    for v in node[now]:
        if ans[v] == -1:
            ans[v] = now
            dist[v] = dist[now] + 1
            que.append(v)
print('Yes')
print('\n'.join(map(str,ans[2:])))

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    import math
    n,m = map(int,stdin.readline().rstrip().split())
    way = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,stdin.readline().rstrip().split())
        way[a].append(b)
        way[b].append(a)
    
    mark = [0]*(n+1)
    flag = True
    check = [1]

    while flag:
        flag = False
        check_bf = [i for i in check]
        check = []

        for i in check_bf:
            for j in way[i]:
                if mark[j] == 0:
                    mark[j] = i
                    check.append(j)
                    flag = True
    
    if 0 in mark[2:]:
        print("No")
    else:
        print("Yes")
        for i in mark[2:]:
            print(i)
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect
import queue

class Graph:

    def __init__(self, size):
        # id starts from 0
        self.size = size
        self.vertices = [0] * size # indicate parent
        self.visited = [False] * size
        self.edges = [None] * size
        for i in range(size):
            self.edges[i] = []

    def add_edge(self, frm, to):
        self.edges[frm].append(to)
        self.edges[to].append(frm)


class Solver:

    def __init__(self, graph):
        self.graph = graph
        self.que = queue.Queue() # (to, parent)
        self.set(0, -1)

    def set(self, v, parent):
        self.que.put(v)
        self.graph.visited[v] = True
        self.graph.vertices[v] = parent

    def run(self):
        while not self.que.empty():
            parent = self.que.get()
            for to in self.graph.edges[parent]:
                if self.graph.visited[to]:
                    continue
                self.set(to, parent)
        self.print_ans()

    def print_ans(self):
        #print('self.graph.parent') # debug
        #print(self.graph.vertices) # debug
        print("Yes")
        for parent in self.graph.vertices[1:]:
            print(parent + 1)

if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    graph = Graph(n)
    for _ in range(m):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        graph.add_edge(a, b)
    Solver(graph).run()

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


import heapq
BIGDI = 10**18
# N nodes  M arcs  go from S to T (node# starts from 1)
n,m = inm()
s = 1
dst = [{} for i in range(n+1)]
for i in range(m):
    u,v = inm()
    dst[u][v] = 1
    dst[v][u] = 1

cost = [BIGDI]*(n+1)
q = [(0,s)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v], v))

# cost[t] is the answer
ans = [-1]*(n+1)
for i in range(1,n+1):
    for j in dst[i]:
        if cost[j] == cost[i]+1:
            ans[j] = i
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")

from collections import deque

def solve(n, m, passages):
    neighbors = {}
    for passage in passages:
        if passage[0] not in neighbors:
            neighbors[passage[0]] = []
        if passage[1] not in neighbors:
            neighbors[passage[1]] = []
        neighbors[passage[0]].append(passage[1])
        neighbors[passage[1]].append(passage[0])

    parents = {}
    visited = set([1])
    bfs = deque([1])
    while len(bfs) > 0:
        curr = bfs.popleft()
        for item in neighbors[curr]:
            if item not in visited:
                parents[item] = curr
                bfs.append(item)
                visited.add(item)


    if len(visited) != n:
        return None
    result = []
    for i in range(2, n+1):
        result.append(parents[i])
    return result



if __name__ == "__main__":
    n, m = arr_in()
    passages = mat_in(m)
    result = solve(n, m, passages)
    out("Yes" if result is not None else "No")
    if result is not None:
        for item in result:
            out(item)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = [[] for _ in range(max(N,M)+1)]
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
dist = [-1 for _ in range(N + 1)]
dist[1]= 0
from collections import deque
#print(G)
q = deque()
q.append(1)
while (len(q) > 0):
    v = q.popleft();
    for nv in G[v]:
        #print(nv)
        if dist[nv] != -1: continue
        dist[nv] = v 
        #print(dist[v],"dist")
        q.append(nv)
print("Yes")
for x in range(2,len(dist)):
    print(dist[x])

Submission status: Accepted

Solution code:
import collections

[n,m] = [int(i) for i in input().split()]
def BFS(s,G,num):
    ls = collections.deque()
    check = [0] * num
    marker = [-1] * num
    check[0] = 1
    ls += G[s]
    for i in G[s]:
        marker[i] = s
    while(len(ls)):
        now = ls.popleft()
        if check[now] == 1:
            continue
        else:
            #print(now)
            check[now] = 1
            ls += G[now]
            for i in G[now]:
                if marker[i] == -1:
                    marker[i] = now
    return marker
dic = collections.defaultdict(list)
for i in range(m):
    [a,b] = [int(i)-1 for i in input().split()]
    dic[a].append(b)
    dic[b].append(a)

ans = BFS(0,dic,n)

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

Submission status: Accepted

Solution code:
from collections import deque
def bfs(s):
    visited = [-1 for _ in range(n)]
    visited[0] = 0
    inf = float("inf")
    que = deque()
    que.append(s)
    while que:
        p = que.popleft()
        for i in grid[p]:
            if visited[i]==-1:
                que.append(i)
                visited[i] = p
    return visited

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

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

v=bfs(0)

if - 1 in v:
    print("No")
else:
    print("Yes")
    [print(i+1) for i in v[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())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

prev = [0] * N
se = set([0])
q = deque([0])
while q:
    x = q.popleft()
    for y in graph[x]:
        if y in se:
            continue
        prev[y] = x
        q.append(y)
        se.add(y)
if len(se) == N:
    print('Yes')
    for x in prev[1:]:
        print(x + 1)
else:
    print('No')

Submission status: Accepted

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

# ある部屋につながっている部屋を管理する
Heyas = [[] for _ in range(N)]

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

#print(Heyas)

ans = [None for _ in range(N)]
visited = [False for _ in range(N)]
# 幅優先探索
que = [0]
while len(que) > 0:
    heya_i = que.pop(0)
    neighbors = Heyas[heya_i]
    for nei in neighbors:
        if not visited[nei]:
            ans[nei] = heya_i + 1
            visited[nei] = True
            que.append(nei)

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

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, M = map(int, input().split())
    edge = [[] for i in range(N)]
    for i in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        edge[A].append(B)
        edge[B].append(A)
    cnt = [float('inf')] * N  
    cnt[0] = 0
    Q = deque([0])
    visited = [False] * N
    visited[0] = True
    while Q:
        s = Q.popleft()

        for v in edge[s]:
            if visited[v]:
                continue
            cnt[v] = s + 1
            visited[v] = True
            Q.append(v)

    for i in range(N):
        if cnt[i] == float('inf'):
            print('No')
            exit()
    print('Yes')
    for i in range(1,N):
        print(cnt[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())

L=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    
now=[]
nex=[1]
went={1}
res={i:-1 for i in range(n+1)}
res[1]=1

while len(nex)>0:
    now=nex[:]
    nex=[]
    for x in now:
        for go in L[x]:
            if res[go]==-1:
                res[go]=x
                nex.append(go)
                
                
#print
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())
Gs = [[] for _ in range(N+1)]

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

ms = [0] * (N+1)
def bfs(c):
    queue = deque()
    ns = Gs[c]
    for n in ns:
        queue.append((n, c))
    while queue:
        c, p = queue.popleft()

        if ms[c] != 0:
            continue

        ms[c] = p

        ns = Gs[c]
        for n in ns:
            if n != p:
                queue.append((n, c))

bfs(1)

for m in ms[2:]:
    if m == 0:
        print('No')
        break
else:
    print('Yes')
    for m in ms[2:]:
        print(m)

Submission status: Accepted

Solution code:
from collections import defaultdict


num_room, num_path = map(int, input().split(' '))

paths = defaultdict(set)
for i in range(0, num_path):
    src, dest = map(int, input().split(' '))
    paths[src].add(dest)
    paths[dest].add(src)

rooms = {1}
route = {}

while rooms:
    new_rooms = set()
    for src in rooms:
        dest_set = paths[src]
        for dest in dest_set:
            if dest in route.keys():
                continue
            route[dest] = src
            new_rooms.add(dest)
    rooms = new_rooms

for i in range(2, num_room+1):
    if i not in route.keys():
        print("No")
        exit(0)

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

Submission status: Accepted

Solution code:
# 幅優先で始点をメモ
from collections import deque, defaultdict


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

visited = [False]*N
q = deque([0])  # 始まりのノード
visited[0] = True
ans = defaultdict(int)
while len(q):
    # vは数字, 親のノードのインデックス
    v = q.popleft()
    color = 1

    for e in tree[v]:
        if visited[e]:  # 到達済みなら次のノードへ
            continue
        visited[e] = True
        ans[e] = v
        q.append(e)

if False in visited:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

N,M =map(int,input().split())
A=[0]*M
B=[0]*M
C=[[] for _ in range(N)] #隣接リスト
d=[-1 for _ in range(N)]
for i in range(M):
  A[i],B[i] = map(int,input().split())
  C[A[i]-1].append(B[i]-1)
  C[B[i]-1].append(A[i]-1)
m=[-1]*N #道しるべの番号

def BFS(x):
  v=deque([x])
  d[x]=0

  while len(v)>0:
    s=v.popleft()
    for t in C[s]:
      #print(s,t,d)
      if d[t]==-1:
        d[t]=0
        m[t]=s
        v.append(t)
        #print(v)
  else:
    pass
    #print(m)
  
BFS(0)

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

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
nodes = range(1, n+1)
edges = {i: [] for i in nodes}
for _ in range(m):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

sign = {}
reached = {i: False for i in nodes}
reached[1] = True
queue = deque([1])
while queue:
    v = queue.popleft()
    for w in edges[v]:
        if not reached[w]:
            reached[w] = True
            queue.append(w)
            sign[w] = v

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

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
root = [[] for i in range(N)]
for i in range(M):
    a, b = map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)
ans = [-1 for _ in range(N)]
check = [(-1,0)]#(from , now)
count = 1
while True:
    for _ in range(len(check)):
        From, now = check.pop(0)
        for next in root[now]:
            if next == From:
                continue
            else:
                if ans[next] == -1:
                    ans[next] = now + 1
                    check.append((now,next))
                    count += 1
    if count == N:
        break
print('Yes')
ans.pop(0)
print('\n'.join(list(map(str,ans))))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

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

target = [-1]*n
seen = [False]*n

from collections import deque
que = deque()

que.append(0)
while len(que) > 0:
    current = que.popleft()
    if seen[current]:
        continue
    seen[current] = True
    nodes = graph[current]

    for i in nodes:
        if target[i] == -1:
            target[i] = current + 1
        que.append(i)

target.pop(0)

if -1 in target:
    print('No')
else:
    print('Yes')
    for t in target:
        print(t)

Submission status: Accepted

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

P=[-1 for i in range(N+1)]
P[1]=1
Q=[]
for i in L[1]:
    Q.append([i,1])

for i in range(10**7):
    if i==len(Q):
        break
    q1,q2=Q[i]
    if P[q1]!=(-1):
        continue
    else:
        P[q1]=q2
        for j in L[q1]:
            if P[j]==(-1):
                Q.append([j,q1])
#print(P)
print("Yes")
for i in range(2,len(P)):
    print(P[i])

Submission status: Accepted

Solution code:
import heapq
from collections import deque
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:
                        heapq.heappush(queue,(w,j,k))

        return gb

    def bfs(self,vartex = 0):
        todo = [True]*self.v
        queue = deque([vartex])
        while(len(queue)>0):
            v = queue.popleft
            todo[v] = False
            yield v
            for v_i in self.neighbor[v]:
                if todo[v_i]:
                    queue.append(v_i)

    def dfs(self,vartex = 0):
        seen = [False]*self.v
        def recdfs(v):
            seen[vartex] = True
            for next_v in self.neighbor[vartex]:
                if (seen[next_v]):continue
                recdfs(next_v)
    
        
            
class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False,edge = None, weights = None):
        self.v = v
        self.directed = directed
        self.edge = []
        self.weights = []
        if edge is not None:
            self.addEdges(edge)
        if weights is not None:
            self.addVartex(weights)

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
    
    def addVartex(self,weights):
        if len(weights) != self.v:
            return
        self.weights.extend(weights)

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():
    n,m = tuple([int(t)for t in input().split()])
    edge = []

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

    gb = GraphBuilder(n,edge=edge)
    g = gb.buildGraph()

    queue = deque([0])
    root = [-1]*n
    checked = [False]*n
    determined = [False]*n
    while(len(queue)>0):
        p = queue.popleft()
        if checked[p]:
            continue
        checked[p] = True
        for q in g.neighbor[p]:
            if determined[q]:
                continue 
            root[q] = p+1
            queue.append(q)
            determined[q] = True

    if all(checked):
        print("Yes")
        for i in root[1:]:
            print(i)
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = {i: [] for i in range(N)}
for i in range(M):
  a, b = map(int, input().split())
  D[a-1].append(b-1)
  D[b-1].append(a-1)
R = [-1 for _ in range(N)]
R[0] = 0
p = [0]
pnt = 0
cnt = 1
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    x = D[p[i]][:]
    for k in x:
      if R[k] == -1:
        R[k] = p[i]+1
        cnt += 1
        p.append(k)
  pnt = n
print("Yes")
for i in range(1, N):
    print(R[i])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    n, m = LI()
    G = [[] for _ in range(n)]
    for _ in range(m):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
    q = deque()
    q.append((0, 0))
    michi = [-1 for _ in range(n)]
    while q:
        v, par = q.popleft()
        michi[v] = par
        for next_v in G[v]:
            if michi[next_v] != -1:
                continue
            michi[next_v] = v
            q.append((next_v, v))
    print('Yes')
    for i in range(1, n):
        print(michi[i] + 1)


main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

n, m, *ab = map(int, sys.stdin.read().split())
ab = zip(*[iter(ab)] * 2)
graph = [[] for _ in range(n)]
for a, b in ab:
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)

def main():
    parent = [None] * n 
    parent[0] = 0
    queue = deque([0])
    while queue:
        x = queue.popleft()
        for y in graph[x]:
            if parent[y] is not None: continue 
            parent[y] = x
            queue.append(y)

    if None in parent:
        print('No')
    else:
        print('Yes')
        for i in range(1, n):
            print(parent[i] + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(M)]
   
from collections import deque
import sys
sys.setrecursionlimit(10**7)

D=[[]for i in range(N)]
E=[-1]*N
for a,b in A:
   a-=1
   b-=1
   D[a].append(b)
   D[b].append(a)
#print(D)

def bfs(x):
  q=deque()
  q.append(x)
  
  while len(q):
    x=q.popleft()    
    for i in D[x]:
      nx=i
      if E[nx]==-1:
        E[nx]=x
        q.append(nx)
bfs(0)
print('Yes')
for i in E[1:]:
  print(i+1)

Submission status: Accepted

Solution code:
import random
import math
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
yes = lambda: print("Yes")
no = lambda: print("No")
I = lambda: list(input())
J = lambda x: "".join(x)
II = lambda: int(input())
SI = lambda: input()
#---khan17---template
n,m = MI()
d = {}
for i in range(m):
	a,b = MI()
	if a not in d:
		d[a] = [b]
	else:
		d[a].append(b)
	if b not in d:
		d[b] = [a]
	else:
		d[b].append(a)
q = [1]
mark = [0]*(n+1)
di = [0]*(n+1)
di[1] = 0
mark[1] = 1
way = [0]*(n+1)
while len(q)>0:
	v = q.pop(0)
	for i in range(len(d[v])):
		if mark[d[v][i]] == 0:
			di[d[v][i]] = di[v] + 1
			mark[d[v][i]] = 1
			q.append(d[v][i])
			way[d[v][i]] = v
if 0 in di[2:]:
	print("No")
else:
	print("Yes")
	for i in range(2,n+1):
		print(way[i])

Submission status: Accepted

Solution code:
import sys
import heapq

def main():
    n, m = map(int, input().split())
    graph = {}
    for i in range(n):
        graph[i + 1] = []
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    
    visited = set()
    stack = [1]
    ans = [None] * (n + 1)
    while stack:
        temp = []
        while stack:
            node = stack.pop()
            if node in visited:
                continue
            visited.add(node)
            for i in graph[node]:
                if ans[i] == None:
                    ans[i] = node
                if i not in visited:
                    temp.append(i)
        stack = temp[:]
    if len(visited) != n:
        print("No")
    else:
        print("Yes")
        for i in range(2, n + 1):
            print(ans[i])
    
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
import numpy as np
from heapq import heapify, heappop, heappush
import copy
from collections import deque


def main():
    N, M = map(int, input().split())
    adj_lists = {i: [] for i in range(1, N + 1)}
    for i in range(M):
        a, b = map(int, input().split())
        adj_lists[a].append(b)
        adj_lists[b].append(a)
    alreadys = np.zeros((N + 1, ))
    queue = deque()
    queue.append(1)
    while(len(queue) != 0):
        now = queue.popleft()
        nexts = adj_lists[now]
        for next_ in nexts:
            if alreadys[next_] != 0:
                continue
            alreadys[next_] = now
            queue.append(next_)
    for i in range(2, N+1):
        if alreadys[i] == 0:
            print('No')
            sys.exit()
    
    print('Yes')
    for i in range(2, N + 1):
        print(int(alreadys[i]))





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
G = [[] for i in range(n)] #Noneでなくて[]でも可
for i in range(m):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
oya = [-1]*n
oya[0] = 0
que = deque([0])
while que:
    v = que.popleft()
    for w in G[v]:
        if oya[w] > -1:
            continue
        oya[w] = v
        que.append(w)
if -1 in oya:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        print(oya[i]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# input
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, m = map(int, input().split())
path = [[] for _ in range(n)]
ans = [-1] * (n - 1)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # 0idx に直す
    path[a].append(b)
    path[b].append(a)
# room 0 から見ていく
# i-1== -1 でなければvisited
stack = deque()
stack.append(0)
while len(stack) > 0:
    pos = stack.popleft()
    for next_pos in path[pos]:
        if next_pos == 0:
            continue
        if ans[next_pos - 1] == -1:  # unvisited
            ans[next_pos - 1] = pos + 1
            stack.append(next_pos)  # 0 idx
print("Yes")
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque



import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    q = deque()
    q.append(1)
    d = {}
    d[1] = 0
    prev = {}
    while q:
        u = q.popleft()
        for v in g[u]:
            if v in d:
                continue
            d[v] = d[u] + 1
            prev[v] = u
            q.append(v)
    print('Yes')
    return [prev[i] for i in range(2, N+1)]


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(*slv(N, M, AB), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())

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

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

result=[-1]*n
result[0]=0
from collections import deque
stack=deque([0])
while len(stack)>0:
    key=stack.popleft()
    for item in tree[key]:
        if result[item]==-1:
            result[item]=key+1
            stack.append(item)

if -1 in stack:
    print("No")
    exit()
else:
    print("Yes")   
    for item in result[1:]:
        print(item)