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:
from sys import stdin
input = stdin.readline


def main():
    n, m = map(int, input().split())

    nexts = [[] for i in range(n)]
    
    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        nexts[ai].append(bi)
        nexts[bi].append(ai)

    scores = [m] * m
    scores[0] = 0

    red_set = [0]
    new_red_set = []
    blue_set = [x + 1 for x in range(n - 1)]
    new_blue_set = blue_set

    arrows = [0] * n

    while len(blue_set) != 0:
        for r in red_set:
            for nxt in nexts[r]:
                if nxt in blue_set:
                    new_blue_set.remove(nxt)
                    if nxt not in new_red_set:
                        new_red_set.append(nxt)
                    arrows[nxt] = r
                blue_set = new_blue_set

        red_set = new_red_set
        new_red_set = []
    
    print("Yes")
    for arrow in arrows[1:]:
        print(arrow + 1)


if __name__ == "__main__":
    main()

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)[0]
#     ind_lis = [e for e in ind_lis if li[e] == -1]
#     print(li)
#     print(lc[x])
    for i,e in enumerate(lc[x]):
#         print(i,e)
        if li[i] != -1 or e == 0:
            continue
        li[i] = x
#         print('q', i+1)
        q.put(i)
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:
## ---- DFS
class Node(object):
    def __init__(self, name):
        self.name = name
    def getName(self):
        return self.name
    def __str__(self):
        return self.name
    
class Edge(object):
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest
    def getSource(self):
        return self.src
    def getDestination(self):
        return self.dest
    def __str__(self):
        return self.src.getName() + '->' + self.dest.getName()
    
class WeightedEdje(Edge):
    def __init__(sekf, src, dest, weight=1.0):
        self.src = scr
        self.dest = dest
        self.weight = weight
    def getWeight(self):
        return self.weight
    def __str__(self):
        return self.src.getName() + '->(' + str(self.weight) + ')' + self.dest.getName()

class Digraph(object):
    def __init__(self):
        self.nodes = []
        self.edges = {}
    def addNode(self, node):
        if node in self.nodes:
            raise ValueError('Duplicate node')
        else:
            self.nodes.append(node)
            self.edges[node] = []
    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.nodes and dest in self.nodes):
            raise ValueError('node not in graph')
        self.edges[src].append(dest)
    def childrenOf(self, node):
        return self.edges[node]
    def hasNode(self, node):
        return node in self.nodes
    def __str__(self):
        result=''
        for src in self.nodes:
            for dest in self.nodes:
                result = result + src.getName() + '->' + dest.getName() + '\n'
        return result[:-1]
            
class Graph(Digraph):
    def addEdge(self, edge):
        addEdge(self, edge)
        Digraph.addEdge(self, edge)
        rev  = Edge(edge.getDestination(), edge.getSorce())
        Digraph.addEdge(self, rev)

def DFS(graph,start,end,path,shortest):
    path = path + [start]
    if start == end:
        return path
    for node in graph.childrenOf(start):
        if node not in path:
            if shortest == None or len(path) < len(shortest):
                newPath = DFS(graph, node, end, path, shortest)
                if newPath != None:
                    shortest = newPath
    return shortest

def shortestPath(graph, start, end):
    return DFS(graph, start, end, [], None)

## ----main
N, M = list(map(int,input().split()))

g = Digraph()
for n in range(1,N+1):
    g.addNode(n)

for _ in range(M):
    a,b = list(map(int,input().split()))
    g.addEdge(Edge(a,b))
    g.addEdge(Edge(b,a))


err = False
paths = []
for i in range(2,N+1):
    ret = shortestPath(g,i,1)
    if len(ret) == 0:
        break
    paths.append(ret)

if err == False:
    print("Yes")
    for p in paths:
        print(p[1])
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])

for x in s:
    g.add_edge(x[0],x[1])
di=nx.single_target_shortest_path(g,target=1)

if len(di)!=n:
    print("No")
    exit()

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

Submission status: Time Limit Exceeded

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


input = sys.stdin.readline
def IS(cb): return cb(input().strip())
def IL(cb): return [cb(s) for s in input().strip().split()]
def IR(cb, rows): return [IS(cb) for _ in range(rows)]
def ILL(cb, rows): return [IL(cb) for _ in range(rows)]


def solve():
    N, M = IL(int)
    AB = ILL(int, M)
    graph = [[False] * N for _ in range(N)]
    for a, b in AB:
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True
    que = deque()
    que.append(0)
    visited = [False] * N
    visited[0] = True
    route = [0] * N
    while len(que):
        current = que.popleft()
        for next in range(N):
            if graph[current][next] and not visited[next]:
                visited[next] = True
                que.append(next)
                route[next] = current + 1

    print('Yes')
    for i in route[1:]:
        print(i)


solve()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
connect = [[] * 1 for i in range(N+1)]
for i in range(M):
  A, B = map(int, input().split())
  connect[A].append(B)
  connect[B].append(A)

check = [0]*(N+1)    ###部屋の深さを調べたかどうか
Next = [0]*(N+1)      ###部屋iに繋がる部屋番号
que = []

for i in connect[1]:   ###初期条件
  check[i]=1
  Next[i]=1
  que.append(i)

while que:
  a = que.pop(0)
  for i in connect[a]:
    if check[i]==0:
      check[i]=1
      Next[i]=a
      que.append(i)

if check.count(0)>2:
  print("No")
  exit()

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

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
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)

# 道の接続マップ
route2 = {}

for a, b in zip(A, B):
    route2.update({(a - 1, b - 1): True})
    route2.update({(b - 1, a - 1): True})

# 探索する
room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

# 次に行く部屋
stack = [0]

while stack:
    now = stack.pop()
    for j in range(N):
        if (now, j) in route2.keys():
            if room_depth[j] is None or room_depth[j] > room_depth[now] + 1:
                room_depth[j] = room_depth[now] + 1
                room_sign[j] = now + 1
                stack.append(j)

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    n, m = map(int, input().split())

    nexts = [[] for i in range(n)]
    
    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        nexts[ai].append(bi)
        nexts[bi].append(ai)

    scores = [m] * m
    scores[0] = 0

    red_set = [0]
    new_red_set = []
    blue_set = [x + 1 for x in range(n - 1)]
    new_blue_set = blue_set

    arrows = [0] * n

    while len(blue_set) != 0:
        for r in red_set:
            for nxt in nexts[r]:
                if nxt in blue_set:
                    new_blue_set.remove(nxt)
                    if nxt not in new_red_set:
                        new_red_set.append(nxt)
                    arrows[nxt] = r
                blue_set = new_blue_set

        red_set = new_red_set
        new_red_set = []
    
    print("Yes")
    for arrow in arrows[1:]:
        print(arrow + 1)

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)[0]
    ind_lis = [e for e in ind_lis if li[e] == -1]
#     print(li)

    for e in ind_lis:
#         print(e+1)

        lc[x][e] =0
        lc[e][x] =0
        if li[e] == -1:
            li[e] = x
#             print('q', e+1)
            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:
s = input().split()

n = int(s[0])
m = int(s[1])

ll = [set() for j in range(n + 1)]
sl = set()

s1 = {1}
s2 = set()


for i in range(m):
    t = input().split()
    sl.add(int(t[0]))
    sl.add(int(t[1]))
    ll[int(t[0])].add(int(t[1]))
    ll[int(t[1])].add(int(t[0]))


if sum(sl) < int(((n + 1) * n ) / 2):
    print("No")
else:
    count = 0
    mydict = {}
    out = 0

    while count < n:
        s2.clear()
        for i in sl:
            if len(s1 & ll[i]) != 0:
                s3 = list(s1 & ll[i])
                mydict.setdefault(i,s3[0])
                s2.add(i)
                count += 1
        sl = sl - s2
        s1 = s2.copy()

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float("inf")

N, M, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

dist = [INF] * (N + 1)
ans = [-1] * (N + 1)

Q = deque([1])
dist[1] = 0
while Q:
    v = Q.popleft()
    d = dist[v] + 1
    for u in E[v]:
        if dist[u] > d:
            dist[u] = d
            ans[u] = v
            Q.appendleft(u)

print("Yes")
for a in ans[2:]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
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)

# 道の接続マップ
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True


# 探索する
room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

# 次に行く部屋
stack = [0]
while stack:
    now = stack.pop()
    for j in range(N):
        if route[now][j]:
            # 次の部屋の深さが不明な場合または今の部屋の深さ+1より大きい場合は次の部屋の情報を更新
            if room_depth[j] is None or room_depth[j] > room_depth[now] + 1:
                room_depth[j] = room_depth[now] + 1
                room_sign[j] = now + 1
                stack.append(j)

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = int(S.split()[0])
M = int(S.split()[1])
P = []
for i in range(M):
    P.append(input().split())
Q = [0]*(N+1)
Q[0] = 1
Q[1] = 1
fin = [1]
done = []
T = True
while 0 in Q:
    for i in fin:
        if i not in done:
            for j in range(M):
                x0 = int(P[j][0])
                x1 = int(P[j][1])
                if x0 == i and Q[x1] == 0:
                    Q[x1] = i
                    if x1 not in fin:
                        fin.append(x1)
                    P[j][0] = 0
                    P[j][1] = 0
                if x1 == i and Q[x0] == 0:
                    Q[x0] = i
                    if x0 not in fin:
                        fin.append(x0)
                    P[j][0] = 0
                    P[j][1] = 0
            done.append(i)
        if 0 not in Q:
            break
    if fin == done:
        T = False
        break
if T:
    print('Yes')
    for i in range(2, N+1):
        print(Q[i])
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import copy

s = input().split()

n = int(s[0])
m = int(s[1])


ll = [set() for j in range(n + 1)]
sl = set()

s1 = {1}
s2 = set()


for i in range(m):
    t = input().split()
    sl.add(int(t[0]))
    sl.add(int(t[1]))
    ll[int(t[0])].add(int(t[1]))
    ll[int(t[1])].add(int(t[0]))


if sum(sl) < int(((n + 1) * n ) / 2):
    print("No")
    #print(sl,int(((n + 1) * n ) / 2))
else:
    count = 0
    goal = [0 for i in range(n)]
    out = 0

    while count < n:
        s2.clear()
        #out += 1
        for i in sl:
            if len(s1 & ll[i]) != 0:
                s3 = list(s1 & ll[i])
                #print(s3)
                goal[i-1] = s3[0]
                s2.add(i)
                count += 1
                #del ll[i]
                #ll[i].clear()
        sl = sl - s2
        s1 = s2.copy()
        #print(s1,s2)

        #if out >= 200:
        #    break
    print("Yes")
    for i in range(1,n):
        print(goal[i])

    #print(count,out)
    #print(goal)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = (int(x) for x in input().split())
ls_A = []
ls_B = []
for i in range(M):
    A_i, B_i = (int(x) for x in input().split())
    ls_A.append(A_i)
    ls_B.append(B_i)

arr_A = np.array(ls_A)
arr_B = np.array(ls_B)

num = 0
ls_rank = [[1]]
ls_rank_all = [1]
while sum(len(v) for v in ls_rank) < N:
    ls_append_all = []
    for i in ls_rank[num]:
        ls_append_temp = list(arr_B[np.where(arr_A==i)]) + list(arr_A[np.where(arr_B==i)])
        ls_append = [i for i in ls_append_temp if i not in ls_rank_all]
        ls_append_all = ls_append_all + ls_append
        ls_rank_all = ls_rank_all + ls_append
    ls_rank.append(ls_append_all)
    num+=1

print('Yes')
for i in range(2,N+1):
    ls_pass = list(arr_B[np.where(arr_A==i)]) + list(arr_A[np.where(arr_B==i)])
    for y, row in enumerate(ls_rank):
        if i in row:
            ls_rank_down = ls_rank[y-1]
        else:
            pass
    print(list(set(ls_pass) & set(ls_rank_down))[0])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)
# hex_str = hex(i)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()

	ans = {}
	ans[0] = 0
	ki = [[] for i in range(N)]

	for i in range(M):
		A,B = inputMap()
		A -= 1
		B -= 1
		ki[A].append(B)
		ki[B].append(A)

	print("Yes")
	stc = Queue()
	for ii in ki[0]:
		ans[ii] = 0
		stc.enqueue(ii)

	while True:
		next = stc.dequeue()
		#print(next)
		if next == None:
			break
		for ii in ki[next]:
			if ii in ans:
				pass
			else:
				ans[ii] = next
				tmp = []
				for jj in ki[ii]:
					if jj in ans:
						pass
					else:
						tmp.append(jj)
				ki[ii] = tmp
				stc.enqueue(ii)

	#print(ans)
	#print(ki)
	aa = [0 for i in range(N)]
	for k, v in ans.items():
		if k == 0:
			continue
		aa[k] = v+1

	#print(aa)
	for i,val in enumerate(aa):
		if i == 0:
			continue
		print(val)


class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
nm=list(map(int, input().split()))
n=nm[0]
m=nm[1]
ab=[]
ans=['Yes']+[0]*(n-1)
for i in range(m):
    ab.append(list(map(int, input().split())))

roomto=[1]
flg=True
while flg:
    roomto1=[]
    path=[]
    flg=False
    abc=ab.copy()
    for pair in ab:
        if pair[0] in roomto and pair[1] in roomto:
            abc.remove(pair)
        elif pair[0] in roomto:
            roomto1.append(pair[1])
            abc.remove(pair)
            ans[pair[1]-1]=pair[0]
            flg=True
        elif pair[1] in roomto:
            roomto1.append(pair[0])
            abc.remove(pair)
            ans[pair[0]-1]=pair[1]
            flg=True
    ab=abc
    roomto1=list(set(roomto1))
    roomto=roomto1

if 0 not in ans:
    for value in ans:
        print(value)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
nm=list(map(int, input().split()))
n=nm[0]
m=nm[1]
ab=[]
ans=['Yes']+[0]*(n-1)
room=[i+2 for i in range(n-1)]

for i in range(m):
    ab.append(list(map(int, input().split())))

roomto=[1]
flg=True
while flg:
    roomto1=[]
    path=[]
    flg=False
    abc=ab.copy()
    for pair in ab:
        if pair[0] in roomto and pair[1] in roomto:
            abc.remove(pair)
        elif pair[0] in roomto:
            roomto1.append(pair[1])
            abc.remove(pair)
            ans[pair[1]-1]=pair[0]
            flg=True
        elif pair[1] in roomto:
            roomto1.append(pair[0])
            abc.remove(pair)
            ans[pair[0]-1]=pair[1]
            flg=True
    ab=abc
    roomto1=list(set(roomto1))
    roomto=roomto1
    for r in roomto1:
        room.remove(r)


if 0 not in ans:
    for value in ans:
        print(value)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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)]
q = deque()
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])):
    c = t[0][i]
    dis[c] = 1
    near[c] = 0
    q.append(c)
while len(q) > 0:
    e = q.popleft()
    for j in range(len(t[e])):
        c = t[e][j]
        if dis[c] >= dis[e] +1:
            dis[c] = dis[e] +1
            near[c] = e
            q.append(c)
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=deque([100000000]*n)
Dis[0]=0
PP=deque([0]*n)
l=deque()
l.append(0)
while l:
    x=l.pop()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m=map(int, input().split())
g = [[] for _ in range(n + 1)]
d = deque()
ans = [0]*(n+1)

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

d = deque()
for i in g[1]: 
    d.append(i)
    ans[i]=1

while d:
    tmp = d[0]
    for j in range(n+1):
        if tmp in g[j] and ans[j]==0:
            ans[j]=tmp
            d.append(j)
    d.popleft()

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

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

N, M = map(int,input().split())
G = nx.Graph()

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

print_str = 'Yes\n'
for i in range(2, N + 1):
    ans = nx.shortest_path(G, source = i, target = 1)
    print_str += (str(ans[1]) + '\n')
        
print(print_str[:-1])

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 = []
d, p = shortest_path(neighbor, return_predecessors=True, indices=0)

for i in range(1,N):
    if p[i]<0:
        print("No")
        sys.exit(0)
    else:
        ans.append(p[i]+1)
print("Yes")
for i in range(N-1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=deque([100000000]*n)
Dis[0]=0
PP=[0]*n
l=deque()
l.append(0)
while l:
    x=l.pop()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m=map(int, input().split())
g = [[] for _ in range(n + 1)]
d = deque()
ans = [0]*(n+1)
flg = 0

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

d = deque()
for i in g[1]: 
    d.append(i)
    ans[i]=1

while flg == 0:
    tmp = d[0]
    for j in range(n+1):
        if tmp in g[j] and ans[j]==0:
            ans[j]=tmp
            d.append(j)
    d.popleft()
    if 0 not in ans[2:]:
        flg = 1

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

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
Dis=[100000000]*n
Dis[0]=0
PP=[0]*n
l=deque()
l.append(0)
while l:
    x=l.pop()
    for a in R[x]:
        if Dis[a]>Dis[x]+1:
            Dis[a]=Dis[x]+1
            l.append(a)
            PP[a]=x
for t in range(1,n):
    print(PP[t]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = map(int, read().split())
    p = []
    d1 = {}
    d2 = {}
    for i in range(m):
        a, b = map(int, read().split())
        if a == 1:
            d1[b] = 1
            d2[b] = 1
        elif b == 1:
            d1[a] = 1
            d2[a] = 1
        else:
            p.append((a, b))
    while p:
        pi = p.pop(0)
        if pi[0] in d1 and pi[1] not in d1:
            d1[pi[1]] = pi[0]
            d2[pi[1]] = d2[pi[0]] + 1
        elif pi[1] in d1 and pi[0] not in d1:
            d1[pi[0]] = pi[1]
            d2[pi[0]] = d2[pi[1]] + 1
        elif pi[0] in d1 and pi[1] in d1:
            if d2[pi[0]] > d2[pi[1]] + 1:
                d1[pi[0]] = pi[1]
                d2[pi[0]] = d2[pi[1]] + 1
            elif d2[pi[1]] > d2[pi[0]] + 1:
                d1[pi[1]] = pi[0]
                d2[pi[1]] = d2[pi[0]] + 1
        else:
            p.append(pi)
    print("Yes")
    for i in range(2, n + 1):
        print(d1[i])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
nm=list(map(int, input().split()))
n=nm[0]
m=nm[1]
ab=[]
ans=['Yes']+[0]*(n-1)
room=[i+2 for i in range(n-1)]

for i in range(m):
    ab.append(list(map(int, input().split())))

roomto=[1]
flg=True
while flg:
    roomto1=[]
    path=[]
    flg=False
    abc=ab.copy()
    for pair in ab:
        if pair[0] in roomto and pair[1] in roomto:
            abc.remove(pair)
        elif pair[0] in roomto:
            roomto1.append(pair[1])
            abc.remove(pair)
            path.append(pair)
            flg=True
        elif pair[1] in roomto:
            roomto1.append(pair[0])
            abc.remove(pair)
            path.append(pair)
            flg=True
    ab=abc
    roomto1=list(set(roomto1))
    roomto=roomto1
    for r in roomto1:
        room.remove(r)
        for pair in path:
            if r==pair[0]:
                ans[r-1]=pair[1]
            elif r==pair[1]:
                ans[r-1]=pair[0]


if 0 not in ans:
    for value in ans:
        print(value)
else:
    print('No')