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: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    before = [float("inf")] * n
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
               if d[j] == d[v] + cost[v][j]:
                 before[j] = v + 1
    return d, before

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    cost[x - 1][y - 1] = 1
    cost[y - 1][x - 1] = 1
#print(dijkstra(0,n,w,cost))
ans, ans2 = dijkstra(0,n,w,cost)

if "inf" in ans:
  print("No")
else:
  print("Yes")
  for i in range(1, n):
    print(ans2[i])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import deque
    n, m = map(int, input().split())
    michi=s = [[0 for i in range(n)] for j in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        michi[a-1][b-1]=1
        michi[b - 1][a - 1] = 1
    heya=[-1]*n

    def f():
        check=0
        que = deque([])
        que.append(0)
        while que:
            if check==n:
                break
            else:
                p=que.popleft()
                for i in range(n):
                    if michi[p][i]==1 and heya[i]==-1:
                        heya[i]=p+1
                        check+=1
                        que.append(i)
        return

    f()
    print("Yes")
    for i in heya[1:]:
        print(i)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    x-=1
    y-=1
    cost[x][y] = 1
    cost[y][x] = 1
sp = [0 for _ in range(n-1)]

for i in range(1,n):
    sp[i-1] = dijkstra_back(0,i,n,w,cost)

sp.sort()
#print(*sp)
sg = [-1 for _ in range(n)]
for l in sp:
    for j in range(len(l)):
        x = l[j]
        if j != 0:
            #print(l,x)
            if sg[x] == -1:
                sg[x] = l[j-1]
            elif sg[x] !=  l[j-1]:
                print('No')
                exit()

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

Submission status: Time Limit Exceeded

Solution code:
import math

N, M = map(int, input().split())
route = [[] for _ in range(N)]
mark = [(None, math.inf) for _ in range(N)]
mark[0] = (-1, 0)

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

while True:
    updated = False
    for i in range(N):
        for to in route[i]:
            if mark[to][1] > mark[i][1] + 1:
                mark[to] = (i, mark[i][1] + 1)
                updated = True
    if not updated:
        break

if any(map(lambda x: x[0] is None, mark)):
    print("No")
else:
    print("Yes")
    [print(m[0] + 1) for m in mark[1:]]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = list(map(int, input().split()))
ab = deque([])
for _ in range(M):
  A= list(map(int, input().split()))
  ab.append(A)

ans = [0]*(N+1)
done = [0]*(N+1)
done[0]=1
done[1]=1

stack = deque([1])

while stack:
  x = stack.pop()
  temp = deque([])
  for i in range(len(ab)):
    c = ab.pop()
    if x in c:
      if c[0] == x:
        if done[c[1]] == 0:
          done[c[1]]+=1
          stack.appendleft(c[1])
          ans[c[1]] = x
      else:
        if done[c[0]] == 0:
          done[c[0]] +=1
          stack.appendleft(c[0])
          ans[c[0]] = x
    else:
      temp.append(c)  
  ab = temp

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
import sys


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


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v]:
        if nv in visited:
            continue
        if tokens[nv] < 0:
            tokens[nv] = v
        q.append(nv)
if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    [print(t + 1) for t in tokens[1:]]

Submission status: Time Limit Exceeded

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

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)

# 部屋1から出発して、
ans = [0]*(n+1)
visited = [1]
que = deque([[1, 1]])  # 今の場所、前の場所
# que_items = [1]
now = 1
prev = 1
# BFS
while (len(visited) != n) and len(que) > 0:
    now, prev = que.popleft()
    # print('pop', now)
    for can_go in path[now]:
        if(not (can_go in visited)):
            # print('push', can_go)
            que.append([can_go, now])
    if (now in visited):
        continue
    ans[now] = prev
    visited.append(now)

if 0 in ans[2:]:
    print('No')
else:
    print('Yes')
    for _ans in ans[2:]:
        print(_ans)

Submission status: Time Limit Exceeded

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

import sys

input = sys.stdin.readline
R = [[]]*n
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0
Done = [-1]*n
Done[0] = 1
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a] = R[a] + [b]
  R[b] = R[b] + [a]
  
#print(R)

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if to == Sin[cur] -1:
      continue
    if Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      Done[to] = 1
      d.append(to)

print('Yes')
for i in range(1,n):
  print(Sin[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class Room:
    def __init__(self, prev=-1, dist=1 << 64):
        self.prev = prev
        self.dist = dist


n, m = map(int, input().split())
passages = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    passages[a].add(b)
    passages[b].add(a)

cave = [Room() for _ in range(n)]
cave[0].dist = 0

opening = deque({0})
while opening:
    curr_room = opening.pop()
    next_dist = cave[curr_room].dist + 1
    for next_room in passages[curr_room]:
        if next_dist < cave[next_room].dist:
            cave[next_room].prev = curr_room
            cave[next_room].dist = next_dist
            opening.append(next_room)

guide_points = [cave[i].prev + 1 for i in range(1, n)]

print('Yes')
print('\n'.join(map(str, guide_points)))

Submission status: Time Limit Exceeded

Solution code:
# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
import networkx as nx
G = nx.Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
MOD = 10**9 + 7
N,M = map(int,input().split())

G.add_nodes_from(list(range(1,N+1)))
for _ in range(M):
    A,B = map(int,input().split())
    G.add_edge(A, B)

shortestPath = nx.shortest_path(G, target=1)
ans = ["Yes"]
for i in range(2,N+1):
    if not i in shortestPath:
        print("No")
        exit()
    ans.append(shortestPath[i][1])

print(*ans,sep="\n")
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Time Limit Exceeded

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
def f(pnode, cur_node):
    michi[cur_node] = pnode
    ret = set([(cur_node, child_node) for child_node in graph[cur_node] if child_node != pnode])
    return ret

uses[1] = True
pnode = -1
cur_node = 1
cur_nodes= set([(cur_node, child_node) for child_node in graph[cur_node] if child_node != pnode])
depth = 1
while True:
    next_nodes = set([])
    done = False
    for pnode, cur_node in cur_nodes:
        if not uses[cur_node]:
            ret = f(pnode, cur_node)
            next_nodes = next_nodes + ret
            #next_nodes = next_nodes | ret
            uses[cur_node] = True
            done = True

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
flag = True
d = {}

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

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

if M < N-1:
    flag = False

que = [1]
checked = set()
ans = {1:-1}
if flag:
    while que:
        if len(ans) == N:
            break
        now = que.pop(0)
        for h in d[now]:
            if not h in ans:
                ans[h] = now
                que.append(h)
    
if len(ans) == N:
    print('Yes')
    for i in range(N-1):
        print(ans[i+2]) 
else:
    print('No')

Submission status: Time Limit Exceeded

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=[]
d = deque()
ans=[-1]*N
now=0
d.append(0)
while d:
  c=d.popleft()
  visited.append(c)
  for e in B[c]:
    if e in visited:
      continue
    if e in d:
      continue
    
    d.append(e)
    ans[e]=c
    
if ans.count(-1)!=1:
  print("No")
else:
  print("Yes")
  for i in range(1,N):
    print(ans[i]+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


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

ll = [[0 for _ in range(N)] for _ in range(N)]
for path in paths:
    u, v = path
    ll[v - 1][u - 1] = 1
    ll[u - 1][v - 1] = 1

csr = csr_matrix(ll)

d, p = shortest_path(csr, indices=0, return_predecessors=True, unweighted=True, directed=False)
if np.inf in d:
    print("No")
else:
    print("Yes")
    for i in p[1:]:
        print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque
N,M=map(int,input().split())
G=[[]for _ in range(N)]

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

dist=[10**9 for _ in range(N)]
chk=[0 for _ in range(N)]
dist[0]=0
prev=[-1 for _ in range(N)]


que=deque()
que.append((0,-1))

while(len(que)):
    v,p=que.popleft()
    if p==-1:
        pass
    else:
        val=dist[p]+1
        if val<dist[v]:
            dist[v]=val
            prev[v]=p
    chk[v]=1
    for tmp in G[v]:
        if tmp==p:
            continue
        if chk[tmp]==1:
            continue
        que.append((tmp,v))

print("Yes")
#print(dist)
for i in range(N):
    if i==0:
        continue
    print(prev[i]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

answer = [sys.maxsize for _ in range(N-1)]
distance = [sys.maxsize for _ in range(N)]
distance[0] = 0
q = deque([1])

while len(q) > 0:
  current = q.popleft()
  for A, B in AB:
    nextroom = 0
    if A == current:
        nextroom = B
    elif B == current:
        nextroom = A
    else:
        continue
    if distance[current-1] + 1 < distance[nextroom-1]:
        q.append(nextroom)
        distance[nextroom-1] = distance[current-1] + 1
        answer[nextroom-2] = current
    else:
        pass
if sys.maxsize in answer:
    print('No')
    exit()
print('Yes')
for a in answer:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, raw_input().split())
paths = {}
for m in range(M):
	path = map(int, raw_input().split())
	a_p = paths.get(path[0],[])
	b_p = paths.get(path[1],[])
	a_p.append(path[1])
	b_p.append(path[0])
	paths[path[0]] = a_p
	paths[path[1]] = b_p

visited = [False] * (N+1)

visited[0] = True
to_visit = [1]
signposts = [None] * (N+1)
while len(to_visit) > 0:
	curr = to_visit.pop(0)
	if visited[curr]:
		continue
	else:
		path = paths[curr]
		for p in path:
			if signposts[p] == None:
				signposts[p] = curr
				to_visit.append(p)
		visited[curr] = True
all_visited = all(visited)

if all_visited:
	print 'Yes'
	for s in range(2,len(signposts)):
		print signposts[s]
else:
	print 'No'

Submission status: Time Limit Exceeded

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 = [[0] * (N+1) for _ in range(N+1)]
for a,b in AB:
    neighbor[a][b] = 1
    neighbor[b][a] = 1

que = deque([1])
while len(que) > 0:
    s = que.popleft()
    for i in range(len(neighbor[s])):
        if neighbor[s][i] == 1 and 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: Time Limit Exceeded

Solution code:
import queue
n,m = map(int,input().split())
graph = [[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
ans = [0]* n
flag = [0]*n
q = queue.deque()
q.append(1)
while q:
    tmp = q.popleft()
    flag[tmp-1] = 1
    for i in range(len(graph[tmp-1])):
        if graph[tmp-1][i] == 1:
            if flag[i] == 0:
                q.append(i+1)
                if ans[i] == 0:
                    ans[i] = tmp
if sum(flag) == n:
    print('Yes')
    for i in range(1,n):
        print(ans[i])
        
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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 = [[0, 0]]
while len(node) > 0:
    v = node.pop(0)
    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: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
q = deque()
keys = [0] * n
dic = {i: [] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    dic[a - 1].append(b - 1)
    dic[b - 1].append(a - 1)

for i in dic[0]:
    q.append(i)
    keys[i] = 1
while len(q) > 0:
    next = q.popleft()
    for i in dic[next]:
        if keys[i]:
            continue
        if i not in q:
            q.append(i)
            keys[i] = next + 1
if 0 in keys[1:]:
    print('No')
else:
    print('Yes')
    for i in keys[1:]:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import collections
    n, m = map(int, input().split())
    hw = [[0]*(n+1) for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        hw[a][b] = 1
        hw[b][a] = 1
    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] == 1:
                if arr[i] == -1:
                    arr[i] = a
                    que.append(i)
    if 0 in arr[2:]:
        print("No")
    else:
        print("Yes")
        for i in range(2, len(arr)):
            print(arr[i])

resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math

tmp = input().split()
n,m = list(map(lambda a: int(a), tmp))

#k = int(input())
#s = input()


room=[]
distance=[]
room.append(0)
distance.append(0)
for i in range(n):
	room.append(-1)
	distance.append(100001)
distance[1]=0

a=[]
b=[]
for i in range(m):
	tmp = input().split()
	tmpa,tmpb = list(map(lambda a: int(a), tmp))
	a.append(tmpa)
	b.append(tmpb)

#print(room)
#print(distance)
#print(a)
#print(b)

for j in range(m):
	for i in range(m):
		if(distance[a[i]]>distance[b[i]]):
			distance[a[i]]=distance[b[i]]+1
			room[a[i]]=b[i]
		elif(distance[a[i]]<distance[b[i]]):
			distance[b[i]]=distance[a[i]]+1
			room[b[i]]=a[i]
	#print(room)
	#print(distance)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split(" "))
load = {}
for _ in range(m):
    a, b = map(int, input().split(" "))
    load[a] = load.get(a, []) + [b]
    load[b] = load.get(b, []) + [a]

queue = deque([1])
visited = [-1] * (n+1)
visited[1] = 1

while len(queue) != 0:
    curr = queue.popleft()
    for _next in load[curr]:
        if visited[_next] == -1:
            visited[_next] = curr
            queue.append(_next)

if not all(map(lambda x: x == -1, visited)):
    print("Yes")
    for i in visited[2:]:
        print(i)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
d = defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)
ans = [(-1, float("inf"))] * N
cnt = 0
stack = [(1, 0)]
while stack:
    val, step = stack.pop()
    next_vals = d[val]
    for nxt in next_vals:
        if ans[nxt - 1][1] > step + 1:
            ans[nxt - 1] = (val, step + 1)
            stack.append((nxt, step + 1))

flag_no = False
for i in range(1, N):
    if ans[i][0] == -1:
        flag_no = True
        break

if flag_no:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i][0])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))


#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node,c):
    
    side_num_arr=list(map(lambda x :len(x),node))
    l=max(side_num_arr)
    #print(l)
    queue=[-1 for _ in range(n)]
    now=0
    queue[now]=s
    ans=[-1 for _ in range(n)]
    ans[0]=[0]
    color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n-1)]
    last_ind=1
    while last_ind<n:
        
        if now>=n:
            return []
        check[queue[now]]=True
        if side_num_arr[queue[now]]<=0:
            now+=1
            continue
        for i in node[queue[now]]:
            edge=i[0]
            
            ind=i[1]
            if side_num_arr[edge]<=0 or check[edge]==True:
                continue
            side_num_arr[edge]-=1
            side_num_arr[queue[now]]-=1
            queue[last_ind]=edge
            last_ind+=1
            check[edge]=True
            
            ans[edge]=queue[now]
            #color[ind]=search_color(queue[now],edge,color_check)
        now+=1
    return ans



n,m=input_list()
node=[[] for _ in range(n)]
for i in range(m):
    u,v=input_list()
    u-=1
    v-=1
    node[u].append([v,i])
    node[v].append([u,i])

#print(np.array(node))
check=[-1 for _ in range(n)]
check[0]=0
ans=bfs(0,n,node,check)
if len(ans)==0:
    print("No")
    exit()

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n, m = map(int, input().split())
    edge = np.array([input().split() for _ in range(m)], dtype=np.int64).T
    a = csr_matrix(([1] * m, (edge - 1)), shape=(n, n))
    s, p = shortest_path(a, return_predecessors=True,
                         indices=0, directed=False, unweighted=True)
    if min(p[1:]) < -1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import defaultdict

if __name__ == '__main__':
    s = input().rstrip().split(' ')
    N, M = int(s[0]), int(s[1])
    room = [(None, None)]*(N+1)
    room[1] = (None, 0)
    room_dict = defaultdict(list)
    for i in range(M):
        s = input().rstrip().split(' ')
        A, B = int(s[0]), int(s[1])
        room_dict[A].append(B)
        room_dict[B].append(A)

    q = queue.Queue()
    memory = set()
    q.put(1)
    
    while not q.empty():
        i = q.get()
        memory.add(i)
        order = room[i][1]
        for adj_i in room_dict[i]:
            if room[adj_i][1] == None or order < room[adj_i][1]:
                room[adj_i] = (i, order + 1)
                q.put(adj_i)

    if len(memory) != N:
        print('No')
    else:
        print('Yes')
        for i in range(2, N+1):
            print(room[i][0])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

n, m = map(int, input().split())
g = Graph()
for i in range(m):
    a, b = map(int, input().split())
    g.add_edge(a-1, b-1, 1)
    g.add_edge(b-1, a-1, 1)

d = Dijkstra(g, 0)
A = []
for i in range(n):
    A.append(d.shortest_distance(i))


if float('inf') in A:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(d.shortest_path(i)[-2] + 1)

Submission status: Time Limit Exceeded

Solution code:
import queue
q = queue.Queue()
n, m = map(int, input().split())
mat = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  mat[a-1].append((a-1,b-1))
  mat[b-1].append((b-1,a-1))

d_list = [(-1,-1)]*n

d_list[0] = (0,0)
while len(mat[0]) > 0:
  q.put(mat[0].pop())

while not q.empty():
  u,v = q.get()

  if d_list[v][1] != -1 and d_list[v][1] <= d_list[u][1]+1:
    pass
  else:
    d_list[v] = (u, d_list[u][1]+1)
    while len(mat[v]) > 0:
      q.put(mat[v].pop())
print("Yes")
for i in range(1,n):
  print(d_list[i][0]+1)

Submission status: Time Limit Exceeded

Solution code:
import collections

INF = float('inf')

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

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

queue = collections.deque()
queue.append((0, 0))
results = [(INF, -1) for i in range(N)]

while queue:
    cost, cur = queue.pop()
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.append((next_cost, next_cur))

del results[0]
# print(results)

is_no = False
for result in results:
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for result in results:
        print(result[1]+1)

Submission status: Time Limit Exceeded

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

import sys

input = sys.stdin.readline
R = [[]]*n
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0
Done = [-1]*n
Done[0] = 1
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a] = R[a] + [b]
  R[b] = R[b] + [a]
  
#print(R)

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if to == Sin[cur] -1:
      continue
    if (Dis[to]>Dis[cur]+1 or Dis[to]<0) and Done[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      Done[to] = 1
      d.append(to)

print('Yes')
for i in range(1,n):
  print(Sin[i])

Submission status: Time Limit Exceeded

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

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

ans=[-1]*n
que = [0]
serched = []
#print(di)

while 1:
    tmp = []
    for i in que:
        for j in di[i]:
            if j in serched:
                continue
            ans[j]=i+1
            serched.append(j)
            tmp.append(j)
    if len(tmp)==0:
        break
    que = tmp[:]
print("Yes")
for i in ans[1:]:
    print(i)