Problem:


Score: 400 points

Problem Statement

There is a cave.

The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.

It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.

Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.

If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.

Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 2 \times 10^5

1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)

A_i \neq B_i\ (1 \leq i \leq M)

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

If there is no way to place signposts satisfying the objective, print No.

Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

If we place the signposts as described in the sample output, the following happens:

Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.

Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.

Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.

Thus, the objective is satisfied.

Sample Input 2

6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6

Sample Output 2

Yes
6
5
5
1
1

If there are multiple solutions, any of them will be accepted.



Sample input:
4 4
1 2
2 3
3 4
4 2


Sample output:
Yes
1
2
2

Submission status: Time Limit Exceeded

Solution code:
N, M = 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()
ans = {1:-1}

while que:
    now = que.pop(0)
    for h in d[now]:
        if not h in ans:
            ans[h] = now
            que.append(h)
    if len(ans) == N:
        break
    
if len(ans) == N:
    print('Yes')
    for i in range(N-1):
        print(ans[i+2]) 
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())
A = []
B = []
for i in range(M):
    A_, B_ = map(int, input().split())
    A.append(A_)
    B.append(B_)

l = [[0]*N for i in range(N)]
for i in range(M):
    l[A[i]-1][B[i]-1] = 1
    l[B[i]-1][A[i]-1] = 1



csr = csr_matrix(l)
ans = list(shortest_path(csr, indices=0, return_predecessors=True))
if float('inf') in ans[0]:
    print('No')
else:
    print('Yes')
    for i in range(N-1):
        print(int(ans[1][i+1]+1))

Submission status: Time Limit Exceeded

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

print("Yes")
print_start = 2
while len(queue) > 0:
    # print(queue)
    e, now = queue.pop(0)
    if reached[e] == 0:
        reached[e] = 1
        guide[e] = now
        if e == print_start:
            print(now)
            print_start += 1
        # edge[e].remove(now)
        for next in edge[e]:
            if next != 1 and reached[next] == 0:
                queue.append((next, e))

for i in range(print_start, n+1):
    print(guide[i])

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


def solve():
    N, M = map(int, input().split())
    loadmap = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, input().split())
        loadmap[A].append(B)
        loadmap[B].append(A)

    dbmap = [[float('inf'), -1] for _ in range(N + 1)]  # 部屋の深度, しるべ
    rooms = [[0, 1, 0]]  # [移動前の部屋, 移動後(現在)の部屋, 深度]
    while rooms:
        br, r, d = heappop(rooms)
        if d <= dbmap[r][0]:
            # update room data
            dbmap[r][0] = d
            dbmap[r][1] = br
            # add new room data
            for l in loadmap[r]:
                heappush(rooms, [r, l, d + 1])

    if min([db[1] for db in dbmap[1:]]) == -1:
        print('No')
    else:
        print('Yes')
        for db in dbmap[2:]:
            print(db[1])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
import math
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

# k = int(input())
# s =input()
# a = list(map(int, input().split()))
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):
    x,y= map(int,input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
print("Yes")
for i in range(1,n):
    ans = dijkstra_back(i,0,n,m,cost)
    print(ans[1]+1)

Submission status: Time Limit Exceeded

Solution code:
import copy
N, M = map(int,input().split())
roads = list()
for i in range(M):
    a ,b = map(int,input().split())
    roads.append([min(a,b),max(a,b)])

minroute = list()
marks = dict()
class Route:
    def __init__(self):
        self.w = ''

    def route(self,n, roads, w):
        R = [a for a in roads if a[0] == n or a[1]== n]
        for r in R:
            if r[0] == n:
                num = r[1]
            else:
                num = r[0]
            if num == 1:
                if len(w + '1') < len(self.w) or len(self.w) == 0:
                    self.w = w + '1'
            else:
                roads_ = copy.deepcopy(roads)
                roads_.remove(r)
                self.route(num,roads_, w + str(num))

route = Route()

for i in range(2, N + 1):
    route.w = ''
    route.route(i,roads,str(i)) 
    marks[i] = route.w
dirs = dict()
for k in marks.values():
    for i in range(len(k)-1):
        if k[i] not in dirs.keys():
            dirs[k[i]] = set()
        dirs[k[i]].add(k[i+1])
ret = list()
for v in range(2, N+1):
    if len(dirs[str(v)]) != 1:
        ans = 'No'
    ret.append(list(dirs[str(v)])[0])
ans = 'Yes'
if ans == 'No':
    print(ans)
else:
    print(ans)
    for i in ret:
        print(i)

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)

    visited = [-1] * N
    stack = deque([0])
    visited[0] = 0
    sign = [0] * N
    while stack:
        v = stack[0]
        if G[v]:
            w = G[v].pop()
            if visited[w] < 0 and not w in stack:
                visited[w] = 1
                sign[w] = v+1
                stack.append(w)
        else:
            stack.popleft()

    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:
def check_road(start, road_array, mark_array):
    search_target = []
    search_target.append(start)

    while len(search_target) > 0:
        target = search_target[0]
        for road in road_array:
            if target in road and mark_array[road[abs(1-road.index(target))]] is None and road[abs(1-road.index(target))] != 1:
                # 逆側の要素を返す
                # print('{}を探している、次は{}へ移動'.format(
                #     target, road[abs(1-road.index(target))]))
                mark_array[road[abs(1-road.index(target))]] = target
                search_target.append(road[abs(1-road.index(target))])
        del search_target[0]


# 部屋の数 通路の数
N, M = map(int, input().split())
road_array = []
for i in range(M):
    road_array.append(list(map(int, input().split())))
mark_array = [None] * (N+1)
check_road(1, road_array, mark_array)
mark_array = mark_array[2:]

if None in mark_array:
    print('No')
else:
    print('Yes')
    for mark in mark_array:
        print(mark)

Submission status: Time Limit Exceeded

Solution code:
R=lambda: map(int, input().split())

n, m = R()
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = R()
  g[u - 1].append(v - 1)
  g[v - 1].append(u - 1)

r = [None] * (n - 1)
V = [True] + [False] * (n - 1)
q = [0]; s = 0
while q[s:]:
  u = q[s]; s += 1
  for v in g[u]:
    if not V[v]:
      V[v] = True
      r[v - 1] = u + 1
      q.append(v)

print(*(['No'],['Yes'] + r)[all(r)], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n,m = map(int, input().split())
r=[[0 for i in range(n)]for i in range(n)]
start = [0, 0]
#print(bfs(h, w, m, start))
for i in range(m):
    a,b=map(int, input().split())
    r[a-1][b-1]=b-1
    r[b-1][a-1]=a-1
#print(r)

def bfs(n,r,start):
    #始点に対して終点"g"に着けるか判定

    from collections import deque
    d = [0 for i in range(n)]
    visited=[False for i in range(n)]
    flg = True
    queue=deque([0])
    dd=0
    while queue:
        now=queue.popleft()
        visited[now]=True
        #print(now)
        for i in r[now]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
                d[i]=now
    for i in range(n):
        if not visited:
            flg=False
    #print(d)
    if flg:
        print("Yes")
        for i in range(1,n):
            print(d[i]+1)
    else:
        print("No")
    return "Yes" if flg else "No"

bfs(n,r,start)
#print(d)
"""
    a = queue.Queue()
    a.put(start)
    while not a.empty():
        na, nb = map(int, a.get())
        if m[hh][ww] == "g":
            flg = True
            break

        for i in range(4):
            nx, ny = ww+dx[i], hh+dy[i]
            if 0 <= ny < h and 0 <= nx < w and m[ny][nx] != "#" and d[ny][nx] == 0:
                a.put([ny, nx])
                d[ny][nx] = 1
"""

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split())
#V=[[] for _ in range(N)]
row=[]
col=[]
data=[1]*(M)
for _ in range(M):
    a,b = map(int, input().split())
    row.append(a-1)
    col.append(b-1)

s=0
graph=coo_matrix((data, (row, col)), shape=(N,N))
dist_matrix,predecessors = dijkstra(csgraph=graph, directed=False, indices = s, unweighted=True, return_predecessors=True)
#print(dist_matrix)
#print(predecessor)
ans = [0]*(N-1)
for i,e in enumerate(predecessors[1:]):
    if e == -9999:
        print('No')
        exit()
    ans[i] = e+1
print('Yes')
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m=map(int,input().split())
    root=[[0 for i in range(n)] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    min=[-1 for i in range(n)]
    min[0]=2
    dict={}
    for i in range(n):
        dict[i]=-1

    start=0
    check=[False]*n
    toVis=queue.Queue()
    check[start]=True
    for i in range(len(root[0])):
        if root[0][i]==1:
            toVis.put(i)
            dict[i]=start
        #   print(i,":",start)
            check[i]=True
    while(toVis.empty()!=True):
        now=toVis.get()
        #print(now)
        check[now]=True
        for i in range(n):
            if root[now][i]==1 and check[i]==False:
                toVis.put(i)
                dict[i]=now
            # print(i,":",now)
                check[i]=True
    #print(dict)  
    for i in range(1,n):
        if dict[i]==-1:
            print("No")
            return 0
    print("Yes")
    for i in range(1,n):
        print(dict[i]+1)         


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# input
N, M = map(int, input().split())
Load = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Load[a].append(b)
    Load[b].append(a)

# process
result = True
sign = [-1]*N
l = [0]
while True:
    for i in l:
        l_ = []
        for j in Load[i]:
            if j == i:
                continue

            if sign[j] == -1:
                sign[j] = i
            l_.append(j)
    
    if not -1 in sign:
        break

    l = l_

sign.pop(0)

# output
print("Yes" if result else "No")
[print(x+1) for x in sign]

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 goal:
    if -1 not in ans:break
    g=goal.popleft()
    for i in range(n):
        v=edge[i]
        if g in v:
            ans[i]=g
            edge[i].clear()
            goal.append(i)

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
connections = [[] for _ in range(N)]
for a, b in AB:
    connections[a - 1].append(b - 1)
    connections[b - 1].append(a - 1)
    
markers = [-1] * N
    
queue = [0]
steps = [-1] * N
steps[0] = 0
while len(queue) >= 1:
    room = queue.pop(0)
    for r in connections[room]:
        if steps[r] >= 0:
            continue
        queue.append(r)
        steps[r] = steps[room] + 1
        markers[r] = str(room + 1)
    
print("Yes")
print("\n".join(markers[1:]))

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 _ in range(m):
    for con in connections:
        r1 = con[0]
        r2 = con[1]
        w1 = weights[r1 - 1]
        w2 = weights[r2 - 1]
        if w1 < 2e5 + 10 and w1 + 1 < w2:
            weights[r2 - 1] = w1 + 1
            directions[r2 - 1] = r1
        if w2 < 2e5 + 10 and w2 + 1 < w1:
            weights[r1 - 1] = w2 + 1
            directions[r1 - 1] = r2

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

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
n,m=[int(_) for _ in input().split()]
A=[[int(_) for _ in input().split()] for l in range(m)]
R=deque([] for _ in range(n))
for a in A:
    R[a[0]-1].append(a[1]-1)
    R[a[1]-1].append(a[0]-1)
print("Yes")
for h in range(1,n):
    dq=deque()
    vlist=deque([0]*n)
    vlist[h]=1
    dq.appendleft([h])
    while dq:
        x=dq.popleft()
        if 0 in R[x[-1]]:
            if len(x)==1:
                print(1)
            else:
                print(x[1]+1)
            break
        for a in R[x[-1]]:
            if vlist[a]==0:
                dq.append(x+[a])
                vlist[a]=1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
adj = [[float("inf") for i in range(N)] for j in range(N)]
signs = [-1 for i in range(N)]
signs[0] = 1

for _ in range(M):
  x,y = map(int,input().split())
  adj[x - 1][y - 1] = 1
  adj[y - 1][x - 1] = 1

queue = deque([0])
dist = 0

while len(queue) > 0:
  cur = queue.popleft()
  for i, c in enumerate(adj[cur]):
    if c == 1:
      if signs[i] == -1:
        queue.append(i)
        signs[i] = cur

if all([sign != -1 for sign in signs]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")

Submission status: Time Limit Exceeded

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

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

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

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

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

print('Yes')

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

Submission status: Time Limit Exceeded

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

#print(input_list)
#print(flg)

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

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

print("Yes")
for i in ans_list:
    if not i == 0:
        print(i)

Submission status: Time Limit Exceeded

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

p=[0]*n
p[0]=1
now=1
cnt=0
while 0 in p and cnt<=m:
    for to in l[now-1]:
        if p[to]==0:
            p[to]=now
            cnt+=1
    now=to+1
if 0 in p:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(p[i])

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    yazi = [0] * 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]:
            yazi[j] = v+1
            d[j] = d[v]+cost[v][j]
    return d[1:], yazi[1:]

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

  cost = [[float("inf") for i in range(N)] for i in range(N)] 
  for i in range(M):
      x,y = map(int,input().split())
      cost[x-1][y-1] = 1
      cost[y-1][x-1] = 1
  dis, yazi = dijkstra(0,N,M,cost)
  if max(dis) > M:
    print('No')
  else:
    print('Yes')
    for i in yazi:
      print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
N,M=list(map(int,input().split()))
road_list=[]
for i in range(M):
  road_list.append(list(map(int,input().split())))
ans_dict=dict([])
before_room=[1]
while True:
  temp_room=[]
  for j in range(len(before_room)):
    temp_delete=[]
    for i in road_list:
      if i[0]==before_room[j]:
        if i[1] not in ans_dict:
          ans_dict[i[1]]=before_room[j]
          temp_room.append(i[1])
        #temp_delete.append(i)
      if i[1]==before_room[j]:
        if i[0] not in ans_dict:
          ans_dict[i[0]]=before_room[j]
          temp_room.append(i[0])
        #temp_delete.append(i)
    #for temp in temp_delete:
    #  road_list.remove(temp)
  before_room=temp_room
  #print(ans_dict)
  #print(before_room)
  if len(ans_dict)==N:
    break
    
if len(ans_dict)==N:
  print("Yes")
  for i in range(2,len(ans_dict)+1):
    print(ans_dict[i])
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ans=[0]*n
route={}
for i in range(m):
  a,b=map(int,input().split())
  if a in route:
    route[a]+=[b]
  else:
    route[a]=[b]
  if b in route:
    route[b]+=[a]
  else:
    route[b]=[a]
que=[1]
clear=[0]*n
while len(que)>0:
  x=que.pop(0)
  if clear[x-1]==0:
    que.extend(route[x])
    for k in route[x]:
      if ans[k-1]==0:
        ans[k-1]=x
    clear[x-1]=1
ans.pop(0)
if sorted(ans)[0]==0:
  print("No")
else:
  print("Yes")
  for k in ans:
    print(k)

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]

from collections import deque

d = deque()
d.append(0)

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

if min(Sin)<0:
  print('No')
  sys.exit()
print('Yes')
for i in range(1,n):
  print(Sin[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n, m = map(int, readline().split())
graph = [[0] * n for _ in range(n)]
ab = [list(map(int, readline().split())) for _ in range(m)]
for a, b in ab:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
ans = dijkstra(csr_matrix(graph), return_predecessors=True)
if any(int(v) == -9999 for v in ans[1][0][1:]):
    print('No')
else:
    print('Yes')
    print('\n'.join(map(str, ans[1][0][1:] + 1)))

Submission status: Time Limit Exceeded

Solution code:
# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph,shortest_path
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())

# G.add_nodes_from(list(range(1,N+1)))
for _ in range(M):
    A,B = map(int,input().split())
    G.add_edge(A, B)

shortestPath = shortest_path(G, target=1)
if len(shortestPath) != N:
    print("No")
    exit()

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

# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Time Limit Exceeded

Solution code:
temp = input()
temp = temp.split()
room = int(temp[0])
passage = int(temp[1])
adjlist = {}
visited = [0] * (room + 1) 
finalans = []
finalans.append(0)
for i in range(passage):
    inpu = input()
    inpu = inpu.split()
    firstnode = int(inpu[0])
    secnode = int(inpu[1])
    if firstnode not in adjlist:
        adjlist[firstnode] = []
    if secnode not in adjlist:
        adjlist[secnode] = []
        
    adjlist[firstnode].append(secnode)
    adjlist[secnode].append(firstnode)

flag = 0 
for i in range(2, room + 1):
    temparr = []
    ans = -1 
    visited = [0] * (room + 1) 
    if i not in adjlist:
        flag = 1 
        break
    templist = adjlist[i]
    if 1 in templist:
        finalans.append(1)
        continue 
    for j in templist:
        visited[j] = 1
        temparr.append((j, j))
    while True:
        if len(temparr) == 0:
            break
        getans = 0 
        newarr = []
        for node in temparr:
            newnode = node[0]
            firstnode = node[1]
            if newnode not in adjlist:
                continue 
            if 1 in adjlist[newnode] :
                getans = 1 
                ans = firstnode
                break
            for j in adjlist[newnode]:
                if visited[j] == 1 :
                    continue 
                visited[j] = 1 
                newarr.append((j, firstnode))
        
        if getans == 1:
            break
        
        temparr = newarr[::]
    
    if ans == -1:
        flag = 1 
        break
    finalans.append(ans)

if flag == 1:
    print("No")
#print(adjlist)
else:
    print("Yes")
    for i,j in enumerate(finalans):
        if i == 0 :
            continue 
        print(j)
#print(finalans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

def bfs(graph, start):
    queue = deque([start])
    visited = set()
    distance = defaultdict(int)
    distance[start] = 0
    while queue:
        current_vertex = queue.popleft()
        visited.add(current_vertex)
        for v in graph[current_vertex]:
            if v not in visited and v not in queue:
                queue.append(v)
                distance[v] = distance[current_vertex] + 1
    return distance

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

distance = bfs(graph, 1)
distance_map = defaultdict(set)
for k, v in distance.items():
    distance_map[v].add(k)

ans = 'Yes'
ans_list = []
for v in range(2, N+1):
    intersection = distance_map[distance[v] - 1] & graph[v]
    if len(intersection) != 0:
        ans_list.append(list(intersection)[0])
    else:
        ans = 'No'
if ans == 'No':
    print(ans)
else:
    print(ans)
    for x in ans_list:
        print(x)

Submission status: Time Limit Exceeded

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


from collections import defaultdict
import queue
connection = defaultdict(lambda: 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)
q = queue.Queue()
d = defaultdict(int)
p = defaultdict(int)

c[0] = 1
d[0] = 0
q.put(0)

while not(q.empty()):
  u = q.get()
  for v in range(N):
    if connection[u][v] == 1 and c[v] == 0:
      c[v] = 1
      d[v] = d[u] + 1
      p[v] = u
      q.put(v)
  c[u] = 2
print("Yes")
for i in range(1,N):
  print(p[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
def trace(s, t, ancestors):
    route = [t]
    c = t
    while True:
        a = ancestors[c]
        assert a is not None, 'Failed to trace'
        route.append(a)
        if a == s:
            break
        c = ancestors[c]
    route.reverse()
    return route


def dijkstra(s, t, links):
    heap = [(*l, s) for l in links[s]]
    heapify(heap)
    visited = set()
    ancestors = [None] * N
    while heap:
        cost, node, ancestor = heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        ancestors[node] = ancestor
        if node == t:
            return cost, trace(s, t, ancestors)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2, node))
    return float('inf'), None

N, M = map(int, input().split())
links = [set() for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    links[x-1].add((1, y-1))
    links[y-1].add((1, x-1))
ans = [0]*N
done = set()
for i in range(1, N):
    if i in done:
        continue
    tmp = dijkstra(0, i, links)
    if tmp == float("inf"):
        print("No")
        exit()
    for j in range(1, len(tmp[1])):
        ans[tmp[1][j]] = tmp[1][j-1] + 1
        done.add(tmp[1][j])

print("Yes")
for i in range(1,N):
    print(ans[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+1
    return 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)

    m = dijkstra(0, N, E)
    print("Yes")
    # for i in range(1,N):
    #   print(m[i]+1)
    print("\n".join(map(str, m[1:])))

if __name__ == '__main__':
    main()