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
N,M=map(int,input().split())
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)
  
visited=[0]*N
d = deque()
ans=[-1]*N
d.append(0)
while d:
  c=d.popleft()
  visited[c]=1
  for e in B[c]:
    if visited[e]:
      continue
    if e in d:
      continue
    
    d.append(e)
    ans[e]=c
    
print("Yes")
for i in range(1,N):
  print(ans[i]+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
a = [[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

for i in range(N):
    if 1 not in a[i]:
        print('No')
        exit()


print('Yes')

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

for i in b[0][1:]:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
INF         = 10000
VISITED     = 1
NOT_VISITED = 0

N, M = map(int, input().split())
route = [[INF for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    route[a-1][b-1] = 1
    route[b-1][a-1] = 1

size = len(route)
cost = [INF for _ in range(size)]
visit = [NOT_VISITED for _ in range(size)]
before = [None for _ in range(size)]
cost[0] = 0
while True:
    min = INF
    for i in range(size):
        if visit[i] == NOT_VISITED and cost[i] < min:
            x = i
            min = cost[x]
    if min == INF:
        break
    visit[x] = VISITED
 
    for i in range(size):
        if cost[i] > route[x][i] + cost[x]:
            cost[i] = route[x][i] + cost[x]
            before[i] = x

ans = [-1 for _ in range(size)]
for i in range(1, size):
    point = i
    to = before[point]
    while True:
        if to == 0:
            ans[point] = 0
            break
        elif ans[point] != -1 and to != ans[point]:
            print("No")
            sys.exit()
        ans[point] = to
        point = to
        to = before[point]

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

Submission status: Time Limit Exceeded

Solution code:
import copy

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

path = [None] + [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    path[a].append(b)
    path[b].append(a)

min_ds = [None] + [-1 for _ in range(N)]
min_paths = [None] + [[] for _ in range(N)]

queue = []
for n in path[1]:
    queue.append((n, 1, {1}, [1]))

while queue:
    c, d, pathed, p = queue.pop(0)

    if min_ds[c] == -1:
        min_ds[c] = d
        min_paths[c] = p
    else:
        if min_ds[c] > d:
            min_ds[c] = d
            min_paths[c] = p

    pathed_ = copy.copy(pathed)
    pathed_.add(c)
    for n in path[c]:
        if n not in pathed:
            queue.append((n, d + 1, pathed_, p + [c]))

for d in min_ds[2:]:
    if d == -1:
        print('No')
        quit(0)

print('Yes')
for p in min_paths[2:]:
    print(p[-1])

Submission status: Time Limit Exceeded

Solution code:
import copy

n,m = map(int,input().split())
a = [[int(i) for i in input().split()] for j in range(m)]
ans=[0 for i in range(n-1)]
now=[1]
tmp=[]
while 0 in ans:
    for i in now:
            for j in a:
                if i ==j[0] and ans[j[1]-2]==0:
                    tmp.append(j[1])
                    ans[j[1]-2]=i
                if i==j[1] and ans[j[0]-2]==0:
                    tmp.append(j[0])
                    ans[j[0]-2]=i
    now=copy.copy(tmp)
    tmp=[]
print("Yes")
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush

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

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

    d, m = dijkstra(0, N, E)
    # print(d, m)
    print("Yes")
    for i in range(1,N):
      print(m[i]+1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

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

g = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append(b)
  g[b].append(a)#番号を修正。0スタートに。
#print(g)  
reach = [0 for _ in range(N)] #0からの距離を記録。0未到達。
par = [-1 for _ in range(N)] #親の位置を記録

def dfs(v):
  #reach[v] = 1 #今の点は到達した。これいるかな？
  for i in range(len(g[v])): #点vから行ける点をすべて探索
    u = g[v][i] #今探索している点
    if u == 0:
      continue
    if reach[u] != 0:
      if reach[u] > reach[v] + 1: #距離が近ければ更新
        reach[u] = reach[v] + 1
        par[u] = v
        dfs(u)
      else:
        continue
    reach[u] = reach[v] + 1 #探索中の点の到達を記録。
    par[u] = v
    dfs(u)

dfs(0)
#print(reach,par)
if 0 not in reach[1:]:
  print("Yes")
  for i in range(1,N):
    ans = par[i]+1
    print(ans)
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s, n, w, cost):
    d = [float('inf')] * n
    used = [False] * n
    d[s] = 0
    x = [-1] * n
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
               
        for j in range(n):
            if d[j] > d[v]+cost[v][j]:
                d[j] = d[v]+cost[v][j]
                x[j] = v
    return d, x

n, m, *AB = map(int, open(0).read().split())
cost = [[10**9]*n for _ in range(n)] 
for a, b in zip(AB[::2], AB[1::2]):
    cost[a-1][b-1] = cost[b-1][a-1] = 1
d, p = dijkstra(0, n, m, cost)
if any(x > 10**9-1 for x in d):
    print('No')
else:
    print('Yes')
    print(*map(lambda x: int(x)+1, p[1:]), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    global ans 
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
               if min(d[j],d[v]+cost[v][j]) == d[v]+cost[v][j]:
                ans[j] = v+1
    return d

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 
ans = [0]*n
for i in range(w):
    x,y = map(int,input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
dijkstra(0,n,w,cost)
print("Yes")
for i in range(1, n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n, m = Is()
AB = TIR(m)
C = [[INF]*n for _ in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    C[a][b] = 1
    C[b][a] = 1

# ANS = [INF]*n

#
# def dijkstra(s, n, w, cost):
#     # 始点sから各頂点への最短距離
#     # n:頂点数, w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
#     d = [float("inf")] * n
#     used = [False] * n
#     d[s] = 0
#
#     while True:
#         v = -1
#         # まだ使われてない頂点の中から最小の距離のものを探す
#         for i in range(n):
#             if (not used[i]) and (v == -1):
#                 v = i
#             elif (not used[i]) and d[i] < d[v]:
#                 v = i
#         if v == -1:
#             break
#         used[v] = True
#
#         for j in range(n):
#             d[j] = min(d[j], d[v] + cost[v][j])
#     return d

# print(dijkstra(0, n, m, C))

def dijkstra_back(s, t, n, w, cost):
    # sからtへの最短経路の経路復元
    prev = [s] * n  # 最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for i in range(n):
            if d[i] > d[v] + cost[v][i]:
                d[i] = d[v] + cost[v][i]
                prev[i] = v

    return prev

ANS = dijkstra_back(0, n-1, n, m, C)[1:]
print("Yes")
for ans in ANS:
    print(ans+1)


# for i in range(n):
#     if ANS[i] != INF:
#         continue
#     path = dijkstra_back(0, i, n, m, C)
#     for j, x in enumerate(path):
#         if j == 0:
#             continue
#         else:
#             ANS[x] = path[j-1]
#
# print("Yes")
# for ans in ANS[1:]:
#     print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M = map(int, readline().split())
graph = [[0] * N for _ in range(N)]
for i in range(M):
    A, B = map(int1, readline().split())
    graph[A][B] = 1
    graph[B][A] = 1
ans = [None] * (N)

visited = [False] * N
visited[0] = True

que = deque([0])

while len(que) > 0:
    acc = que.popleft()
    for i, pos in enumerate(graph[acc]):
        if pos == 0 or visited[i]:
            continue

        ans[i] = acc + 1
        visited[i] = True
        que.append(i)

if sum(visited) == len(visited):
    print("Yes")
    for sign in ans[1:]:
        print(sign)
else:
    print("No")

Submission status: Time Limit Exceeded

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


from collections import defaultdict
display_num = defaultdict(int)
move_num = defaultdict(int)
connection = defaultdict(lambda: defaultdict(int))
def_room = defaultdict(int)

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

c = defaultdict(int)
d = defaultdict(lambda: 10**10)
p = defaultdict(lambda: -1)
d[0] = 0
p[0] = -1

while True:
  mincost = 10**10
  for i in range(N):
    if c[i] != 2 and d[i] < mincost:
      mincost = d[i]
      u = i
  if mincost == 10**10:
    break
  c[u] = 2
  for v in range(N):
    if c[v] != 2 and connection[u][v] == 1:
      if d[u] + 1 < d[v]:
        d[v] = d[u] + 1
        p[v] = u
        c[v] = 1
print("Yes")
for i in range(1,N):
  print(p[i] + 1)

Submission status: Time Limit Exceeded

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

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

import copy

for i in range(N):
  Z[i][i]=-1

for i in X:
  Z[i[0]-1][i[1]-1]=1
  Z[i[1]-1][i[0]-1]=1

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
d = {}
for _ in range(M):
    A, B = map(int, input().split())
    if A not in d:
        d[A] = [B]
    else:
        d[A].append(B)
    if B not in d:
        d[B] = [A]
    else:
        d[B].append(A)

ans = [(-1, float("inf"))] * N
cnt = 0
stack = [(1, 0)]
while stack:
    val, step = stack.pop()
    next_vals = d[val]
    for nxt in next_vals:
        if ans[nxt - 1][1] > step + 1:
            if ans[nxt - 1][0] == -1:
                cnt += 1
            ans[nxt - 1] = (val, step + 1)
            stack.append((nxt, step + 1))

if cnt < N - 1:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i][0])

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

next = [1]
reached = {0:-1}
fromnode = {}

N,M = nm()
# print(N,M)
tunnel = [{} for i in range(N+1)]
# print(tunnel)
for _ in range(M):
    a,b = nm()
    # print(a,b)
    tunnel[a][b] = 1
    tunnel[b][a] = 1
# print(tunnel)

d = 0
while len(next) != 0:
    # print(d,next,reached,fromnode)
    now = next
    next = []
    for node in now:
        reached[node] = d
    for node in now:
        for nn in tunnel[node]:
            # print('check',nn)
            if not (nn in reached):
                fromnode[nn] = node
                next.append(nn)
    d += 1

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m=map(int,input().split())
    ab = {}
    for _ in range(m):
        a,b=map(int,input().split())
        ab.setdefault(a,[]).append(b)
        ab.setdefault(b,[]).append(a)
    result = [None] * n
    result[0] = (-1, 0)
    d = 0
    while ab:
        for i,t in enumerate(result):
            if t and t[1] == d:
                if i+1 in ab:
                    for k in ab[i+1]:
                        if not result[k-1]:
                            result[k-1] = (i+1,d+1)
                    del ab[i+1]
        d+=1
    if None in result:
        print('No')
        return
    print('Yes')
    for i in range(1,n):
        print(result[i][0])

main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
 
path = [list() for _ in range(N+1)]
mark = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
    
queue = []
order = []
queue.append(0)    
order.append(0)
 
while queue:
    v = queue.pop(0)
    for w in path[v]:
        if w not in order:
            order.append(w)
            queue.append(w)
            mark[w] = v+1
mark = mark[1:]
if len(order)<N:
    print ("No")
else:
    print ("Yes")
    for i in range(len(mark)):
        print (mark[i])

Submission status: Time Limit Exceeded

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

G = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
    
ans = [-1 for _ in range(N)]
ans[0] = 1
count = 1

stack = [0]

while stack:
    if count == N:
        break
    j = stack.pop(0)
    for i in G[j]:
        if ans[i] == -1:
            ans[i] = j
            stack.append(i)
            count += 1
            
if count != N:
    print("No")
        
else:
    print("Yes")            
    for i in range(1, N):
        print(ans[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for i in range(M)]

    from collections import deque

    search = deque([1])
    visited = set([])
    before = [0] * (N-1)
    while search:
        s = search.popleft()
        visited.add(s)
        for a, b in AB:
            if s == a:
                new_s = b
            elif s == b:
                new_s = a
            else:
                continue
            if new_s in visited:
                continue
            if new_s in search:
                continue

            search.append(new_s)
            # visited.add()
            before[new_s-2] = s
        # print("search", search)
        # print(before)
    if 0 in before:
        print('No')
    else:
        print('Yes')
        for b in before:
            print(b)
    # from scipy.sparse import csgraph, csr_matrix
    # import numpy as np

    # start = [0] * M
    # end = [0] * M
    # cost = [1]*M
    # for i in range(M):
    #     start[i] = AB[i][0]-1
    #     end[i] = AB[i][1]-1
    # csr = csr_matrix((cost, (start, end)), shape=(N, N))

    # d, p = csgraph.dijkstra(csr, return_predecessors=True,
    #                         indices=[0], directed=False)
    # if np.any(d == np.inf):
    #     print('No')
    # else:
    #     print('Yes')
    #     for i in range(1, N):
    #         print(get_path(0, i, p)[-2]+1)


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]


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools as iter
import math as m
from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = []
    for _ in range(M):
        R.append(list(map(int, input().split())))
    
    q = deque()
    s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        s.add(x)
        for i in R:
            if i[0] == x and i[1] not in s and i[1] not in q:
                if r[i[1]] == 0:
                    r[i[1]] = i[0]
                q.append(i[1])
            if i[1] == x and i[0] not in s and i[0] not in q:
                if r[i[0]] == 0:
                    r[i[0]] = i[1]
                q.append(i[0])
        #print(r)
    #print(len(s))
    if len(s) == N:
        print("Yes")
        for i in r[2:]:
            print(i)
    else:
        print("No")
    
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# print(edge)
queue = [(e, 1) for e in edge[1]]
while sum(reached.values()) < n-1:
    # print(queue)
    e, now = queue.pop(0)
    if reached[e] == 0:
        reached[e] = 1
        guide[e] = now
        for next in edge[e]:
            if next != 1 and reached[next] == 0:
                queue.append((next, e))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

def solve(N, M, paths):
    used = [False for _ in range(M)]
    stack = deque([1])
    ret = [[float("inf"), -1] for _ in range(N + 1)]
    ret[1] = [0, 1]

    while stack:
        cur = stack.popleft()
        nexts = paths[cur]
        for n in nexts:
            if used[n[0]]:
                continue
            used[n[0]] = True
            stack.append(n[1])
            if ret[cur][0] + 1 < ret[n[1]][0]:
                ret[n[1]] = [ret[cur][0] + 1, cur]

    print("Yes")
    for r in ret[2:]:
        print(r[1])

if __name__ == "__main__":
    N, M = map(int, input().split())
    paths = defaultdict(list)
    for idx in range(M):
        a, b = map(int, input().split())
        paths[a].append([idx, b])
        paths[b].append([idx, a])

    solve(N, M, paths)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
A = []
B = []
for _ in range(m):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

print("Yes")

ans = [0]*(n-1)
temp = [1]
while True:
    if 0 not in ans:
        break
    else:
        for i in temp:
            Ai = [a for a in range(m) if A[a] == i]
            Bi = [b for b in range(m) if B[b] == i]
            for j in Ai:
                if ans[B[j]-2] == 0:
                    ans[B[j]-2] = i
                    temp.append(B[j])
            for j in Bi:
                if ans[A[j]-2] == 0:
                    ans[A[j]-2] = i
                    temp.append(A[j])
        temp.pop(0)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
  a+=[list(map(int,input().split()))]
l=sorted(a)
print('Yes')
b=[[n+1,0]for i in range(n)]
b[0][0]=0
while len(l)>0:
  a=l[0]
  #print(a,b)
  if b[a[0]-1][0]==b[a[1]-1][0]:
    if b[a[0]-1][0]==n+1:
      l+=[a]
  elif b[a[0]-1][0]>b[a[1]-1][0]:
    b[a[0]-1][0]=b[a[1]-1][0]+1
    b[a[0]-1][1]=a[1]
  else:
    b[a[1]-1][0]=b[a[0]-1][0]+1
    b[a[1]-1][1]=a[0]
  del l[0]
for i in range(1,n):
  print(b[i][1])
#print(b)

Submission status: Time Limit Exceeded

Solution code:
import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}

while queue:
    cost, cur = queue.pop()
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.append((next_cost, next_cur))

del results[0]

is_no = False
for k, result in results.items():
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for k, result in results.items():
        print(result[1] + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
n,m=map(int,input().split())
g = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = [(0,-1)]
d=[-1]*n
d[0]=0
res={}
while q:
    u,r = q.pop(0)
    for v in g[u]:
        if d[v] == -1 and r != v:
            d[v] = d[u] + 1
            q.append((v,u))
            if not v-1 in res:
                res[v-1] = u+1
res = sorted(res.items())
if len(res) != n-1:
    print("No")
    exit()
print("Yes")
for i,j in res:
    print(j)

Submission status: Time Limit Exceeded

Solution code:
import sys

# class Node:
#     def __init__(self, n, N):
#         self.id = n
#         self.edges = []
#         self.dist = 2*10**5
#         self.nroom = -1

#     def set_edge(self, e):
#         self.edges.append(e)    
    
#     def set_dist(self, e, i):
#         if e < self.dist:
#             self.dist = e
#             self.nroom = i


from heapq import *

def dijkstra(start,node,edge):
    d = [float("inf")] * node
    m = [0]*node
    d[start] = 0
    #スタートをキューに入れる
    q = [0]
    heapify(q)
    
    while(len(q) != 0):
      i = heappop(q)
    #   print(i)  
      for j in edge[i]:
        if(d[j] > d[i] + 1):
          d[j] = d[i] + 1
          heappush(q, j)
          m[j] = i
    return d, m

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

    d, m = dijkstra(0, N, E)
    # print(d, m)
    print("Yes")
    for i in range(1,N):
      print(m[i]+1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

n, m = map(int, input().split())
dic = collections.defaultdict(lambda:[])
for _ in range(m):
  a, b = map(int, input().split())
  dic[a].append(b)
  dic[b].append(a)
  
ans = [None] * n
bfs = [(1,0)]
visited = set()
get = 0
while bfs and get < n:
  now, prev = bfs.pop(0)
  if now in visited:
    continue
  visited.add(now)
  get += 1
  if ans[now-1] == None:
    ans[now-1] = prev
  for next in dic[now]:
    if next not in visited:
      bfs.append((next, now))
      
print('Yes')  
for i in range(1, n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = [int(x) for x in input().split()]
INF = 10**9
dist = [INF] * N
ans = [-1] * N
to = [set() for _ in range(N)]
for _ in range(M):
    A, B = [int(x)-1 for x in input().split()]
    to[A].add(B)
    to[B].add(A)
bfs = deque([(0, 0, -1)])
while len(bfs):
    cur, d, p = bfs.popleft()
    if d < dist[cur]:
        dist[cur] = d
        ans[cur] = p
    for v in to[cur]:
        if d+1 < dist[v]:
            bfs.append((v, d+1, cur))
    d += 1
print('Yes')
for a in ans[1:]:
    print(a+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import breadth_first_tree
from scipy.sparse import csr_matrix
N, M = map(int,input().split())
l = [[0]*(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

csr = csr_matrix(l)
Tcsr = breadth_first_tree(csr, 0, False)

if int(np.sum(Tcsr)) != N-1:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(np.dot(Tcsr.toarray().T.astype(int), np.arange(N)+1)[i])

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(v) for v in input().split(" ")]

paths = []
for i in range(M):
  paths.append([int(v) - 1 for v in input().split(" ")])
  
marks = [-1 for _ in range(N)]
hops = [999999999999999999999999999 for _ in range(N)]
marked = [0]
marks[0] = 0
hops[0] = 0

hops_prev = sum(hops)
while True:
  for path_index in range(M):
    path = paths[path_index]
    if path[0] in marked and path[1] in marked:
      continue
    
    for path in [(path[0], path[1]), (path[1], path[0])]:
      hop_ = hops[path[1]]
      hop = hops[path[0]] + 1
      if hop_ > hop:
        marks[path[1]] = path[0]
        hops[path[1]] = hop
        
        if path[0] in marked:
          marked.append(path[0])
        
  if hops_prev == sum(hops):
    break
  else:
    hops_prev = sum(hops)
     

if min(hops) >= 999999999999999999999999999:
  print("No")
else:
  print("Yes")
  [print(v+1) for v in marks[1:]]

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

next = [1]
reached = {0:-1}
fromnode = {}

N,M = nm()
# print(N,M)
tunnel = [{} for i in range(N+1)]
# print(tunnel)
for _ in range(M):
    a,b = nm()
    # print(a,b)
    tunnel[a][b] = 1
    tunnel[b][a] = 1
# print(tunnel)

d = 0
while len(next) != 0:
    # print(d,next,reached,fromnode)
    now = next
    next = []
    for node in now:
        reached[node] = d
    for node in now:
        for nn in tunnel[node]:
            # print('check',nn)
            if not (nn in reached):
                fromnode[nn] = node
                next.append(nn)
    d += 1

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