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:
# coding: utf-8
import sys
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
sys.setrecursionlimit(10**7)
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [0] * (N+1)

    while stack:
        dist, current, prev = heappop(stack)
        if not seen[current]:
            seen[current] = True
            mark[current] = prev
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
alist = []
blist = []
ablist = []
N,M=map(int, input().split())
for _ in range(M):
    a,b=map(int, input().split())
    alist.append(a)
    blist.append(b)
Ndic = {1:[0,0]}
def duplistindex(list1,list2, number):
    returnlist = []
    for l in [i for i, x in enumerate(list1) if x == number]:
        returnlist.append(list2[l])
    for l in [i for i, x in enumerate(list2) if x == number]:
        returnlist.append(list1[l])
    return returnlist
reviewed = [1]
while reviewed:
    for review in reviewed:
        for i in duplistindex(alist,blist,review):
            if i not in Ndic.keys():
                Ndic[i] = []
                Ndic[i].append(Ndic[review][0] + 1)
                Ndic[i].append(review)
                reviewed.append(i)
            else:
                if Ndic[i][0] > Ndic[review][0] + 1:
                    Ndic[i][0] = Ndic[review][0] + 1
                    Ndic[i][1] = review
                    reviewed.append(i)
        reviewed.remove(review)
print('Yes')
for i in range(N-1):
    print(Ndic[i+2][1])

Submission status: Time Limit Exceeded

Solution code:
# https://qiita.com/kazukazukazukazu/items/e5db00a3aefb1f5ed72f
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

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

graph = Dijkstra()

for _ in range(M):
    a, b = map(int, input().split())
    graph.add(a, b, 1)

# for a, b in AB:
#     graph.add(a, b, 1)

ans = [float('inf')] * (N-1)
flg = False
for i in range(2, N+1):
    result = graph.getDijkstraShortestPath(i, 1)
    if result[1]==float('inf'):
        flg = True
        break
    ans[i-2] = result[1]
#     print(result[1])

if flg:
    print('No')
else:
    print('Yes')
    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import itertools
#input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

n,m = ri()
edge=[[0]*n for i in range(n)]
for i in range(m):
    a, b = ri()
    a+=-1
    b+=-1
    edge[a].append(b)
    edge[b].append(a)

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    while len(q):
        
        now, p, d = q.popleft()
        if now==p:
            continue
        if visited[now]==1:
            continue
        
        ans[now]=p+1
        dis[now]=d+1
        visited[now]=1
        for i in range(len(edge[now])):
            if visited[edge[now][i]]==0:
                q.append((edge[now][i], now, dis[now]))
                
                visited[edge[now][i]]==1
bfs(0)

flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    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

n, m = (int(each) for each in input().split())
paths = []
for each in range(m):
    paths.append(set([int(each) for each in input().split()]))

result = [-1]*(n+1)

queue = deque()
queue.append(1)
while queue:
    start_at = queue.popleft()

    for path in paths:
        if start_at in path:
            neibor = (path-{start_at}).pop()
            if result[neibor] != -1:
                continue
            result[neibor] = start_at
            queue.append(neibor)

if -1 in result[2:]:
    print('No')
else:
    print('Yes')
    print('\n'.join(str(each) for each in result[2:]))

Submission status: Time Limit Exceeded

Solution code:
mNM = map(int, input().split())
lNM = list(mNM)

mWay = [map(int, input().split()) for i in range(lNM[1])]
lWay = [list(mWay[i]) for i in range(lNM[1])]

maps = [-1 for i in range(lNM[0])]
deep = [-1 for i in range(lNM[0])]
ways = [[] for i in range(lNM[0])]

for i in range(lNM[1]):
    ways[lWay[i][0] - 1].append(lWay[i][1])
    ways[lWay[i][1] - 1].append(lWay[i][0])

maps[0] = 0
deep[0] = 0

for i in range(lNM[0]):
    try:
        index = [n for n, v in enumerate(deep) if v == i]
        for x in index:
            for w in ways[x]:
                if(deep[w - 1] == -1):
                    deep[w - 1] = i + 1
                    maps[w - 1] = x + 1
        
    except:
        pass
    
if(-1 in maps):
    print('No')
else:
    print('Yes')
    for i in maps[1:]:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import math
(r, p)=[int(n) for n in input().split()]
route_list=[[0 for j in range(r)] for i in range(r)]
for i in range(p):
  (x, y)=[int(n)-1 for n in input().split()]
  route_list[x][y] = 1
  route_list[y][x] = 1 

node_num = len(route_list)

unsearched_nodes = list(range(node_num))
distance = [math.inf] * node_num
previous_nodes = [-1] * node_num
distance[0] = 0

def initial():
  unsearched_nodes = list(range(node_num))
  distance = [math.inf] * node_num
  previous_nodes = [-1] * node_num
  distance[0] = 0

def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0):
    posible_min_distance = math.inf
    for node_index in unsearched_nodes:
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index]
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes)
    unsearched_nodes.remove(target_min_index)

    target_edge = route_list[target_min_index]
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis
                previous_nodes[index] =  target_min_index

ans=[-1]*(r-1)
for i in range(1, r):
  if ans[i-1] != -1:
    continue
  previous_node = i
  string=""
  while previous_node != -1:
    if previous_node !=0:
        string += str(previous_node + 1) + " "
    else:
        string += str(previous_node + 1)
    previous_node = previous_nodes[previous_node]
  string = string.split()
  for i, v in enumerate(string[:-1]):
    ans[int(v)-2]=string[i+1]

if "No" in ans:
  print("No")
else:
  print("Yes")
  for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import queue

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])

q = queue.Queue()
q.put(0)
f = []

#部屋1からの距離
d = [10**6]*n
d[0] = 0
ans = [0]*n
while not q.empty():
	x = q.get()
	if not(x in f):
		for i in c[x]:
			if not(i in f):
				q.put(i)
			if d[x]+1 < d[i]:
				d[i] = d[x]+1
				ans[i] = x+1
			
		f.append(x)

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

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 i == 0 or keys[i]:
            continue
        if i not in q:
            q.append(i)
            keys[i] = next + 1
print('Yes')
print(*keys[1:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
ab=list(list(map(int,input().split())) for i in range(m))
d=deque()
d.append(1)
t=[deque() for i in range(n)]
for i in range(m):
  t[ab[i][0]-1].append(ab[i][1])
  t[ab[i][1]-1].append(ab[i][0])
h=[0]*(n-1)
u=deque()
while 0 in h:
  for i in t[d[0]-1]:
    if i in d or i in u:
      continue
    else:
      h[i-2]+=d[0]
      d.append(i)
  u.append(d[0])
  d.popleft()
print("Yes")
for i in range(n-1):
  print(h[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, item):
        heapq.heappush(self.heap, item)

    def pop(self):
        return heapq.heappop(self.heap)

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


n, m = [int(i) for i in input().split()]
V_ds = [None, 0] + [10**10] * (n-1)
V_prevs = [None] * (n+1)
class V:
    def __init__(self, idx):
        self.idx = idx
        # self.d = 10**10 if idx != 1 else 0
        # self.prev = None

    def __lt__(self, other):
        return V_ds[self.idx] < V_ds[other.idx]

raw_edges = [[int(i) for i in input().split()] for i in range(m)]
edges = {i: [] for i in range(1, n+1)}
for i, j in raw_edges:
    edges[i].append(j)
    edges[j].append(i)

Q = PriorityQueue()

for i in range(1, n+1):
    Q.push(V(i))
while len(Q):
    u = Q.pop()

    for d in edges[u.idx]:
        if V_ds[d] > V_ds[u.idx] + 1:
            V_ds[d] = V_ds[u.idx]+ 1
            V_prevs[d] = u.idx
            heapq.heapify(Q.heap)

ans = V_prevs[2:]
if None in ans:
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
inf = 10 ** 7
N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]
a = [[] for i in range(N)]
for i in P:
    a[i[0]-1].append(i[1]-1)
    a[i[1]-1].append(i[0]-1)
path = [-1] * N
path[0] = 0
checked = [False] * N
stack = [(0,0)]
while (len(stack) != 0):
    kk = stack.pop(0)
    now = kk[0]
    pre = kk[1]
    if  not checked[now]:    
        nextP = a[now]
        checked[now] = True
        path[now] = pre
        for i in nextP:
            stack.append((i,now))
if False in checked:
    print("No")
else:
    print("Yes")
    for i in path[1:]:
        print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
t = [[] for i in range(n)]
dis = [n for i in range(n)]
dis[0] = 0
near = [0 for i in range(n)]
c = []
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    dis[t[0][i]] = 1
    near[t[0][i]] = 0
    c.append(t[0][i])
while len(c) > 0:
    e = c[0]
    for j in range(len(t[e])):
        if dis[t[e][j]] >= dis[e] +1:
            dis[t[e][j]] = dis[e] +1
            near[t[e][j]] = e
            c.append(t[e][j])
    del c[0]
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)

Submission status: Time Limit Exceeded

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

paths = set()
for _ in range(M):
    a, b = map(int, input().split())
    paths.add((a-1, b-1))

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    kick_list = []
    next_key_rooms = []
    for key_room in key_rooms[-1]:
        for path in paths:
            if key_room in path:
                else_room = path[0]
                if else_room == key_room:
                    else_room = path[1]
                kick_list.append(path)
                if rooms[else_room] == -1:
                    rooms[else_room] = step
                    next_key_rooms.append(else_room)
                    marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)
    for kick in kick_list:
        if kick in paths:
            paths.remove(kick)

flag = True
for room in rooms[1:]:
    if room == -1:
        flag = False
        print('No')
        break

if flag:
    print('Yes')
    for i in marks:
        print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
r=[[] for x in range(n)]
for c in range(m):
    a,b=map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
s=[-1]*n
u=[0]
v=[]
k=1
for c in range(10**5):
    for d in u:
        for e in r[d]:
            if s[e]==-1:
                s[e]=d
                k+=1
                v.append(e)
    if k==n:
        break
    u=v
print('Yes')
for c in range(n-1):
    print(s[c+1]+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
room, route_count = map(int,input().split())
route = np.array([list(map(int,input().split())) for _ in range(route_count)])

object_nums = [1]
ans = np.array([0]*(room-1))

def mem_ans(ans, object_num, next):
    if next is not None:
      for n in next:
        if ans[n-2] == 0:
          ans[n-2] = object_num
    return ans

for object_num in object_nums:
    object_rows = route[np.any(route==object_num, axis=1)]
    route[np.any(route==object_num, axis=1)] = 0
    next = object_rows[object_rows!=object_num]
    ans = mem_ans(ans, object_num, next)
    object_nums.extend(next)

if 0 in set(ans):
  print('No')
else:
  print('Yes')
  for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

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

csr = csr_matrix(l)
d, p = shortest_path(csr, method='D', indices=0, directed=False, unweighted=True, return_predecessors=True)
#d, p = shortest_path(csr, indices=0, directed=False, unweighted=True, return_predecessors=True)
p += 1
#print(p)
print('Yes')
for i in p:
  if i < 0: continue
  print(i)

Submission status: Time Limit Exceeded

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

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)
ans[0] = 0.5

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:
            if ans[r-1]==0:
                ans[r-1] = room
            #dangerous.remove(r)
    return next_rooms

while ans.min()==0:
    layer = find_next(layer)
    if len(layer)==0:
        judge = "No"
        break

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

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:
        if n%2 == 0:
            next_n = n+1
        else:
            next_n = n-1

        next = A[next_n]

        if Past.count(next) == 0:
            Past.append(next)
            Que.append(next)
            Mark[next-2]=Que[0]

    delete = []

    for n in next_road:
        if n%2 == 0:
            m = n+1
        else:
            m = n-1

        delete.append(n)
        delete.append(m)

    delete.sort(reverse=True)

    for n in delete:
        A.pop(n)

    Que.pop(0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import networkx as nx
n,m=map(int,input().split())
g = nx.Graph()
l = sys.stdin.readlines()
for x in l:
    g.add_edge(int(x.split(' ')[0]), int(x.split(' ')[1].strip()))
l=[None]*(n-1)
for i in range(2,n+1):
    l[i-2] = nx.shortest_path(g, source=1, target=i)[-2]
if None in l:
    print("No")
else:
    print("Yes")
    for x in l:
        print(x)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
if M < N - 1:
  print("No")
else:
  roots = [list(map(int, input().split())) for _ in range(M)]

  nvisit = list(range(2, N + 1))
  visit = [None for _ in range(N + 1)]
  min_visit = [1]

  while nvisit != []:
    next_visit = []
    for v in min_visit:
      for root in roots:
        if v in root:
          i = 1 - root.index(v)
          if root[i] in nvisit:
            nvisit.remove(root[i])
            visit[root[i]] = v
            next_visit.append(root[i])

    min_visit = next_visit

  print("Yes")
  for s in visit[2:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
sys.setrecursionlimit(10**7)
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [0] * (N+1)
    done = [False] * (N+1)

    while stack:
        dist, current, prev = heappop(stack)
        if not seen[current]:
            seen[current] = True
            mark[current] = prev
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

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):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = []
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.extend(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = []
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(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.searched_from = set([])
        self.fastest_room = None

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m = map(int,input().split())
    list = [[0 for i in range(0)] for j in range(n+1)]
    key = [1]
    ans = [0] * (n+1)
    flag = [0] * (n+1)

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

    for i in range(2,n+1):
        if 1 in list[i]:
            ans[i] = 1
            flag[i] = 1
            key.append(i)

    for x in range(n):
        for i in range(2,n+1):
            for j in key:
                if j in list[i] and flag[i] == 0:
                    ans[i] = j
                    flag[i] = 1
                    key.append(i)

    if 0 in ans[2:]:
        print("No")
    else:
        print("Yes")
        for i in ans[2:]:
            print(i)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

N, M = map(int,input().split())
G = nx.Graph()
[G.add_node(i + 1) for i in range(N)]

for _ in range(M):
    A, B = map(int,input().split())
    G.add_edge(A, B)

flag = 1
print_str = 'Yes\n'
for i in range(2, N + 1):
    haspath = nx.has_path(G, source = i, target = 1)
    
    if haspath == False:
        flag = 0
        break
    else:
        ans = nx.shortest_path(G, source = i, target = 1)
        print_str += (str(ans[1]) + '\n')
        
if flag == 1:
    print(print_str[:-1])
else:
    print('No')

Submission status: Time Limit Exceeded

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

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)
graph = csr_matrix((data, (row, col)), shape=(n, n))
_, p = dijkstra(graph, return_predecessors=True, unweighted=True, directed=False, indices=0, limit=n)
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:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[Tuple[int, int]], n: int) -> List[int]:
    passages = defaultdict(set)
    for a, b in values:
        passages[a].add(b)
        passages[b].add(a)
    if len(passages) < n:
        return []
    to_visit = deque((1,))
    visited = set()
    # 0 idx is not used
    distances = [n + 1] * (n + 1)
    distances[1] = 0
    signs = [1] * (n + 1)
    while to_visit:
        cur = to_visit.popleft()
        for neighbour in passages[cur]:
            tmp = distances[cur] + 1
            if tmp < distances[neighbour]:
                distances[neighbour] = tmp
                signs[neighbour] = cur
            if neighbour not in visited:
                to_visit.append(neighbour)
        visited.add(cur)
    # LOG.debug((visited))
    # LOG.debug((distances))
    if len(visited) < n:
        return []
    return signs[2:]


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    N, M = map(int, stdin.readline().split())
    values = []
    for _ in range(M):
        a, b = map(int, stdin.readline().split())
        values.append((a, b))
    result = solve(values, N)
    if not result:
        print("No", file=stdout)
    else:
        print("Yes", file=stdout)
        print("\n".join(map(str, result)), file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    # pylint: disable=super-init-not-called
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split( ))
AB = [list(map(int,input().split( ))) for _ in range(M)]
all_ = set([i for i in range(1,N)])
child = [[] for _ in range(N)]
ans = [[] for _ in range(N)]
for ab in AB:
    child[ab[0]-1].append(ab[1]-1)
    child[ab[1]-1].append(ab[0]-1)
child = list(map(set,child))
check = [0]
while len(all_ ) != 0:
    checkk = {-1}
    for c in check:
        a = child[c] & all_
        ans[c] = list(a)
        checkk = checkk | set(a)
        all_ = all_ - child[c]
    check = checkk - {-1}
anss = [[] for i in range(N)]
for i in range(N):
    for a in ans[i]:
        anss[a] = i
print('Yes')
for a in anss[1:]:
    print(a + 1)