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:
# D

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

adj_matrix = [[10**9] * N for i in range(N)]
for i in range(M):
    ab = list(map(int, input().split()))
    adj_matrix[ab[0]-1][ab[1]-1] = 1
    adj_matrix[ab[1]-1][ab[0]-1] = 1
 
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np
 
csr = csgraph_from_dense(adj_matrix, null_value=10**9)
from_starts, procs = dijkstra(csr, indices=[0], return_predecessors =True)
from_start = from_starts[0]
proc = procs[0]
 
if -9999 in proc[1:]:
  print('No')
else:
  print('Yes')
  for i in range(N-1):
    print(int(proc[i+1]) + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
maze=[[0]*n for i in range(n)]
for i in range(m):
    r,l=map(int,input().split())
    maze[r-1][l-1]=1
    maze[l-1][r-1]=1

stamp=[-1]*n
queue=deque([0])
while queue:
    d=queue.popleft()
    for i in range(n):
        if maze[d][i]==1 and stamp[i]==-1:
            stamp[i]=d
            queue.append(i)

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X = [ [] for j in range(N+1) ]
for i in range(M):
    a, b = map(int, input().split())
    X[a].append(b)
    X[b].append(a)

result = [0] * (N+1)
c = []
for x in X[1]:
    result[x] = 1
    c.append(x)

c_new = []
while 0 in result[2:]:
    for x in c:
        for y in X[x]:
            if result[y] == 0:
                result[y] = x
                c_new.append(y)
    c = c_new
    c_new = []

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
graph = {i: set() for i in range(N)}
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v] - visited:
        if tokens[nv] < 0:
            tokens[nv] = v
        if nv not in visited:
            q.append(nv)
if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    [print(t + 1) for t in tokens[1:]]

Submission status: Time Limit Exceeded

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

path = [list() for _ in range(M+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:
#!/usr/bin/env python3
import sys
from collections import deque


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


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

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


solve()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
P = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    P[A-1].append(B)
    P[B-1].append(A)
V = [[N,N] for i in range(N)]
V[0] = [0,0]
W = [1]
while(W):
    a = W.pop()
    p,q = V[a-1]
    while(P[a-1]):
        s = P[a-1].pop()
        if q + 1 <= V[s-1][1]:
            V[s-1] = [a,q+1]
        W.insert(0,s)
print("Yes")
for i in range(N-1):
    print(V[i+1][0])

Submission status: Time Limit Exceeded

Solution code:
n,m=(int(i) for i in input().split())
l=[[] for i in range(n+1)]
for i in range(m):
  a,b=(int(i) for i in input().split())
  l[a].append(b)
  l[b].append(a)
queue = []
visited = [] 
visited = [0 for i in range(n+1)]
ans=[None for i in range(n+1)]
queue.append([1,0])
visited[1]=1
while len(queue)>0:
  now=queue.pop(0)
  for i in l[now[0]]:
    if visited[i]==0:
      visited[i]=1
      queue.append([i,now[0]])
  ans[now[0]]=now[1]
print('Yes')
for i in range(n-1):
  print(ans[i+2])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
k=[[] for i in [0]*n]
for i in range(m):
    a,b=map(int,input().split())
    k[a-1]+=[b-1]
    k[b-1]+=[a-1]
l=[0]*n
q=[0]
p=[0]
while True:
    s=[]
    for i in p:
        r=k[i]
        for j in r:
            if not j in q:
                l[j]=i+1
                s+=[j]
                q+=[j]
    p=s
    if len(p)==0:
        break
print("Yes")
for i in l[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
graph = {i: set() for i in range(N)}
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v] - visited:
        if tokens[nv] < 0:
            tokens[nv] = v
        q.append(nv)
if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    [print(t + 1) for t in tokens[1:]]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m=INTM()
    roots=[[0]*n for i in range(n)]
    visit=[0]*n
    visit[0]=1
    q=deque([0])
    for i in range(m):
        a,b=INTM()
        roots[a-1].append(b-1)
        roots[b-1].append(a-1)
    while q:
        temp=q.popleft()
        for root in roots[temp]:
            if visit[root]!=0:
                continue
            else:
                q.append(root)
                visit[root]=temp+1
    
    print('Yes')
    for i in visit[1:]:
        print(i)
        

                
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
import queue

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

adj = [[False] * M for i in range(M)]
edge = [[] for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    edge[A - 1].append(B - 1)
    edge[B - 1].append(A - 1)
    # adj[A - 1][B - 1] = True
    # adj[B - 1][A - 1] = True

node = [-1] * N
node[0] = 0

Q = queue.Queue()
Q.put(0)

while not Q.empty():
    i = Q.get()
    for j in edge[i]:
        # if adj[i][j] == 0:
        #     continue
        if node[j] != -1:
            continue
        node[j] = i
        Q.put(j)

if any([i == -1 for i in node]):
    print('No')
else:
    print('Yes')
    for i in node[1:]:
        print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

neighbor = [[] for _ in range(n+1)]

for i in range(m):
    A, B = map(int, input().split())
    neighbor[A].append(B)
    neighbor[B].append(A)

h = []

heappush(h, (0, 1, 0))

ans = [0] * (n+1)
while h:
    step, cur, prev = heappop(h)
    if ans[cur] != 0:
        continue

    ans[cur] = prev

    for i in neighbor[cur]:
        heappush(h, (step+1, i, cur))

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

Submission status: Time Limit Exceeded

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

a, b = [], []


def dijkstra(s, n, w, cost):
    # 始点sから各頂点への最短距離
    # n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    directions = [-1] * n
    d[s] = 0
    directions[s] = s

    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]
                directions[j] = v + 1
            # d[j] = min(d[j], d[v] + cost[v][j])
    return d, directions


for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)

cost = [[float("inf") for j in range(n)] for i in range(n)]

# cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(m):
    cost[a[i] - 1][b[i] - 1] = 1
    cost[b[i] - 1][a[i] - 1] = 1

d, directions = dijkstra(0, n, m, cost)

if -1 in directions:
    print("No")
else:
    print("Yes")
    for v in directions[1:]:
        print(v)

Submission status: Time Limit Exceeded

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

import sys

input = sys.stdin.readline
R = [[]]*n
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a] = R[a] + [b]
  R[b] = R[b] + [a]
  
#print(R)

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if Dis[to]>Dis[cur]+1 or Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

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

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    path[A-1].append(B-1)
    path[B-1].append(A-1)

parent = [-1] * (N)
parent[0] = 0

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

depth = [10 ** 9] * N
depth[0] = 0

q = queue.Queue()
q.put(0)
while not q.empty():
    pos = q.get()
    possible_parent = []
    for next_room in path[pos]:
        if parent[next_room] == -1:
            if not found[next_room]:
                q.put(next_room)
                found[next_room] = True
                depth[next_room] = min(depth[next_room], depth[pos] + 1)
        else:
            possible_parent.append(next_room)

    for p1 in possible_parent:
        for p2 in possible_parent:
            if depth[p1] > depth[p2]:
                break
        else:
            parent[pos] = p1
            break

if -1 in parent:
    print("No")
else:
    print("Yes")
    for elem in parent[1:]:
        print(elem + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


N, M = map(int, input().split())
graph = {i: set() for i in range(N)}
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v] - visited:
        if tokens[nv] < 0:
            tokens[nv] = v
        q.append(nv)
if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    [print(t + 1) for t in tokens[1:]]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
li=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    li[a-1].append(b)
    li[b-1].append(a)
ans=[]
a=[0]*n
d=deque([1])
while len(d)>0:
    x=d.popleft()
    if x not in ans:
        ans.append(x)
        for v in li[x-1]:
            if v not in ans:
                d.append(v)
                if a[v-1]==0:
                    a[v-1]=x
if len(ans)==n:
    print("Yes")
    for i in range(1,n):
        print(a[i])
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = (int(x) for x in input().split())
list_load=[]
for i in range(m):
    a, b = (int(x) for x in input().split())
    list_load.append((a,b))
    list_load.append((b,a))
list_ans=[0]*n

que=deque()
que.append(1)
while que:
    now = que.pop()
    for i in list_load:
        if i[0]==now:
            next=i[1]
            if list_ans[next-1]==0:
                list_ans[next-1]=now
                que.appendleft(next)
bool = True
for i in range(1,n):
    if list_ans[i]==0:
        bool=False
if bool:
    print("Yes")
    for i in range(1,n):
        print(list_ans[i])
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
a = []
b = []
for i in range(M):
    aa, bb = list(map(int, input().split()))
    a.append(aa-1)
    b.append(bb-1)
    
table = [0] * N
ans = [0] * N

table[0] = 1


#start
q = [0]

while(q):
    
    x = q[0]
    
    for i in range(M):
        if a[i] == x and table[b[i]]==0:
            table[b[i]]=1
            ans[b[i]]=a[i]+1
            q.append(b[i])
        if b[i] == x and table[a[i]]==0:
            table[a[i]]=1
            ans[a[i]]=b[i]+1
            q.append(a[i])         
    
    q.pop(0)

if sum(table)==N:
    print("Yes")
    for i in range(1,N):
        print(ans[i])
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l2=[0]*(N-1)
for i in range(M):
   A,B= list(map(int,input().split()))
   l[A-1].append(B)
   l[B-1].append(A)
from collections import deque
que=deque([1])
after=deque()
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())
P=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  P[a][b]=b
  P[b][a]=a
#AB=[list(map(int,input().split())) for i in range(M)]
ans=[0]*N
con=set()
now=[1]
while now!=[]:
  _now=[]
  for n in now:
    for p in P[n]:
      if p>0 and p not in con:
        ans[p-1]=n
        _now.append(p)
        con.add(p)
    #con.add(n)
  now=_now
print('Yes')
for a in ans[1:]:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
n,m = (int(x) for x in input().split())

E = [[] for i in range(n+1)]

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

#print(E)   

flag = [False]*(n+1)
vs = [1]
flag[1] = True
res = [0]*(n+1)

while(vs):
    this_v = vs[0]
    for i in E[this_v]:
        if flag[i]:
            continue
        else:
            res[i] = this_v
            flag[i] = True
            vs.append(i)
    vs = vs[1:]
            
print("Yes")
for i in res[2:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline
from collections import deque

n,m = map(int,input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
ans = [-1]*n
cnt = [n]*n
def dfs(now, prev,c):
    for next in g[now]:
        if next != prev and next!=0:
          if cnt[next] > c:
            ans[next] = now+1
            cnt[next] = c
            dfs(next, now,c+1)
            
dfs(0,-1,1)

for i in ans[1:]:
  if i == -1:
    print('No')
    exit()
print('Yes')
for i in ans[1:]:
  print(i)

Submission status: Time Limit Exceeded

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

d = {}

for i in range(N):
    d[i+1] = []

for i in range(M):
    a, b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)
que = [1]
checked = set([1])
ans = [-1]*(N-1)
while que:
    now = que.pop(0)
    for h in d[now]:
        if not h in checked:
            ans[h-2] = str(now)
            checked.add(h)
            que.append(h)
    
if len(checked) == N:
    print('Yes')
    print("\n".join(ans))
else:
    print('No')

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())
rank = [300000] * n
mtrx = [[0]*n for _ in range(n)]
for i in range(m):
   a,b = map(int,input().split())
   mtrx[a-1][b-1] = 1
   mtrx[b-1][a-1] = 1
mtrx = csr_matrix(mtrx)
dij = (dijkstra(mtrx,indices=0,return_predecessors=True,directed=False))
#print(type(dij[0][3]))
if np.inf in dij[0]:
   print('No')
else:
   print('Yes')
   for i in dij[1][1:]:
      print(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)

    arrive_time = [-1] * (N + 1)
    stack = deque([0])
    arrive_time[0] = 1
    sign = [0] * N
    while stack:
        v = stack.popleft()
        if G[v]:
            for w in G[v]:
                if arrive_time[w] < 0 and not w  in stack:
                    arrive_time[w] = 1
                    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:
# 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()))
    for i in range(M):
        a = AB[2*i]
        b = AB[2*i+1]
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [-1] * (N+1)
    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if mark[current] == -1:
            mark[current] = str(prev)
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,m = na()
    path = [[] for _ in range(n)]
    ans = [0] + [-1 for i in range(n-1)]
    sumcheck = 1
    for _ in range(m):
        a,b = na()
        a -= 1
        b -= 1
        path[a] += [b]
        path[b] += [a]
    que = [0]
    while que != []:
        now = que.pop(0)
        for nxt in path[now]:
            if ans[nxt] == -1:
                ans[nxt] = now
                sumcheck += 1
                que.append(nxt)
    if sumcheck == n:
        print('Yes')
        for i in ans[1:]:
            print(i+1)
    else:
        print('No')
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
edge = [[] for k in range(n)]
for k in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

from collections import deque
def dijkstra(start, edge_list):
    """
    edge_list = [[1, 2], [0, 2], [1, 3, 0], [2]]
    start = 0
    [0, 1, 1, 2] == dijkstra(start, edge_list, n)
    """
    
    n = len(edge_list)
    dist = [int(2e9) for _ in range(n)]
    dist[start] = 0
    parents = [0 for _ in range(n)]
    stack = deque([start])
    while len(stack) != 0:
        start = stack.pop()
        next_list = edge_list[start]
        for nex in next_list:
            if dist[start] + 1 < dist[nex]:
                dist[nex] = dist[start] + 1 
                stack.append(nex)
                parents[nex] = start
                
    return dist, parents

dist, parents = dijkstra(0, edge)

if max(dist) == int(2e9):
    print("No")
else:
    print("Yes")
    for k in range(1, n):
        print(parents[k] + 1)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, M = nm()
adj = [[] for _ in range(N)]
for i in range(M):
    a, b = nm()
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


def solve():
    INF = 1 << 62
    q = collections.deque([(0, 0, -1)])
    dist = [INF] * N
    prev = [None] * N
    while q:
        l, node, pnode = q.popleft()
        if dist[node] < l:
            continue
        dist[node] = l
        prev[node] = pnode
        for nxt in adj[node]:
            if nxt != pnode and dist[nxt] > l + 1:
                q.append((l + 1, nxt, node))
    # if any(x is None for x in prev):
    #     print("No")
    #     return
    print("Yes")
    for i in range(1, N):
        print(prev[i] + 1)


if __name__ == "__main__":
    solve()

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

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

    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path


print("Yes")
for i in range(1, n):
    print(dijkstra_back(0, i, n, m, C)[-2] + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0

    q = deque([0])
    while q:
        now = q.pop()
        for next in g[now]:
            if prev[next] < 0 or dist[now] + 1 < dist[next]:
                if prev[next] < 0:
                    q.append(next)
                else:
                    q.appendleft(next)
                prev[next] = now + 1
                dist[next] = dist[now] + 1
    if all(prev[i] > 0 for i in range(1, n)):
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


if __name__ == '__main__':
    main()

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 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:
#coding: utf-8
from collections import deque
N, M = map(int, input().split())
d = [[10^6 for _ in range(N)] for _ in range(N)]
dd = {i:[] for i in range(N)}
for i in range(N):
    d[i][i] = 0
for i in range(M):
    a, b = map(int, input().split())
    dd[a-1].append(b-1)
    dd[b-1].append(a-1)
ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
queue = []
for i in range(len(dd[0])):
    queue.append([0, dd[0][i]])
queue = deque(queue)
while queue:
    q = queue.popleft()
    if visited[q[1]]:
        continue
    visited[q[1]] = True
    ans[q[1]] = q[0] + 1
    for v in dd[q[1]]:
        if not visited[v]:
            queue.append([q[1], v])
print("Yes")
print(*ans[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

INF = float('inf')
dist = [INF]*n # dfsの条件式の書き換えに注意

ans = [-1]*(n)

from functools import lru_cache
@lru_cache(None)
def dfs(now,d):
    for next_v in es[now]:
        if dist[next_v] > d+1:
            dist[next_v] = d+1
            ans[next_v] = now+1
            dfs(next_v, dist[next_v])

start = 0
dist[start]=0 #初期化
dfs(start,0)

print('Yes')
print(*ans[1:],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline
from collections import deque

n,m = map(int,input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
ans = [-1]*n
cnt = [n]*n
def dfs(now, prev,c):
    for next in g[now]:
        if next != prev:
          if cnt[next] > c:
            ans[next] = now+1
            cnt[next] = c
            dfs(next, now,c+1)
            
dfs(0,-1,1)

for i in ans[1:]:
  if i == -1:
    print('No')
    exit()
print('Yes')
for i in ans[1:]:
  print(i)

Submission status: Time Limit Exceeded

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

pathes = {i: set() for i in range(1, n + 1)}
for _ in range(m):
  ai, bi = map(int, input().split()) 
  pathes[ai].add(bi)
  pathes[bi].add(ai)

queue = [None] * n
queue[0] = 1
idx = 1

ans = [None] * n 

for i in queue:
  if idx == n:
    continue
  next_room = pathes[i] - set(queue)
  for j in next_room:
    ans[j-1] = str(i)
    queue[idx] = j
    idx += 1

ans[0] = "Yes"

print("\n".join(ans))

Submission status: Time Limit Exceeded

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

G = [[] for _ in range(N + 1)]

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

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

dist[1] = 0
q = [1]
while q.__len__():
    now = q.pop(0)
    for i in G[now]:
        if dist[i] == -1:
            q.append(i)
            dist[i] = now

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