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
    prev= [0] * 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):
            if d[j] > d[v]+cost[v][j]:
                prev[j] = v
            d[j] = min(d[j],d[v]+cost[v][j])
    return prev

def main():
    n,w = map(int,input().split()) #n:頂点数　w:辺の数
    checker = [0]
    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()) 
        checker.append(x)
        checker.append(y)
        x -= 1
        y -= 1
        cost[x][y] = 1
        cost[y][x] = 1
    checker = list(set(checker))
    if checker == list(range(n+1)):
        print("Yes")
        for i in dijkstra(0,n,w,cost)[1:]:
            print(i + 1)
    else:
        print("No")
 
 
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().split()]
dict = {}
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    dict.setdefault(a-1,[]).append(b-1)
    dict.setdefault(b-1,[]).append(a-1)
tmp = []
ans = [0]*n
ans2 = [0]
t = 0
while t < n:
  for s in ans2:
    for i in range(1,n):
      if s in dict[i] and ans[i] == 0:
        tmp.append(i)
        ans[i] = s+1
  ans2 = tmp
  t += 1
if ans.count(0) == 1:
  print('Yes')
  for i in range(1,n):
    print(ans[i])
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l2=np.zeros(N-1)
import sys
l_l=[i.rsplit() for i in sys.stdin.readlines()]
l_l = [list(map(int,i)) for i in l_l]
for i in l_l:
   l[i[0]-1].append(i[1])
   l[i[1]-1].append(i[0])
from collections import deque
que=deque([1])
after=deque()
que_append=que.append
after_append=after.append
while que != deque([]):
   X=que.popleft()
   after_append(X)
   for i in l[X-1]:
      if i in after:
         continue
      if i in que:
         continue
      que_append(i)
      np.put(l2,[i-2],X)
if len(after) == N:
   print("Yes")
   for i in l2:
      print(int(i))
else:
   print("No")

Submission status: Time Limit Exceeded

Solution code:
temp = input()
temp = temp.split()
room = int(temp[0])
passage = int(temp[1])
adjlist = {}
visited = [0] * (room + 1) 
finalans = []
finalans.append(0)
findmin1 = {}
for i in range(passage):
    inpu = input()
    inpu = inpu.split()
    firstnode = int(inpu[0])
    secnode = int(inpu[1])
    if firstnode == 1:
        findmin1[secnode] = 1 
    if secnode == 1 :
        findmin1[firstnode] = 1 
    
    if firstnode not in adjlist:
        adjlist[firstnode] = []
    if secnode not in adjlist:
        adjlist[secnode] = []
        
    adjlist[firstnode].append(secnode)
    adjlist[secnode].append(firstnode)

flag = 0 
for i in range(2, room + 1):
    temparr = []
    ans = -1 
    visited = [0] * (room + 1) 
    if i not in adjlist:
        flag = 1 
        break
    templist = adjlist[i]
    if i in findmin1:
        finalans.append(1)
        continue 
    for j in templist:
        visited[j] = 1
        temparr.append((j, j))
    while True:
        if len(temparr) == 0:
            break
        getans = 0 
        newarr = []
        for node in temparr:
            newnode = node[0]
            firstnode = node[1]
            if newnode not in adjlist:
                continue 
            if newnode in findmin1:
                getans = 1 
                ans = firstnode
                break
            for j in adjlist[newnode]:
                if visited[j] == 1 :
                    continue 
                visited[j] = 1 
                newarr.append((j, firstnode))
        
        if getans == 1:
            break
        
        temparr = newarr[::]
    
    if ans == -1:
        flag = 1 
        break
    finalans.append(ans)

if flag == 1:
    print("No")
#print(adjlist)
else:
    print("Yes")
    for i,j in enumerate(finalans):
        if i == 0 :
            continue 
        print(j)
#print(finalans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M = map(int,input().split())
A = []
for m in range(M):
    A.append(list(map(int,list(input().split()))))
A = list(itertools.chain.from_iterable(A))

#
def whereto(x):
    if x%2 == 0:
        return x+1
    else:
        return x-1

Mark = [-1]*(N-1)
Past = [1]
Que = [1]

while len(Past) != N:
    next_road = ([i for i, x in enumerate(A) if x == Que[0]])

    for n in next_road:
        next = A[whereto(n)]
        #print(next)
        if Past.count(next) == 0:
            Past.append(next)
            Que.append(next)
            #print(next-2)
            Mark[next-2]=Que[0]
    Que.pop(0)

print("Yes")
for m in Mark:
    print(m)

Submission status: Time Limit Exceeded

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

def get_route(pathways, routes, nows):
    if len(nows) == 0 or 0 not in routes: return routes
    next_nows = []
    for now in nows:
        for src, dest in filter(lambda x:x[0] == now and routes[x[1]-1] == 0, pathways):
            routes[dest-1] = now
            next_nows.append(dest)
    routes = get_route(pathways, routes, next_nows)
    return routes

def main():
    N, M = map(int, input().split())
    pathways = []
    for _ in range(M):
        A, B = map(int, input().split())
        pathways.append([A, B])
        pathways.append([B, A])
    ans_route = get_route(pathways, [-1] + [0] * (N-1), [1])
    if 0 in ans_route: print("No")
    else:
        print("Yes")
        for x in ans_route[1:]: print(x)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict,deque
    sys.setrecursionlimit(10**5+2)

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=defaultdict(list)
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A].append(B)
        dic[B].append(A)
    
    L=[-1]*(N+1)
    R=[-1]*(N+1)


    d = deque()
    d.append((1,1))
    while len(d):
        now,count=d.pop()
        for goto in dic[now]:
            if L[goto]==-1 or count<L[goto]:
                L[goto]=count
                R[goto]=now
                d.append((goto,count+1))

    if any(x+1 for x in R[2:]):
        print('Yes')
        for x in R[2:]:
            print(x)
    else:
        print('No')
    


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
import resource
sys.setrecursionlimit(200000)
input = sys.stdin.readline


road_dict=defaultdict(list)

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

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

result_dict=defaultdict(list)

def next_tansaku(kiten,counter):
    for i in road_dict[kiten]:
        if (i not in result_dict) or (result_dict[i][1]>counter):
            result_dict[i]=[kiten,counter]
            next_tansaku(i,counter+1)


next_tansaku(1,0)

print('Yes')
for k in range(2,N+1):
    print(result_dict[k][0])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush

def dijkstra(start,node,edge):
    d = [2*10**5] * node
    m = [0]*node
    d[start] = 0
    q = [0]
    heapify(q)
    
    while(len(q) != 0):
      i = heappop(q)
      di = d[i]
      for j in edge[i]:
        if(d[j] > di+1):
          d[j] = di + 1
          heappush(q, j)
          m[j] = i+1
    return m

def main():
    N,M = map(int, input().split())
    
    E = [[] for _ in [0]*N]
    for i in range(M):
      a,b = (int(x) for x in input().split())
      E[a-1].append(b-1)
      E[b-1].append(a-1)

    m = dijkstra(0, N, E)
    print("Yes")
    print("\n".join(map(str, m[1:])))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
# 目印置くリスト
me = [0 for _ in range(n+1)]
me[1] = 1
miti = [[] for _ in range(n+1)]
tansaku = [0 for i in range(n+1)]
tansaku[1]=1
for i,j in l:
  miti[j].append(i)
  miti[i].append(j)
a = deque()
for i in miti[1]:
  a.append(i)
  me[i] = 1
while len(a)!=0:
#  print(a)
  w = a.popleft()
  tansaku[w] = 1
  for j in miti[w]:
    if tansaku[j]==0 and j not in a:
          a.append(j) 
          me[j] = w
#  print(w,tansaku,me)
  
print("Yes")
for i in range(len(miti)-2):
  print(me[i+2])

Submission status: Time Limit Exceeded

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)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        self.searched = [0] * len(self.Rs)

        w = 1
        count = 1
        new_nodes, count = self._search(1, w, count)
        #print(new_nodes, count)
        while count < N:
            w += 1
            _new_nodes = []
            for num in new_nodes:
                _new_node, count = self._search(num, w, count)
                _new_nodes.extend(_new_node)
                #print(_new_nodes, count)

            new_nodes = list(set(_new_nodes))
        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs))]

    def _search(self, num, w, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = []
        for node in r.searched_from:
            cons.remove(node)
        for con in cons:
            weight = self.Rs[con-1].weight
            if weight is None:
                self.Rs[con-1].weight = w
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.append(num)
                new_nodes.append(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.weight     = None
        self.searched_from = []
        self.fastest_room = None

r = Rs()
for i in range(N):
    cons_idx = []
    for j, a in enumerate(A):
        if a == (i+1):
            cons_idx.append(j)
    cons = [ B[i] for i in cons_idx ]
    cons_idx = []
    for j, a in enumerate(B):
        if a == (i+1):
            cons_idx.append(j)
    cons.extend([ A[i] for i in cons_idx ])
    r.append(R(i+1, cons))

l = r.search()
print("Yes")
for room in l:
    print(room)

Submission status: Time Limit Exceeded

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

a = []
b = []

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

#各部屋から行ける部屋
c = [[] for i in range(n)]

for i in range(m):
	c[a[i]].append(b[i])
	c[b[i]].append(a[i])

s = [0]
f = []

#部屋1からの距離
d = [10**6]*n
d[0] = 0

while s!=[]:
	x = s[-1]
	s.pop(-1)
	if not(x in f):
		for i in c[x]:
			if not(i in s):
				s.append(i)
			d[i] = min(d[i], d[x]+1)
		f.append(x)

print('Yes')
for i in range(1,n):
	m = 10**6
	ans = 0
	for j in c[i]:
		if d[j]<m:
			m = d[j]
			ans = j+1
	print(ans)

Submission status: Time Limit Exceeded

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

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

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

ans_list = [-1] * N

queue = [0]
seen = []

while queue:
    qi = queue.pop(0)
    # qi から 1 遠い頂点が gi
    for gi in g[qi]:
        if gi not in seen:
            queue.append(gi)
            if ans_list[gi] == -1:
                ans_list[gi] = qi
                seen.append(gi)

print("Yes")
for ans in ans_list[1:]:
    print(ans+1)  # 1-index に直す

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M = map(int, input().split())
path = []
for i in range(M):
    a = list(map(int, input().split()))
    path.append( a )

path = np.array(path)

def connect(x):
    a1 = path[path[:,0]==x][:,1]
    a2 = path[path[:,1]==x][:,0]
    return list(np.concatenate([a1,a2]))

con = list(map(connect, range(1,N+1)))

dangerous = list(range(2,N+1))
ans = np.zeros(N-1)

layer = [1]
judge="Yes"

def find_next(layer):
    for room in layer:
        next_rooms = con[room-1]
        next_rooms = np.array(list(set(next_rooms) & set(dangerous)))
        for r in next_rooms:
            ans[r-2] = room
            dangerous.remove(r)
    return next_rooms

while dangerous !=[]:
    layer = find_next(layer)
    if len(layer)==0:
        judge = "No"
        break

if judge =="Yes":
    print(judge)
    for m in ans:
        print(int(m))
else:
    print(judge)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
edge = [[] for i in range(n+1)]
reached = [0 for _ in range(n+1)]
guide = {i: 0 for i in range(2, n+1)}
queue = []
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        queue.append((b, a))
    elif b == 1:
        queue.append((a, b))
    else:
        edge[a].append(b)
        edge[b].append(a)

print("Yes")
while len(queue) > 0:
    # print(queue)
    e, now = queue.pop(0)
    if reached[e] == 0:
        reached[e] = 1
        guide[e] = now
        # edge[e].remove(now)
        for next in edge[e]:
            if next != 1 and reached[next] == 0:
                queue.append((next, e))

for i in range(2, n+1):
    print(guide[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
AB = [[0, 0] for _ in range(M)]
for i in range(M):
  AB[i] = list(map(int, input().split()))
  AB[i][0] -= 1
  AB[i][1] -= 1
AB = np.array(AB)

ikikata = [0 for _ in range(N)]
miti = [0 for _ in range(N)]

idx = [0]
j = 0
while j < len(idx):
  index1 = list(np.where(AB[:, 0] == idx[j])[0])
  index2 = list(np.where(AB[:, 1] == idx[j])[0])
  for i in index1:
    if miti[AB[i][1]] == 0:
      ikikata[AB[i][1]] = 1
      miti[AB[i][1]] = idx[j] + 1
      if AB[i][1] in idx:
        continue
      idx.append(AB[i][1])
  for i in index2:
    if miti[AB[i][0]] == 0:
      ikikata[AB[i][0]] = 1
      miti[AB[i][0]] = idx[j] + 1
      if AB[i][0] in idx:
        continue
      idx.append(AB[i][0])
  j += 1

if 0 in miti[1:]:
  print('No')
else:
  print('Yes')
  for i in miti[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

searchedroom = set([1])# 道標をおいた部屋リスト
markroom = [0] * N
pathlist = ABlist
searchqueue = queue.Queue()
searchqueue.put(1)
while not searchqueue.empty():
  roomid = searchqueue.get()
  pathlist1 = [path for path in pathlist if roomid == path[0]]
  pathlist2 = [path for path in pathlist if roomid == path[1]]
  pathlist = [path for path in pathlist if not path in pathlist1 and not path in pathlist2]

  for path in pathlist1:
    if markroom[path[1]-1] == 0:
      markroom[path[1]-1] = roomid
      searchqueue.put(path[1])
  for path in pathlist2:
    if markroom[path[0]-1] == 0:
      markroom[path[0]-1] = roomid
      searchqueue.put(path[0])

if 0 in markroom[1:]:
  print("No")
else:
  print("Yes")
  [print(x) for x in markroom[1:]]

Submission status: Time Limit Exceeded

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

import networkx as nx


def main():
    n, m = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]

    g = nx.Graph()
    for a, b in AB:
        g.add_edge(a, b)
    path = nx.single_target_shortest_path(g, 1)

    if len(path) != n:
        print('No')
        return
    # 有る
    print('Yes')
    for i in range(2, n + 1):
        print(path[i][1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
import sys

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

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())
A = []
B = []
neighbor = [[0 for x in range(N)] for y in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    neighbor[a][b] = 1
    neighbor[b][a] = 1

neighbor = csr_matrix(neighbor)

ans = []
for i in range(1,N):
    d, p = shortest_path(neighbor, return_predecessors=True, indices=[0, i], method='D')
    next_sign = get_path(0,i,p)
    if next_sign:
        ans.append(next_sign[-2]+1)
    else:
        print("No")
        sys.exit(0)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
c = [[0] * n for i in range(n)]
lead = [0]* n
for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    c[b[i]][a[i]] = 1
    c[a[i]][b[i]] = 1

cnt =0
d= deque()
d.append(0)
while len(d):
    cnt +=1
    k = len(d)
    for i in range(k):
        p = d[0]
        for j in range(n):
            if c[p][j] == 1:
                if lead[j] == 0:
                    lead[j] = p+1
                    d.append(j)
        d.popleft()
print('Yes')
for i in range(n-1):
    print(lead[i+1])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

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())
data = []
row = []
col = []
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    data.append(1)
    row.append(a)
    col.append(b)
    data.append(1)
    row.append(b)
    col.append(a)
graph = csr_matrix((data, (row, col)), shape=(n, n))
_, p = dijkstra(graph, return_predecessors=True, unweighted=True, indices=0)
for item in p[1:]:
    if(item < 0):
        print("No")
        exit()
print("Yes")
for item in p[1:]:
    print(item + 1)

Submission status: Time Limit Exceeded

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


def num():
    return int(input())


def nums():
    return map(int,input().split())

n,m = nums()

root = [list(nums()) for _ in range(m)]

res = [[math.inf]*n  for _ in range(n)]

for i in range(n):
    res[i][i] = 0

for i,j in root:
     
    res[i-1][j-1] = res[j-1][i-1] = 1

res = csr_matrix(res)
res,t = shortest_path(res, indices=0, return_predecessors=True)

if -9999 in res[1:]:
    print('No')
else:
    print('Yes')
    [print(i+1) for i in t[1:]]

Submission status: Time Limit Exceeded

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

X=[list(map(int,input().split())) for i in range(M)]
Y=[0 for i in range(N)]
Y[0]=-1
Z=[[] for j in range(N)]

import copy


for i in X:
  Z[i[0]-1].append(i[1]-1)
  Z[i[1]-1].append(i[0]-1)

  
item =[0]
while (0 in Y):
  note=[]
  for i in item:
    
    
    for j in Z[i]:
      Z[j].remove(i)
      if Y[j]==0:
        Y[j]=i+1
        note=note+[j]
  item=copy.deepcopy(note)
print("Yes")
for i in Y:
  if i==-1:
    continue
  print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n,m=map(int,input().split())
    root=[[0 for i in range(n)] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    min=[-1 for i in range(n)]
    min[0]=2
    dict={}
    for i in range(n):
        dict[i]=-1

    start=0
    check=[False]*n
    toVis=deque()
    check[start]=True
    for i in range(len(root[0])):
        if root[0][i]==1:
            toVis.append(i)
            dict[i]=start
        #   print(i,":",start)
            check[i]=True
    while len(toVis)>0:
        now=toVis.popleft()
        #print(now)
        check[now]=True
        for i in range(n):
            if root[now][i]==1 and check[i]==False:
                toVis.append(i)
                dict[i]=now
            # print(i,":",now)
                check[i]=True
    #print(dict)  
    for i in range(1,n):
        if dict[i]==-1:
            print("No")
            return 0
    print("Yes")
    for i in range(1,n):
        print(dict[i]+1)         


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
ab=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  ab[a].append(b)
  ab[b].append(a)
if not ab[1]:
  print('No')
  exit()
l,ll=deque([1]),deque([])
ans=[-1]*n
while l:
  x=l.popleft()
  ll.append(x)
  for i in ab[x]:
    if i in ll:
      continue
    if i in l:
      continue
    l.append(i)
    ans[i-1]=x
if all(i>=0 for i in ans[1:]):
  print('Yes')
  for i in ans[1:]:
    print(i) 
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
import queue


q = queue.Queue()

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


l = np.array(l)
lc = copy.deepcopy(l)
li = [-1 for _ in range(n)]

def search(x):
    if sum(lc[x]) == 0:
        q.queue = False
        return
    
    ind_lis = np.where(lc[x] == 1)
#     print(ind_lis)
    for e in ind_lis[0]:
#         print(e+1)
        if li[e] == -1:
            li[e] = x
    for e in ind_lis[0]:
        lc[x][e] =0
        lc[e][x] =0
        q.put(e)
x = 0
search(x)
while q.queue:
    search(q.get())

if li[1:].count(-1) == 0:
    print('Yes')
    for e in li[1:]:
        print(e+1)
else:
    print('No')

Submission status: Time Limit Exceeded

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

d = {}

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

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

que = [1]
checked = set()
ans = {1:-1}

while que:
    now = que.pop(0)
    for h in d[now]:
        if not h in ans:
            ans[h] = now
            que.append(h)
    if len(ans) == N:
        break
    
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:
import copy

N, M = map(int, input().split())
ans = [0]*(N+1)

path = []
check = []
for neveruse in range(M):
    l = list(map(int, input().split()))
    path.append(l)
    if 1 in l:
        temp = copy.copy(l)
        temp.remove(1)
        ans[temp[0]] = 1
        check.append(temp[0])

while len(check) > 0:
    precheck = copy.copy(check)
    check = []
    for n in precheck:
        for item in path:
            if n in item:
                tmpl = copy.copy(item)

                tmpl.remove(n)

                if ans[tmpl[0]] == 0:
                    ans[tmpl[0]] = n
                    check.append(tmpl[0])

ans.pop(1)

if ans.count(0) > 1:
    print('No')

else:
    ans[0] = 'Yes'

    for i in range(N):
        print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ary = []
a = []
b = []
ary = [0 for i in range(n)]
chk = [False for i in range(n)]
d = {}
for i in range(m):
	aa, bb = map(int, input().split())
	if aa not in d:
		d[aa] = []
	d[aa].append(bb)
	if bb not in d:
		d[bb] = []
	d[bb].append(aa)

flg = True
e = set()
e.add(1)
#print (d)

chk[0] = True
f = set()
cnt = 0
while True:
	flg = False
	for i in e:
		for j in d[i]:
			if chk[j-1]:
				continue
			if ary[j-1] == 0:
				flg = True
				ary[j-1] = i
				chk[j-1] = True
				cnt += 1
				f.add(j)
	e = f.copy()
	if flg == False:
		break
if cnt < n-1:
	print ("No")
else:
	print ("Yes")
	for i in ary[1:]:
		print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
N,M = map(int,input().split())

A = []
B = []
print("Yes")
for x in range(M):
    At,Bt = map(int,input().split())
    A.append(At)
    B.append(Bt)
rinsetu =[[0 for x in range(N)] for y in range(N)]
for x in range(M):
    rinsetu[A[x]-1][B[x]-1] = 1
    rinsetu[B[x]-1][A[x]-1] = 1
L = csr_matrix(rinsetu)
shortest,p =  shortest_path(L,return_predecessors=True,indices=0,directed=False,unweighted=True)


for x in p[1:]:
    print(x+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

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

from collections import deque

d = deque()
d.append(0)

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

if min(Dis)<0:
  print('No')
  sys.exit()
print('Yes')
for i in range(1,n):
  print(Sin[i])

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
a = []
b = []
for i in range(M):
    aa, bb = list(map(int, input().split()))
    a.append(aa-1)
    b.append(bb-1)
    
table = [0] * N
ans = [0] * N

table[0] = 1

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


for i in range(M):
    miti[a[i]].append(i)
    miti[b[i]].append(i)


#start
q = [0]

while(q):
    
    x = q[0]
    
    for i in range(len(miti[x])):
        m = miti[x][i]
        if a[m] == x and table[b[m]]==0:
            table[b[m]]=1
            ans[b[m]]=a[m]+1
            q.append(b[m])
        if b[m] == x and table[a[m]]==0:
            table[a[m]]=1
            ans[a[m]]=b[m]+1
            q.append(a[m])         
    
    q.pop(0)

if sum(table)==N:
    print("Yes")
    for i in range(1,N):
        print(ans[i])
else:
    print("No")

Submission status: Time Limit Exceeded

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

    visited = [-1] * N
    stack = deque([0])
    visited[0] = 0
    sign = [0] * N
    while stack:
        v = stack[0]
        if G[v]:
            w = G[v].pop()
            if visited[w] == 1 or w in stack:
                continue
            visited[w] = 1
            sign[w] = v+1
            stack.append(w)
        else:
            stack.popleft()

    sign = sign[1:]
    if all(s > 0 for s in sign):
        print('Yes')
        for s in sign:
            print(s)
    else:
        print('No')
        
main()

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
rt = [[] for i in range(n)]
dk = [10**10] * n
srb = [None]*n

for i in range(m):
    a,b = mi()
    rt[a-1].append(b-1)
    rt[b-1].append(a-1)

l = []
dk[0] = 0
for i in rt[0]:
    l.append(i)
    dk[i] = 1
    srb[i] = 1

while len(l) != 0:
# for j in range(20):
    # ルートが最小のnodeを見つける
    mincost = 10**6
    for i in l:
        if mincost > dk[i]:
            mincost = dk[i]
            minnode = i
    # そのnodeの数字を確定し、
    l.remove(minnode)
        
    # 隣接する確定してないnodeにコストを上書き（小さければ）
    # queueに隣接nodeをappend
    for i in rt[minnode]:
        if dk[i] > dk[minnode]:
            dk[i] = dk[minnode]+1
            srb[i] = minnode+1
            if i not in l:
                l.append(i)

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
chizu = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    chizu[a-1].append(b-1)
    chizu[b-1].append(a-1)
inf = 10**10
dep = [inf]*n
dep[0] = 0
prev = [-1]*n
former = []

for i in chizu[0]: #１につながっている部屋だけ先に入力する
    prev[i] = 1
    dep[i] = 1
    former.append(i) #formerに深さが１の部屋を格納する

while former:
    c = former.pop(0)
    for i in chizu[c]:
        if dep[i]!=inf:
            continue
        else:
            dep[i] = dep[c]+1
            prev[i] = c+1
            former.append(i)
print('Yes')
for i in range(1,n):
    print(prev[i])