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:
N,M=list(map(int,input().split(" "))) # それぞれ部屋、通路の数
R=[[] for _ in range(N)] # 連結の関係、R[i]にiの関係を列挙

for m in range(M): # 各通路について
    p,c=list(map(int,input().split(" ")))
    R[p-1].append(c-1) # 連結
    R[c-1].append(p-1) # 連結
    
##### 幅優先探索
queue=[] # キュー
now=0 # 現在見ている部屋
A=[1]+[0 for _ in range(N-1)] # すでに訪れたマーク
P=[-1 for _ in range(N)] # どこから来たかを表す番号

while True:
    A[now]=1 # 訪れたマークをつける

    for rnow in R[now]: # 次の候補について
        if (rnow not in queue) and A[rnow]!=1: # キューにもないし、まだ訪れていない場合のみキューに追加
            queue.append(rnow)
            P[rnow]=now

    if len(queue)==0: # もしキューが空になったら終了
        break
    
    next=queue.pop(0) # 次の候補をゲット
    now=next # 次はその部屋へ
    
print("Yes") # Noの場合が思いつかないので、Yesと表示

for p in P[1:]: # 最後にみちしるべを表示
    print(p+1)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

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

                tmpl.remove(n)

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

ans.pop(1)

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

else:
    ans[0] = 'Yes'

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

Submission status: Time Limit Exceeded

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

a = [0] * m
b = [0] * m

graph = [[float('inf') for j in range(n)] for i in range(n)]

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


size = len(graph)
cost = [float('inf') for _ in range(size)]
visit = [0 for _ in range(size)]
before = [None for _ in range(size)]

cost[0] = 0
while True:
  min_r = float('inf')
  for i in range(size):
    if visit[i] == 0 and cost[i] < min_r:
      x = i
      min_r = cost[x]
  if min_r == float('inf'):
    break
  visit[x] = 1

  for i in range(size):
    if cost[i] > graph[x][i] + cost[x]:
      cost[i] = graph[x][i] + cost[x]
      before[i] = x

del before[0]

if (None in before):
  print('No')

else:
  print('Yes')
  for i in range(len(before)):
    print(before[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
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)
    INF = 1<<64
    mark = [INF] * (N+1)
    done = [False] * (N+1)

    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if not done[current]:
            done[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:
import networkx as nx


ichi = list(map(int,input().split()))
n = ichi[0]
m = ichi[1]

G = nx.Graph()
for i in range(n):
    G.add_node(i+1)

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

G.add_edges_from(ab)

ans = [0] * (n-1)
can = True
for i in range(2, n+1):
    try:
        path = nx.shortest_path(G, 1, i)
    except nx.NetworkXNoPath:
        can = False
        break
    ans[i-2] = path[len(path)-2]

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

AB = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

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

AB = [sorted(ab) for ab in AB]

new_places = [1]
max_N = N + 1

# https://qiita.com/redmeteor777/items/ac7a2cec6e26f2e0ddd1
def binary_search(num_list, target):
    # 「値が何番目にあるか」を確認するための変数
    ans_counter = 0
    while True:
        # 配列の中心にある値を取り出す
        middle = num_list[len(num_list) // 2]
        # 配列の左側
        left = num_list[:len(num_list) // 2]
        # 配列の右側
        right = num_list[len(num_list) // 2:]
        # 中心の値が探索値と一致したら探索終了(探索値発見)
        if middle == target:
            return True
        # 値が最後の1個になっても一致しなかったら探索終了(探索値不存在1)
        # 左の最大値 < 探索値 < 右の最小値となった場合探索終了(探索値不存在2)
        elif len(num_list) == 1 and num_list[0] != target\
                or left[-1] < target < right[0]:
            return False
        # 左の最大値より探索値が小さい場合、探索範囲を左側に絞る
        elif target <= left[-1]:
            num_list = left
        # 右の最小値より探索値が大きい場合、探索範囲を右側に絞る
        elif right[0] < target:
            ans_counter += len(left)
            num_list = right

def check(targets, waras):
    dame_num = len(waras)
    for target in targets:
        if binary_search(waras,target):
            return target
    return None

while new_places:
    tmp_places = []
    for i in range(2, max_N):
        if ans[i] == -1:
            check_ans = check(new_places, AB[i])
            if check_ans:
                ans[i] = check_ans
                tmp_places.append(i)
    new_places = tmp_places

if all(i != -1 for i in ans[2:]):
    print("Yes")
    for i in ans[2:]:
        print(i)

else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, M = map(int, input().split())

    road = [set() for _ in range(N)]
    for i in range(M):
        ai, bi = map(int, input().split())
        for j in range(1, N+1):
            if ai == j:
                road[j-1].add(bi)
            elif bi == j:
                road[j-1].add(ai)

    q = deque()
    seen = [-1 for _ in range(N)]

    q.append(1)
    seen[0] = 0
    f = 1

    while q:
        n = q.popleft()
        if f == N:
            break
        
        else:
            for next in road[n-1]:
                if seen[next-1] == -1:
                    seen[next-1] = n
                    q.append(next)
                    f += 1

    print("Yes")
    for i in seen[1:]:
        print(i)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
n,m=n1()
ab=n3(m)

ans={}
d=[0]*(n+1)
p=[1]
p2=[]
while len(ans)<n-1:
    for c in p:
        d[c]=1
        for a,b in ab:
            if a==c and d[b]==0:
                p2.append(b)
                d[b]=1
                ans[b]=a
            if b==c and d[a]==0:
                p2.append(a)
                d[a]=1
                ans[a]=b
    p=p2.copy()
    p2=[]

A=list(ans.items())
A.sort(key=lambda x:x[0])
print("Yes")
for line in A:
    print(line[1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
L = [[0] * N for i 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
ans = [0] * N
from collections import deque
q = deque()
for i in range(N):
    if L[0][i] == 1:
        ans[i] = 1
        q.append(i)
while True:
    if len(q) == 0:
        break
    else:
        k = q.popleft()
        for i in range(1,N):
            if L[k][i] == 1:
                if ans[i] == 0:
                    ans[i] = k+1
                    q.append(i)
flag = True
for i in range(1,N):
    if ans[i] == 0:
        flag = False
        print('No')
        break
if flag == True:
    print('Yes')
    for i in range(N-1):
        print(ans[i+1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    N,M = map(int,input().split())
    G = [deque([]) for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        
    stack = deque([0])
    sign = [0] * N
    while stack:
        v = stack.popleft()
        if G[v]:
            for w in G[v]:
                if sign[w] == 0 and not w in stack:
                    sign[w] = v+1
                    stack.append(w)   
    
    sign = sign[1:]
    if all(s > 0 for s in sign):
        print('Yes')
        for s in sign:
            print(s)
    else:
        print('No')
        
main()

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split()]
l = {}
for i in range(M):
    a,b = [int(j) for j in input().split()]
    a -= 1
    b -= 1
    if a in l:
        l[a].append(b)
    else:
        l[a] = [b]
    if b in l:
        l[b].append(a)
    else:
        l[b] = [a]
ans = [10**8] * N

v = []
num = 0

def search(idx, num):
    if ans[idx] > num:
        ans[idx] = num
    for i in l[idx]:
        if ans[i] < num + 1:
            continue 
        v.append(i)

search(0,0)

for i in range(N-1):
    a = v
    v = []
    num += 1
    for j in a:
        search(j, num)

ret = []
for i in range(1,N):
    for j in l[i]:
        if ans[j] == ans[i] - 1:
            ret.append(j+1)
            break

if len(ret) == N - 1:
    print("Yes")
    for i in ret:
        print(i)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
#N = int(input())
#J,K = map(int,input().split())
#A = list(map(int,input().split()))
#A = [list(map(int,input().split())) for _ in range(N)]
#for i in range():

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
length = len(AB)
ans = [0]*(N-1)
seek = [1]
seeknext = [0]
while length > 0:
    i = 0
    delete = 0
    while i < length:
        if AB[i][0] in seek:
            if ans[AB[i][1]-2] == 0:
                ans[AB[i][1]-2] = AB[i][0]
            seeknext += [AB[i][1]]
            AB = AB[:i]+AB[i+1:]
            length-=1
        elif AB[i][1] in seek:
            if ans[AB[i][0]-2] == 0:
                ans[AB[i][0]-2] = AB[i][1]
            seeknext += [AB[i][0]]
            AB = AB[:i]+AB[i+1:]
            length-=1
        else:
            i += 1
    seek = seeknext
    seeknext = [0]
print("Yes")
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
way = []
for i in range(M):
    a_,b_ = map(int,input().split())
    a,b = min(a_,b_), max(a_,b_)
    way.append([a,b])

ans = [0] * N
ans[0] = 1
check = [False] * N
check[0] = True
l = [1]

inf = 10**9
for j in range(inf):
    m = []
    for k in l:
        for i in range(len(way)):
            if k in way[i]:
                numls = [j for j in way[i] if j != k]
                num = numls[0]
                if check[num-1]:
                    continue
                else:
                    m.append(num)
                    ans[num-1] = k
                    check[num-1] = True
    if m == []:
        break
    else:
        l = m

if False in check:
    print("No")
else:
    print("Yes")
    print(*ans[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

line = []

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

# print(line)

line = np.array(line)

ans=[0 for i in range(n)]
target=[1]

for j in range(n):
    # print(target)
    next_target=[]
    for i in target:
        a = line[np.any(line == i, axis=1)]
        for b in list(a):
            if b[0] == i:
                c = b[1]
            else:
                c = b[0]
            if ans[c-1]==0:
                ans[c-1]=i
            next_target.append(c)
        line = line[~np.any(line == i, axis=1)]
        # print(line)
        # print(next_target)
    target = next_target
    if line==[]:
        break

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(M)]
print("Yes")
ans = [0] * (N-1)
current = [1]
next_room = []

while ans.count(0) != 0:
    for c in range(len(current)):
        for m in range(len(a)):
            if current[c] in a[m]:
                if a[m][0] == current[c]:
                    if ans[a[m][1]-2] == 0:
                        ans[a[m][1]-2] = current[c]
                        next_room.append(a[m][1])
                else:
                    if ans[a[m][0]-2] == 0:
                        ans[a[m][0]-2] = current[c]
                        next_room.append(a[m][0])

    current = list(set(next_room))
[print(x) for x in ans]

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
connections = [list(map(int, input().split())) for _ in range(m)]
weights = [2e5 + 10] * n
weights[0] = 1
directions = [1] * n
for con in connections:
    if con[0] > con[1]:
        tmp = con[0]
        con[0] = con[1]
        con[1] = tmp
connections.sort()
for i in range(1, m + 1):
    c_ = connections
    for con in c_:
        r1 = con[0]
        r2 = con[1]
        w1 = weights[r1 - 1]
        w2 = weights[r2 - 1]
        if w1 < 2e5 + 10 and w1 + 1 < w2:
            weights[r2 - 1] = w1 + 1
            directions[r2 - 1] = r1
        if w2 < 2e5 + 10 and w2 + 1 < w1:
            weights[r1 - 1] = w2 + 1
            directions[r1 - 1] = r2
        if r1 == i:
            connections = connections[1:]

if max(weights) > 2e5 + 5:
    print("No")
else:
    print("Yes")
    for d in directions[1:]:
        print(d)

Submission status: Time Limit Exceeded

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

a = [0] * m
b = [0] * m

graph = [[float('inf') for j in range(n)] for i in range(n)]

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



size = len(graph)
cost = [float('inf') for _ in range(size)]
visit = [0 for _ in range(size)]
before = [None for _ in range(size)]

cost[0] = 0
while True:
  min_r = float('inf')
  for i in range(size):
    if visit[i] == 0 and cost[i] < min_r:
      x = i
      min_r = cost[x]
  if min_r == float('inf'):
    break
  visit[x] = 1

  for i in range(size):
    if cost[i] > graph[x][i] + cost[x]:
      cost[i] = graph[x][i] + cost[x]
      before[i] = x

i = size - 1
optimum_route = []
while True:
  optimum_route.insert(0, i)
  if i == 0:
    break
  i = before[i]

del before[0]

if (None in before):
  print('No')

else:
  print('Yes')
  for i in range(len(before)):
    print(before[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

tmp = list(map(int, input().split()))
N, M = tmp[0], tmp[1]
A = []
B = []
for i in [0]*M:
    tmp = list(map(int, input().split()))
    A.append(tmp[0])
    B.append(tmp[1])

arranged = [[1]]
nextroom = []
ans = [0]*(N-1)
for j in [0]*M:
    flattenarr = sum(arranged, [])
    for i in range(M):
        for rooms in arranged:
            if A[i] in rooms and B[i] not in flattenarr:
                nextroom.append(B[i])
                if ans[B[i]-2] == 0:
                    ans[B[i]-2]=A[i]
                break

            if B[i] in rooms and A[i] not in flattenarr:
                nextroom.append(A[i])
                if ans[A[i]-2] == 0:
                    ans[A[i]-2]=B[i]
                break
    arranged.append(nextroom)
    nextroom = []

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

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][b]=1
    edge[b][a]=1

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    while len(q):
        if now==p:
            continue
        now, p, d = q.popleft()
        if visited[now]==0:
            ans[now]=p+1
            dis[now]=d+1
            visited[now]=1
            for i in range(n):
                if edge[now][i]==1 and visited[i]==0:
                    q.append((i, now, dis[now]))
                    
                    visited[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:
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 = []
    for c in check:
        a = list(child[c] & all_)
        ans[c] = a
        checkk += a
        all_ = all_ - child[c]
    check = list(set(checkk))
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)

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
a = [[0] * N for _ in range(N)]

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

a = np.array(a)
a, b = shortest_path(a, return_predecessors=True)

if -1 in np.sign(b[0][1:]):
    print('No')
    exit()

print('Yes')

print(*b[0][1:]+1, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, M = map(int, input().split())
# 文字列の入力
#s = input()
#開業されたN個要素を受け付ける
#list = [input() for i in range(N)]
input_list = [list(map(int, input().split())) for i in range(M)]
flg = [0 for i in range(N)]

#print(input_list)
#print(flg)

flg[0] = 1
ans_list = [0 for i in range(N)]
now_depth = [1]
depth = 1

while(0 in flg):
    #print(depth)
    #print(now_depth)
    #print(input_list)
    next_depth = []
    for i in now_depth:
        j = 0
        while j < len(input_list):
            #print(input_list)
            if i in input_list[j]:
                if input_list[j][0] == i:
                    if flg[input_list[j][1]-1] == 0:
                        flg[input_list[j][1]-1] = 1
                        ans_list[input_list[j][1]-1] = i
                        next_depth.append(input_list[j][1])
                        #input_list.pop(j)
                        #continue
                elif input_list[j][1] == i:
                    if flg[input_list[j][0]-1] == 0:
                        flg[input_list[j][0]-1] = 1
                        ans_list[input_list[j][0]-1] = i
                        next_depth.append(input_list[j][0])
                        #input_list.pop(j)
                        #continue
                input_list.pop(j)
                continue
            j = j+1
            #print("len:"+str(len(input_list))+", j:"+str(j))
    depth = depth+1
    now_depth = next_depth
#print(now_depth)
#print(input_list)
print("Yes")
for i in ans_list:
    if not i == 0:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque
n,m=LI()
edge=[[]*n for i in range(n)]
for i in range(m):
    a,b=LI()
    a-=1;b-=1
    edge[a].append(b)
    edge[b].append(a)

ans=[-1]*n
goal=deque([0])
while (-1 in ans):
    g=goal.popleft()
    for i,v in enumerate(edge):
        if v==-1:continue
        if g in v:
            ans[i]=g+1
            edge[i]=-1
            goal.append(i)

if (-1 in ans):
    no()
    exit()
yes()
for i in ans[1:]:
    print(i)

Submission status: Time Limit Exceeded

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


n, m = map(int, input().split())
path = list(list(map(int, input().split())) for _ in range(m))

dic = dict()
for i in range(m):
    p = path[i]
    if p[0] not in dic:
        dic[p[0]] = [p[1]]
    else:
        dic[p[0]].append(p[1])
    if p[1] not in dic:
        dic[p[1]] = [p[0]]
    else:
        dic[p[1]].append(p[0])
        
table = [0]*n
sign = [0]*n

def bfs(k):
    for i in dic[k]:
        if table[i-1] == 0 and i != 1:
            table[i-1] = table[k-1] + 1
            sign[i-1] = k
        elif table[k-1] + 1 < table[i-1]:
            table[i-1] = table[k-1] + 1
            sign[i-1] = k
        else:
            continue
        bfs(i)
    return

bfs(1)

print("Yes")
for i in range(n-1):
    print(sign[i+1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

NM = [int(x) for x in input().split()]
M=[]
for i in range(NM[1]):
  M.append([int(x) for x in input().split()])

X=np.zeros(NM[0])
Y=np.zeros(NM[0])
target=1
list_target={0:1}
list_target_d={0:1}
for i in range(NM[1]):
  for j in range(NM[1]):
    for k in range(2):
      if M[j][k] in list_target.values() and not M[j][k-1] in list_target.values():
        target=M[j][k-1]
        X[target-1]=i+1
        Y[target-1]=M[j][k]
        list_target_d[len(list_target_d)]=target
  list_target.update(list_target_d)
if np.count_nonzero(X ==0)>2:
  print("No")
else:
  print("Yes")
  for i in range(1,NM[0]):
    print(int(Y[i]))
    
"""
6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6
Yes
6
5
5
1
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)
    to_visit = deque((1,))
    visited = set()
    distances = defaultdict(lambda: sys.maxsize)
    distances[1] = 0
    while to_visit:
        cur = to_visit.popleft()
        for neighbour in passages[cur]:
            distances[neighbour] = min(distances[neighbour], distances[cur] + 1)
            if neighbour not in visited:
                to_visit.append(neighbour)
        visited.add(cur)
    # LOG.debug((visited, to_visit))
    if len(visited) < n:
        return []
    result = []
    for i in range(2, n + 1):
        found = 1
        min_dist = sys.maxsize
        for neighbour in passages[i]:
            if distances[neighbour] < min_dist:
                found = neighbour
                min_dist = distances[neighbour]
        if min_dist == sys.maxsize:
            return []
        result.append(found)
    return result


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