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:
#! /usr/bin/env python3
# -*- coding:utf-8 -*-
from collections import deque

def get_route(pathways, routes, visited, start):
    queue = deque([start])
    while queue:
        now = queue.popleft()
        visited[now-1] = True
        for src, dest in filter(lambda x:x[0] == now and routes[x[1]-1] == 0, pathways):
            routes[dest-1] = now
            queue.append(dest)
    return routes

def main():
    N, M = map(int, input().split())
    pathways = []
    for _ in range(M):
        A, B = map(int, input().split())
        pathways.append([A, B])
        pathways.append([B, A])
    ans_route = get_route(pathways, [0] * N, [False] * N, 1)
    if 0 in ans_route: print("No")
    else:
        print("Yes")
        for x in ans_route[1:]: print(x)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

from collections import deque






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

ab_list = [list(map(int,input().split())) for _ in range(m)]

ab_count = {key:[] for key in range(1,n+1)}

for i in range(m):
    ab_count[ab_list[i][0]].append(ab_list[i][1])
    ab_count[ab_list[i][1]].append(ab_list[i][0])


#print(ab_count)

que = deque()

#始点は1、階層は0からスタート
que.append([1,0])

checked_dict = {key:[] for key in range(1,n+1)}
temp_dict = {key:[] for key in range(1,n+1)}
where = 0

while que:
    x_pop = que.popleft()
    x = x_pop[0]
    if where != x_pop[1]:
        #階層が代わったから、temp_dictをchecked_dictへ反映させる処理
        for k in range(1,n+1):
            if len(checked_dict[k]) == 0:
                checked_dict[k] = temp_dict[k]
            elif set(checked_dict[k]) & set(temp_dict[k]) != set():
                checked_dict[k] = list(set(checked_dict[k]) & set(temp_dict[k]))

    
    where = x_pop[1]

    for j in ab_count[x]:
        if len(checked_dict[j]) == 0:
            #OK,temp_dictに入れて、queに入れる。
            temp_dict[j].append(x)
            que.append([j,where+1])
        else:
            continue

    

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

Submission status: Time Limit Exceeded

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


n, m = map(int,input().split())
tsuro = [[] for i in range(n)]
michishirube = [[0,n] for i in range(n)]



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

visited = [0]*n


def adv(r,x,y):
    #print(x,y)
    global visited
    if y > n:#visited[x] == 1:
        return
    else:
        #visited[x] = 1
        yy = y + 1
        last_room = x
        if michishirube[x][1] >= yy:
            michishirube[x][0] = r
            michishirube[x][1] = yy
            for i in tsuro[x]:
                if i == 0:
                    pass
                else:
                    adv(last_room,i,yy)
        else:
            return

for i in tsuro[0]:
    adv(0,i,0)



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

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

n,m = map(int,input().split())
G = nx.Graph()
a,b = [0]*m,[0]*m

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

if min(min(a),min(b)) != 1:
    print("No")
else:
    l = nx.shortest_path(G, target=1)
    print("Yes")
    [print(l[i][1]) for i in range(2,len(l)+1)]

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)
# print(edge)

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


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

miti = [[] for i in range(N)]


for i in range(M):
    miti[a[i]].append(i)
    miti[b[i]].append(i)


#start
q = [0]
cnt = 1

while(q):
    
    if cnt==N:
        break
    
    x = q[0]
    
    for i in range(len(miti[x])):
        m = miti[x][i]
        if a[m] == x:
            if table[b[m]]==0:
                table[b[m]]=1
                ans[b[m]]=a[m]+1
                q.append(b[m])
                cnt += 1
            miti[b[m]].remove(m)
            
        if b[m] == x:
            if table[a[m]]==0:
                table[a[m]]=1
                ans[a[m]]=b[m]+1
                q.append(a[m])      
                cnt +=1
            miti[a[m]].remove(m)
    
    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()))
root_list = []
for _ in range(m):
    root_list.append(list(map(int, input().split())))

answer_list = [0] * (n-1)
done_list = [1]
already_list = [1]
while len(root_list) > 0 and 0 in answer_list:
    if len(done_list) == 0:
        break
    tmp_list = []
    copy_root_list = root_list.copy()
    for num in done_list:
        for l in root_list:
            if l[1] == num:
                if answer_list[int(l[0]-2)] == 0:
                    answer_list[int(l[0]-2)] = num
                    tmp_list.append(l[0])
                    already_list.append(l[0])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
            elif  l[0] == num and l[0] != l[1]:
                if answer_list[int(l[1]-2)] == 0:
                    answer_list[int(l[1]-2)] = num
                    tmp_list.append(l[1])
                    already_list.append(l[1])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
    copy_root_list = [i for i in copy_root_list if (i[0] not in already_list or i[1] not in already_list)]
    root_list = copy_root_list
    done_list = tmp_list

if 0 not in answer_list:
    print("Yes")
    for i in answer_list:
        print(int(i))
else:
    print("No")

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 way[:]:
            if k in i:
                numls = [j for j in i if j != k]
                num = numls[0]
                if check[num-1]:
                    continue
                else:
                    m.append(num)
                    ans[num-1] = k
                    check[num-1] = True
                    way.remove(i)
    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:
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 min_weight in range(1, m + 1):
    for con in connections:
        r1 = con[0]
        r2 = con[1]
        w1 = weights[r1 - 1]
        w2 = weights[r2 - 1]
        if w1 <= min_weight and w2 <= min_weight:
            continue
        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 max(weights) > 2e5 + 5:
    print("No")
else:
    print("Yes")
    for d in directions[1:]:
        print(d)

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()
        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 = map(int, input().split())
data = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    data[a - 1].append(b - 1)
    data[b - 1].append(a - 1)

ans = [0] * (n - 1)

def bfs(i, queue, p):
    while len(queue) > 0:
        x = queue.pop(0)
        pre = p.pop(0)
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                queue.append(data[x[j]])
                p.append(x[j])

queue = []
pre = [0]
queue.append(data[0])
bfs(0, queue, pre)

if 0 not in ans:
    print("Yes")
    for i in range(len(ans)):
        print(ans[i])
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def SS(): return map(str,sys.stdin.readline().rstrip().split())
def II(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

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
  
N,M = II()
d = [[float("inf")]*N for i in range(N)] 
for _ in range(M):
  A,B = II()
  d[A-1][B-1] = d[B-1][A-1] = 1
path = [-1]*(N)
for i in range(1,N):
  tmp = dijkstra_back(i,0,N,M,d)
  now = i
  for j in range(1,len(tmp)):
    if path[now] == -1:
      path[now] = tmp[j]
      now = path[now]
    elif path[now] == tmp[j]:
      now = path[now]
    else:
      print("No")
      exit()
print("Yes")
for i in range(1,N):
  print(path[i]+1)

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):
        
        now, p, d = q.popleft()
        if now==p:
            continue
        if visited[now]==1:
            continue
        
        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:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
N,M = map(int,input().split())

A = []
B = []
print("Yes")
for x in range(M):
    At,Bt = map(int,input().split())
    A.append(At)
    B.append(Bt)
rinsetu =[[0 for x in range(N)] for y in range(N)]
for x in range(M):
    rinsetu[A[x]-1][B[x]-1] = 1
    rinsetu[B[x]-1][A[x]-1] = 1
L = csr_matrix(rinsetu)
shortest,p =  dijkstra(L,return_predecessors=True,indices=0,directed=False,unweighted=True)


for x in p[1:]:
    print(x+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque

n,m = LI()
p = [[] for i in range(n)]
r = [-1]*n
c = [-1]*n
d = deque()

for _ in range(m):
    a,b = LI()
    p[a-1].append(b-1)
    p[b-1].append(a-1)

r[0] = 0
d.append(0)
while(len(d) > 0):
    x = d.pop()
    for i in p[x]:
        if(r[i] == -1 or r[i] > r[x] + 1):
            r[i] = r[x] + 1
            c[i] = x
            d.append(i)


flg = True
for i in range(n):
    if(r[i] == -1):
        flg = False
        break

if(flg):
    print("Yes")
    for i in range(1,n):
        print(c[i]+1)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M= [int(i) for i in input().split(' ')]
graph = {}

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

for j in range(M):
  a, b= [int(i) for i in input().split(' ')]
  graph[a].append(b)
  graph[b].append(a)
    

def bfs(graph, start):
  queue = [start]
  visited1 = []
  visited = {}
  for i in range(1,N+1):
    visited[i] = 0  
  miti = {}
  for i in range(1,N+1):
    miti[i] = 0
  where_from = [start-1]
  while queue:
    label = queue.pop(0)
    label2 = where_from.pop(0)
    if visited[label]==0:
      visited1.append(label)
      visited[label]=1
      if miti[label] != 0:
        return False
      miti[label] = label2
      queue += graph.get(label, [])
      where_from += [label]*len(graph.get(label, []))
    if len(visited1) == N:
      break
  if len(visited1) != N:
    return False
  return miti

miti = bfs(graph, 1)
if miti:
  print('Yes')
  for i in range(2,N+1):
    print(miti[i])
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
N,M = [int(i) for i in input().split()]
roads = []
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    roads.append([A,B])
    roads.append([B,A])
roads = np.array(roads)
places = [0]*(N+1)
places[1] = 1
q = deque([1])
while min(places[1:]) == 0:
    i = q.pop()
    L = roads[roads[:,0] == i][:,1]
    for j in L:
        if places[j] == 0:
            places[j] = i
            q.appendleft(j)
print("Yes")
for i in range(2,N+1):
    print(places[i])

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M = map(int,input().split())
A = []
for m in range(M):
    A.append(list(map(int,list(input().split()))))
A = list(itertools.chain.from_iterable(A))


Mark = [-1]*(N-1)
Past = [1]
Que = [1]

while len(Past) != N:
    next_road = ([i for i, x in enumerate(A) if x == Que[0]])

    for n in next_road:
        if n%2 == 0:
            next_n = n+1
        else:
            next_n = n-1

        next = A[next_n]

        if Past.count(next) == 0:
            Past.append(next)
            Que.append(next)
            Mark[next-2]=Que[0]


    Que.pop(0)

print("Yes")
for m in Mark:
    print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def abc168_d():
    N, _ = map(int, readline().split())
    adj = [[] for _ in range(N+1)]
    for ln in readlines():
        a, b = map(int, ln.split())
        adj[a].append(b)
        adj[b].append(a)

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

    stack = [1]
    while stack:
        x = stack.pop()
        for ch in adj[x]:
            if dist[ch] != -1 and dist[ch] < dist[x] + 1: continue
            dist[ch] = dist[x] + 1
            label[ch] = x
            stack.append(ch)

    if -1 in label:
        print('No')
        return
    else:
        print('Yes')
        print(*label[2:], sep='\n')

abc168_d()

Submission status: Time Limit Exceeded

Solution code:
import math
import queue
def dijkstra(n, w):
    ans=[math.inf]*n
    done=[]
    done.append(1)
    q=queue.Queue()
    for i in range(n+1):
        if w[1][i]==1:
            q.put(i)
            ans[i-1]=1
            done.append(i)
    while not q.empty():
        now=q.get()
        
        for i in range(n+1):
            if w[now][i]==1 and (i not in done):
                q.put(i)
                done.append(i)
                ans[i-1]=now
    return ans


s = list(map(int,input().split()))
n=s[0]
m=s[1]
mapping=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
    s = list(map(int, input().split()))
    mapping[s[0]][s[1]]=1
    mapping[s[1]][s[0]] = 1

ans=dijkstra(n,mapping)
if not math.inf in ans[1:]:
    print('Yes')
    for i in ans[1:]:
        print(i)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    n, m = map(int, input().split())
    ans = [-1 for i in range(n + 1)]
    # ans[0] = 1

    connections = [[0 for i in range(n)] for i in range(n)]

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

    count = 1
    stack = []
    connected_to_one = [i for i, x in enumerate(connections[0]) if x == 1]
    for room in connected_to_one:
        ans[room] = count
        connections[0][room] = 0
        connections[room][0] = 0

        stack.append(room)

    count += 1
    while len(stack) > 0:
        next_stack = []
        # print(stack)

        for room in stack:
            connected = [i for i, x in enumerate(connections[room]) if x == 1]

            for _room in connected:
                if ans[_room] == -1:
                    ans[_room] = room + 1
                    connections[room][_room] = 0
                    connections[_room][room] = 0
                    next_stack.append(_room)

        count += 1

        stack = [*next_stack]
    _ans = ans[1:-1]
    if -1 in _ans:
        print('No')
    else:
        print('Yes')
        for i in _ans:
            print(i)


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**18

def bfs(start):
    d = [INF]*n
    d[start] = 0
    q = collections.deque([])
    q.append(start)
    pre = [0]*(n)
    while q:
        c = q.popleft()
        next_v = edge[c]
        for v in next_v:
            if d[v] == INF and v != c:
                q.append(v)
                d[v] = d[c]+1
                pre[v] = c
    #経路を復元したい
    return [pre,d]
n,m = map(int,input().split())
edge =[[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
flag = bfs(0)
judge = flag[1]
for i in judge:
    if i == INF:
        print("No")
        sys.exit()
print("Yes")
for i in range(1,n):
    ans = bfs(i)
    if ans[1][0] == 1:
        print("1")
    else:
        print(ans[0][0]+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())
ab = [list(map(int,input().split())) for i in range(m)]

l = [[0 for i in range(n)] for i in range(n)]

a = np.array(l)

for i in range(m):
    l[ab[i][0 ]-1][ab[i][1]-1] = 1
    l[ab[i][1]-1][ab[i][0]-1] = 1

a = np.array(l)
d, p = shortest_path(a, return_predecessors=True, indices=0)

if float('inf') in d:
    print('No')
    

else:
    print('Yes')

for i in p[1:]:
    print(i+1)

Submission status: Time Limit Exceeded

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

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

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

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

    arrows = [0] * n

    j = 0

    while len(blue_set) != 0:
        for r in red_set:
            for nxt in nexts[r]:
                if nxt in blue_set:
                    new_blue_set.remove(nxt)
                    new_red_set.append(nxt)
                    arrows[nxt] = r
        red_set = new_red_set
        new_red_set = []
        blue_set = new_blue_set
    
    print("Yes")
    for arrow in arrows[1:]:
        print(arrow + 1)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,t,n,m,cost):
    prev = [s] * (n+1)
    d = [float("inf")] * (n+1)
    used = [False] * (n+1)
    d[s] = 0

    while True:
        v = -1
        for i in range(n+1):
            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+1):
            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

N,M = map(int, input().split())
cost = [[float("inf") for i in range(N+1)] for i in range(N+1)]

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


ans = []
print("Yes")
for i in range(2,N+1):
    D = dijkstra(1,i,N,M,cost)
    ans.append(D[-2])
    print(D[-2],end = " ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = list(map(int, input().split()))
connects = [[0] * n for _ in range(n)]
for _ in range(m):
    i, j =  list(map(int, input().split()))
    connects[i - 1][j - 1] = 1
    connects[j - 1][i - 1] = 1
can = False
d = [float('inf')] * n
d[0] = 0
r = [0] * n
visited = [0] * n
stack = deque([0, ])
while stack:
    x = stack.popleft()
    next = [j for j in range(n) if connects[x][j] == 1]
    for dx in next:
        d[dx] = min(d[dx], d[x] + 1)
        if visited[dx]:
            continue
        else:
            stack.append(dx)
            visited[dx] = 1
print('Yes')
for i in range(1, n):
    d_next = [[j + 1, d[j]] for j in range(n) if connects[i][j] == 1]
    d_min = float('inf')
    i_min = 0
    for i, dx in d_next:
        if dx < d_min:
            d_min = dx
            i_min = i
    print(i_min)

Submission status: Time Limit Exceeded

Solution code:
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

l = inlt()
n = l[0]
m = l[1]

rooms = []
for i in range(n):
    rooms.append([])

for i in range(m):
    tmp = inlt()

    a = tmp[0]
    b = tmp[1]

    rooms[a-1].append(b)
    rooms[b-1].append(a)

#print(rooms)
sorted = [0]
ans = [0] * n
clear = [0]
while(clear):
    clear_room = clear[0]
    clear.pop(0)
    for i in range(n):
        if clear_room+1 in rooms[i] and i not in sorted:
            ans[i] = clear_room
            sorted.append(i)
            clear.append(i)

if(len(sorted) != n):
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(ans[i]+1)

Submission status: Time Limit Exceeded

Solution code:
def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())


N, M = mapint_inp()

adjm = [[0]*(N+1) for _ in range(N+1)]

for i in range(M):
    A, B = mapint_inp()
    adjm[A][B] = 1
    adjm[B][A] = 1

ans = [0]*(N+1)

from collections import deque

q = deque([1])
visited = set()
visited.add(1)
while q:
    now = q.popleft()
    for i, room in enumerate(adjm[now]):
        if room == 0: continue
        if i not in visited:
            q.append(i)
            visited.add(i)
            ans[i] = now

f = True
for i, e in enumerate(ans):
    if i == 0: continue
    if i == 1: continue
    if e == 0:
        f = False

if f:
    print("Yes")
    for i, e in enumerate(ans):
        if i == 0: continue
        if i == 1: continue
        print(e)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, m = map(int, input().split())
    ans = [-1 for i in range(n + 1)]
    # ans[0] = 1

    connections = [[0 for i in range(n)] for i in range(n)]

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

    count = 1
    stack = []
    connected_to_one = [i for i, x in enumerate(connections[0]) if x == 1]
    for room in connected_to_one:
        ans[room] = count
        connections[0][room] = 0
        connections[room][0] = 0

        stack.append(room)

    count += 1
    while len(stack) > 0:
        next_stack = []
        # print(stack)

        for room in stack:
            connected = [i for i, x in enumerate(connections[room]) if x == 1]

            for _room in connected:
                if ans[_room] == -1:
                    ans[_room] = room + 1
                    connections[room][_room] = 0
                    connections[_room][room] = 0
                    next_stack.append(_room)

        count += 1

        stack = [*next_stack]
    _ans = ans[1:-1]
    if -1 in _ans:
        print('No')
    else:
        print('Yes')
        for i in _ans:
            print(i)
resolve()

Submission status: Time Limit Exceeded

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

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

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

prev =  [-1]* N
d = [float("inf")]*N
used = [False] * N
d[0] = 0

def dijkstra():
    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
dijkstra()
if -1 in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(prev[i]+1)

Submission status: Time Limit Exceeded

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

r=[[] for _ in range(n)]
d=[]
b=[n+1]*n
for _ in range(m):
    a,z=map(int,input().split())
    r[a-1].append(z-1)
    r[z-1].append(a-1)

o=0
f=1
b[o]=0
for _ in range(n):
    for i in r[o]:
        if(b[i]==n+1):
            b[i]=o
            d.append(i)
    if(d):
        f+=1
        o=d[0]
        del d[0]
    else:
        break

if (f==n):
    print("Yes")
    for i in b[1:]:
        print(i+1)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m=list(map(int,input().split()))
R=[[] for _ in range(n)]
sign=[0 for _ in range(n-1)]
dp=[0 for _ in range(n)]

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

start=deque()
start.append(0)
dp[0]=1

while 0 in sign:
  if len(start) == 0:
    print("No")
    exit()
  s=start.popleft()
  for r in R[s]:
    if dp[r-1]:
      continue
    sign[r-2] = s + 1
    start.append(r-1)
    dp[r-1]=1
  
print("Yes")
for s in sign:
  print(s)