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 collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[0] * (n+1) for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a][b] = 1
    ggg[b][a] = 1
    
  qq = deque()
  qq.append(1)
  ff[1] = 1
  
  while qq:
    a = qq.popleft()
    for b in range(1, n+1):
      if ggg[a][b] and not ff[b]:
        ff[b] = a
        qq.append(b)
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    p = []
    d1 = {}
    d2 = {}
    for i in range(m):
        a, b = map(int, input().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:
# -*- 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
				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 = input().split()
n = int(nm[0])
m = int(nm[1])

roads = []

for i in range(m):
    a = input().split()
    roads.append([int(a[0]), int(a[1])])

visited = [1]
output = [0]*(n-1)
shortest = [1]
while len(visited) < n:
    for i in range(len(shortest)):
        for k in range(len(roads)):
            if shortest[i] in roads[k]:
                t = roads[k].index(shortest[i])
                if roads[k][(t+1) % 2] not in visited:
                    shortest.append(roads[k][(t+1) % 2])
                    visited.append(roads[k][(t+1) % 2])
                    output[roads[k][(t+1) % 2] - 2] = shortest[i]

print('Yes')
for i in range(len(output)):
    print(output[i])

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

for i in range(n):
    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 queue

n,m=map(int,input().split())

G=[[] for i in range(n)]

for _ in range(m):
 y,yy=map(int,input().split())
 y-=1
 yy-=1
 G[y].append(yy)
 G[yy].append(y)

q=queue.Queue()

vis=[0]*n
mae=[-1]*n

q.put([0,0])
while q.empty()==False:
 r=q.get()
 if vis[r[0]]==1:
  continue
 vis[r[0]]=1
 mae[r[0]]=r[1]
 for v in G[r[0]]:
  q.put([v,r[0]])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int,input().split())
D = [[] for i in range(N)]

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

if [] in D:
  print("No")
  sys.exit()
else:
  print("Yes")

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

near_next = [1]

while 0 in ans[1:]:
  near = near_next
  near_next = []
  for i in near:
    for j in D[i-1]:
      if ans[j-1]==0:
        ans[j-1] = i
        if j not in near_next:
          near_next.append(j)
  
for i in ans[1:]:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[0] * (n+1) for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a][b] = 1
    ggg[b][a] = 1
    
  qq = deque()
  qq.append((1, 1))
  
  while qq:
    a, f = qq.popleft()
    for b in range(1, n+1):
      if ggg[a][b] and not ff[b]:
        ff[b] = a
        qq.append((b, a))
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)

if __name__ == '__main__':
  main()

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 = [inf for i in range(N)]
	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 ans[ii] == inf:
				ans[ii] = next
				stc.enqueue(ii)

	#print(ans)
	#print(ki)
	for i,val in enumerate(ans):
		if i == 0:
			continue
		print(val+1)

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:
import numpy as np
n,m = map(int,input().split())
sign = np.zeros(n)
road = np.zeros((m,2),dtype=np.int)
for i in range(m):
  road[i] = list(map(int,input().split()))

root = [1]
pre_root = [1]
while len(road) != 0:
  for i in range(len(pre_root)):
    f = road[np.any(road ==pre_root[i] , axis=1), :]
    g = np.where(road == pre_root[i])[0]
    for j in range(len(f)):
      for k in range(2):
        if f[j][k] != pre_root[i]:
          if sign[f[j][k]-1] not in root:
            sign[f[j][k]-1] = pre_root[i]
            root.append(f[j][k])
    road = np.delete(road, g,axis=0)
  pre_root = list(set(root)-set(pre_root))
print('Yes')
for i in range(1,len(sign)):
  if sign[i] == 0:
    print('No')
  else:
    print(int(sign[i]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())
ans = []
data1 = deque([1])
data2 = deque([])
hantei = [0]*(10**5+2)
hantei[1] = 1
for i in range(m):
    data2.append(list(map(int,input().split())))
while data1 and data2:
    i = data1.popleft()
    for k in range(len(data2)):
        a,b = map(int,data2.popleft())
        if a == i and hantei[b] == 0:
            ans.append([b,a])
            data1.append(b)
            hantei[b] = 1
        elif hantei[a] == 0 and b == i:
            ans.append([a,b])
            data1.append(a)
            hantei[a] = 1
        else:
            if hantei[a]*hantei[b] == 1:
                continue
            else:
                data2.append([a,b])
else:
    if data2:
        print("No")
    else:
        print("Yes")
        ans.sort()
        for i in ans:
            print(i[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[-1 for i in range(N)]
A[0]=0
B=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  B[a-1].append(b-1)
  B[b-1].append(a-1)
ans=[0 for i in range(N-1)]

kaisuu=0
while min(A)==-1:
  for i in range(N):
    if A[i]==kaisuu:
      for j in B[i]:
        if A[j]==-1:
          A[j]=kaisuu+1
          ans[j-1]=i+1
  kaisuu+=1

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())
d = deque()
As = [0] * m
Bs = [0] * m
Cs = [0] * (n + 1)  # 標

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


def solver(i):
    aindexs = [j for j, x in enumerate(As) if x == i]
    bindexs = [j for j, x in enumerate(Bs) if x == i]
    for aindex in aindexs:
        target = Bs[aindex]
        d.append(target)
        if Cs[target] == 0:
            Cs[target] = i
        As[aindex] = -1
        Bs[aindex] = -1
    for bindex in bindexs:
        target = As[bindex]
        d.append(target)
        if Cs[target] == 0:
            Cs[target] = i
        As[bindex] = -1
        Bs[bindex] = -1


d.append(1)

while d:
    solver(d.popleft())

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

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 room:
            roomto1.append(pair[1])
            abc.remove(pair)
            path.append(pair)
            flg=True
        elif pair[1] in roomto and pair[0] in room:
            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')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n,m = map(int,input().split())
ab = []
for _ in range(m):
    a,b = map(int,stdin.readline().split())
    ab.append([a,b])
#ここまで入力
whole = [1]
check = whole
ans = [0 for i in range(n)]
while len(whole) < n:
    part = []
    for i in check:
        dellist = []
        for j in range(len(ab)):
            c = 0
            k = ab[j]
            if k[0] == i:
                if (k[1] not in whole) and (k[1] not in part):
                    part.append(k[1])
                    ans[k[1]-1] = i
                    dellist.append(j)
            if k[1] == i:
                if (k[0] not in whole) and (k[0] not in part):
                    part.append(k[0])
                    ans[k[0]-1] = i
                    dellist.append(j)
        for i in range(len(dellist)):
            del ab[dellist[i]-i] 
    check = part[:]
    for i in part:
        whole.append(i)
print("Yes")
for i in range(1,n):
    print(ans[i])

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 = [inf for i in range(N)]
	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 ans[ii] == inf:
				ans[ii] = next
				stc.enqueue(ii)

	#print(ans)
	#print(ki)
	for i,val in enumerate(ans):
		if i == 0:
			continue
		print(val+1)



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

n,m = map(int,input().split())

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

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

q = [0]

ans = [-1]*n
ans[0] = 0
count = 1

while q:
    l = q.pop(0)
    for i in edges[l]:
        if ans[i] == -1:
            ans[i] = l
            count += 1
            q.append(i)
    if count == n:
        break

if count == n:
    print('Yes')
    for i in ans[1:]:
        print(i+1)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n , m = map(int, input().split())

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

kakutei = [1]

answer_li = [0]*n

while kakutei:
    k = kakutei.pop(0)
    for r in root[k-1]:
        if answer_li[r-1] == 0:
            kakutei.append(r)
            answer_li[r-1] = k

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
PATHS = list([tuple(map(lambda t: int(t) - 1, input().split())) for i in range(M)])

depths = [None] * N
guides = [None] * N

def func(cuurent, paths, depth):
    depths[cuurent] = depth

    next_rooms = []
    ls_ex = []

    for r1, r2 in paths:
        if r1 == cuurent or r2 == cuurent:
            if r2 == cuurent:
                cuurent, r2 = r2, r1

            if depths[r2] == None or depths[r2] > depth + 1:
                depths[r2] = depth + 1
                guides[r2] = cuurent
                next_rooms.append(r2)
        
        else:
            ls_ex.append((r1, r2))
    
    for room in next_rooms:
        func(room, ls_ex, depth + 1)

func(0, PATHS, 0)

#if not all([follow_guide(i, guides) == depths[i] for i in range(1, N)]):
if False:
    print("No")

else:
    print("Yes")

    for i in guides[1:]:#
        print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
import math
import sys

def bfs(queue, visited):
    while len(queue) > 0:
        dest = queue.popleft()
        for i in G[dest]:
            if visited[i] == -1:
                visited[i] = visited[dest] + 1
                queue.append(i)
    return visited
# k = int(input())
# s =input()
# a = list(map(int, input().split()))
n,m= map(int, input().split())
G = {} 
for i in range(m):
    x,y= map(int,input().split())
    if x not in G:
        G[x] = {y}
    else:
        G[x].add(y)
    if y not in G:
        G[y] = {x}
    else:
        G[y].add(x)

print("Yes")
visited = [-1]*(n+1)
visited[1] = 0
q = deque([1])
visited = bfs(q,visited)

deep = {}
for i,j in enumerate(visited[2:]):
    if j not in deep:
        deep[j]={i+2}
    else:
        deep[j].add(i+2)

for i in range(2,n+1):
    d = visited[i]
    if d == 1:
        print(1)
    else:
        for j in deep[d-1]:
            if j in G[i]:
                print(j)
                break

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