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:
# https://qiita.com/kazukazukazukazu/items/e5db00a3aefb1f5ed72f
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

N, M = map(int, input().split())
# AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = Dijkstra()

for _ in range(M):
    a, b = map(int, input().split())
    graph.add(a, b, 1)

# for a, b in AB:
#     graph.add(a, b, 1)

ans = []
flg = False
for i in range(2, N+1):
    result = graph.getDijkstraShortestPath(i, 1)
    if result[1]==float('inf'):
        flg = True
        break
    ans.append(result[1])
#     print(result[1])

if flg:
    print('No')
else:
    print('Yes')
    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

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

A = []
B = []

for i in range(M):
    A_i, B_i = map(int, input().split())
    A.append(A_i)
    B.append(B_i)

output = [0] * (N-1)


# 1回目
index_1_A = [i for i, x in enumerate(A) if x == 1]
index_1_B = [i for i, x in enumerate(B) if x == 1]

first_index = []

for i in range(len(index_1_A)):
    first_index.append(B[index_1_A[i]])

for i in range(len(index_1_B)):
    first_index.append(A[index_1_B[i]])


for i in first_index:
    output[i-2] = 1


former_index_2 = [1]
former_index = first_index
temp_index = []

# 2回目以降
while len(former_index) != 0:
    for j in former_index:
        index_1_A = [i for i, x in enumerate(A) if x == j]
        index_1_B = [i for i, x in enumerate(B) if x == j]

        for i in range(len(index_1_A)):
            temp_index.append(B[index_1_A[i]])

        for i in range(len(index_1_B)):
            temp_index.append(A[index_1_B[i]])

        temp_index = [i for i in temp_index if i not in former_index_2]

        for i in temp_index:
            if output[i-2] == 0:
                output[i-2] = j

    former_index_2 = former_index
    former_index = temp_index
    temp_index = []        

if 0 in output:
    print("No")
else:
    print("Yes")
    for i in output:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
R = [list(map(int, input().split())) for i in range(M)]

F = [1] * N
F[0] = 0
O = [0] * N

Us = [1]
for i in range(N):
    NUs = []
    for j in R:
        for U in Us:
            if j[0] == U and F[j[1] - 1] == 1:
                F[j[1] - 1] = 0
                O[j[1] - 1] = U
                NUs.append(j[1])
            if j[1] == U and F[j[0] - 1] == 1:
                F[j[0] - 1] = 0
                O[j[0] - 1] = U
                NUs.append(j[0])
    Us = NUs

if np.prod(F):
    print('No')
else:
    print('Yes')
    for i in O[1:]:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lis=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    lis[a].append(b)
    lis[b].append(a)
ans=[0 for i in range(n+1)]
i=1
ii=lis[i]
for oo in ii:
  ans[oo]=1
  lis[oo].clear()
while i<=n:
    for k in ii:
        for j in lis:
            if ii!=j:
                if k in j:
                    ans[lis.index(j)]=k
                    j.clear()
    i+=1
print("Yes")
for i in range(2,len(ans)):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

# stdin = open('sample.txt')


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ABs = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
    nows = [1]
    next_ = []
    ans = [None] * N
    while True:
        for now in nows:
            for ab in [item for item in ABs if item[0] == now or item[1] == now]:
                a, b = ab
                tmp = b if a == now else a
                if not ans[tmp - 1]:
                    if not ans[tmp - 1]:
                        ans[tmp - 1] = now
                    ABs.remove(ab)
                    next_.append(tmp)
        nows = next_[:]
        next_ = []
        if not ABs:
            break
        if not [x for x in ans[1:] if x is None]:
            break
    ans = ans[1:]
    if None in ans:
        print('No')
    else:
        print('Yes')
        for item in ans:
            print(item)


if __name__ == "__main__":
    main()

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, method='D')

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:
from collections import deque

n, m = (int(each) for each in input().split())
paths = []
for each in range(m):
    paths.append(set([int(each) for each in input().split()]))

result = [-1]*(n+1)

queue = deque()
queue.append(1)
while queue:
    start_at = queue.popleft()

    for path in paths:
        if start_at in path:
            neibor = (list(path-{start_at}))[0]
            # print(neibor)
            if result[neibor] != -1:
                continue
            result[neibor] = start_at
            queue.append(neibor)

if -1 in result[2:]:
    print('No')
else:
    print('Yes')
    print('\n'.join(str(each) for each in result[2:]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M=map(int,input().split())
A=np.zeros(N)
B=np.zeros([M,2])
for i in range(M):
  k,l=map(int,input().split())
  B[i,0]=k
  B[i,1]=l

C={1}
D=set()
E=[]
while B.shape[0]>0:
  for i in range(B.shape[0]):
    if B[i,0] in C:
      if A[int(B[i,1])-1]==0:
        A[int(B[i,1])-1]=B[i,0]
        D.add(B[i,1])
      E.append(i)
    elif B[i,1] in C:
      if A[int(B[i,0])-1]==0:
        A[int(B[i,0])-1]=B[i,1]
        D.add(B[i,0])
      E.append(i)
  B=np.delete(B,E,0)
  E=[]
  C=D
  D=set()

print("Yes")
for i in range(1,N):
  print(int(A[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])):
        if cnt==N:
            break
    
        m = miti[x][i]
        if a[m] == x and table[b[m]]==0:
            table[b[m]]=1
            ans[b[m]]=a[m]+1
            q.append(b[m])
            cnt += 1
        if b[m] == x and table[a[m]]==0:
            table[a[m]]=1
            ans[a[m]]=b[m]+1
            q.append(a[m])      
            cnt +=1
    
    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:
from collections import deque

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

if __name__ == '__main__':
    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()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [0] * (N+1)
    done = [False] * (N+1)

    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if not done[current]:
            done[current] = True
            mark[current] = str(prev)
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    #mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
        
    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()
    
        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)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def main():
    N, M = map(int, input().split())
    route = [[] for _ in range(N)]
 
    for i in range(M):
        a, b = map(int, input().split())
        route[a-1].append(b-1)
        route[b-1].append(a-1)
    
    arrive_time = [0] + [-1] * (N - 1)
    arrive_route = [0] + [-1] * (N - 1)
    q = deque()
    q.append(0)
    while len(q):
        idx = q.pop()
        for c in route[idx]:
            if arrive_time[c] >= 0 and arrive_time[c] <= arrive_time[idx]+1:
                continue
            arrive_time[c] = arrive_time[idx]+1
            arrive_route[c] = idx
            q.append(c)
    if min(arrive_time) < 0:
        print("No") 
    else:
        print("Yes")
        for r in arrive_route[1:]:
            print(r+1)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import networkx as nx

YES = "Yes"  # type: str
NO = "No"


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()
    G.add_nodes_from([1+n for n in range(N)])

    G.add_edges_from([(a,b) for a,b in zip(A,B)])

    paths = nx.predecessor(G, 1)

    ans_list = []
    for key, val in sorted(paths.items()):
        if key != 1:
            ans_list.append((key,val[0]))

    print(YES)
    ans_list.sort(key=lambda x: x[0])
    for key, val in ans_list:
        print(val)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:


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

p = [[] for _ in range(n+1)]
f = [0] * (n + 1)
x = [0] * (n + 1)

f[1] = 1
for _ in range(m):
    a, b = map(int, input().split())
    p[a] = p[a]+[b]
    p[b] = p[b] + [a]

st = [1]

while (len(st) > 0):
    ls = len(st)
    #print("stack", st)
    t = st[:]
    for i in t:
        #print("i=", i, t)
        for j in p[i]:
            if(f[j] == 0):
                #print(j, "from", i)
                st += [j]
                f[j] = i
    st = st[ls:]

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

Submission status: Time Limit Exceeded

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

n,m = map(int,input().split())
roots=[]
for i in range(m):
    roots.append(list(map(int,input().split())))

am=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(m):
        if roots[j][0] == i+1:
            am[i][roots[j][1]-1] = 1
        elif roots[j][1] == i+1:
            am[i][roots[j][0]-1] = 1
am = np.array(am)

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]
def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])
d,p = shortest_path(am,return_predecessors=True)

routes=[]
for i in range(len(d)):
    routes.append(get_path(i,0,p))

flag = 0
ms = [0 for _ in range(n)]
changes=[0 for _ in range(n)]
for i in range(n):
    if len(routes[i]) > 1:
        for j in range(len(routes[i])):
            tmp = ms[routes[i][j-1]]
            ms[routes[i][j-1]] = routes[i][j] + 1
            if tmp != ms[routes[i][j-1]]:
                changes[routes[i][j-1]] += 1

for i in range(1,n):
    if changes[i] > 1:
        flag = 1

if flag == 0:
    for i in range(n):
        if i == 0:
            print('Yes')
        else:
            print(ms[i])
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
def readinput():
    n,m=list(map(int,input().split()))
    rooms = [
        [[],-1,-1] for _ in range(n)
        ]
    for _ in range(m):
        a,b = list(map(int,input().split()))
        rooms[a-1][0].append(b)
        rooms[b-1][0].append(a)
    return n,m,rooms

def labelNext(target, rooms, nokori, cost):
    oitaList=[]
    idx = list(nokori)
    for ii in idx:
        i = ii-1
        room=rooms[i]
        if (target in room[0]) and (room[1] == -1):
            room[1] = target
            room[2] = cost
            oitaList.append(i+1) # 道しるべをおいた部屋番号のリストにするので+1
    nokori -= set(oitaList)  #　道しるべを置いた部屋番号を削除
    return oitaList

def main(n,m,rooms):
    nokori=set(range(2,n+1))  # 道しるべを置いてない部屋番号の集合 (1を除くすべて)
    target=1
    cost=1
    nextList=labelNext(target,rooms, nokori, cost)
    while(len(nokori)>0):
        cost+=1
        nl=[]
        for n in nextList:
            nl.append(labelNext(n,rooms,nokori,cost))
            if(len(nokori)==0):
                break
        nextList=nl
    labelList=[]
    for room in rooms:
        labelList.append(room[1])   
    labelList.pop(0)     
    return labelList

if __name__=='__main__':
    n,m,rooms=readinput()
    labelList=main(n,m,rooms)
    print('Yes')
    for l in labelList:
        print(l)

Submission status: Time Limit Exceeded

Solution code:
import copy
N, M = map(int, input().split())
inputlist = []
prev = []
next = []
ans = [10000000] * (N + 1)
idxStock = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        prev.append(b)
        ans[b] = 1
    elif b == 1:
        prev.append(a)
        ans[a] = 1
    else:
        inputlist.append(a)
        inputlist.append(b)
while len(inputlist) != 0:
    for i in range(int(len(inputlist) / 2)):
        if prev.count(inputlist[i * 2]) != 0:
            idxStock.append(i)
            next.append(inputlist[i * 2 + 1])
            if ans[inputlist[i * 2 + 1]] ==10000000:
                ans[inputlist[i * 2 + 1]] = inputlist[i*2]
        elif prev.count(inputlist[i * 2 + 1]) != 0:
            idxStock.append(i)
            next.append(inputlist[i * 2])
            if ans[inputlist[i * 2]] == 10000000:
                ans[inputlist[i * 2]] = inputlist[i * 2 + 1]
    if len(next) == 0:
        print("No")
        exit()
    list.sort(idxStock, reverse=True)
    for i in idxStock:
        del inputlist[i*2]
        del inputlist[i * 2]
    idxStock.clear()
    prev.clear()
    prev = copy.copy(next)
    next.clear()
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())
t = [[] for i in range(n)]
dis = [n for i in range(n)]
dis[0] = 0
near = [0 for i in range(n)]
c = []
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    dis[t[0][i]] = 1
    near[t[0][i]] = 0
    c.append(t[0][i])
while len(c) > 0:
    d = len(c)
    for i in range(d):
        e = c[0]
        for j in range(len(t[e])):
            if dis[t[e][j]] >= dis[e] +1:
                 dis[t[e][j]] = dis[e] +1
                 near[t[e][j]] = e
                 c.append(t[e][j])
        del c[0]
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)

Submission status: Time Limit Exceeded

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

#隣接リスト
adjacency_list=[[] for i in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    adjacency_list[a-1].append(b-1)
    adjacency_list[b-1].append(a-1)

#i番目が、1からの距離がiのリスト
dist_list=[[0]]
#i番目が、1から部屋までの距離
#dist_list2=[float("inf")]*n
#dist_list2[0]=0
#目印をつける方向
flag_list=[0]*(n-1)
#処理が終わってない部屋の集合
task_list=set([int(i) for i in range(1,n)])

while len(task_list)!=0:
    for i in dist_list[-1]:
        #iはひとつ距離が短い部屋の番号
        tmp=[]
        for j in adjacency_list[i]:
            #jは、iと隣接している部屋の番号
            if j in task_list:
            #if dist_list2[j] = float("inf"):
                #dist_list2[j]=#新しい距離
                tmp.append(j)
                flag_list[j-1]=i
                task_list.discard(j)
        dist_list.append(tmp)

print("Yes")
for i in flag_list:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [0] * (N+1)
    done = [False] * (N+1)

    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if not done[current]:
            done[current] = True
            mark[current] = prev
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

N, M = map(int, input().split())
AB = [[0, 0] for _ in range(M)]
for i in range(M):
  AB[i] = list(map(int, input().split()))
  AB[i][0] -= 1
  AB[i][1] -= 1
AB = np.array(AB)

ikikata = [0 for _ in range(N)]
miti = [0 for _ in range(N)]
x = [i for i in range(M)]

idx = deque([0])
j = 0
while idx:
  k = idx.popleft()
  index1 = set(np.where(AB[:, 0] == k)[0]) & set(x)
  index2 = set(np.where(AB[:, 1] == k)[0]) & set(x)
  for i in index1:
    if miti[AB[i][1]] == 0:
      ikikata[AB[i][1]] = 1
      miti[AB[i][1]] = k + 1
      x[i] = -1
      idx.append(AB[i][1])
  for i in index2:
    if miti[AB[i][0]] == 0:
      ikikata[AB[i][0]] = 1
      miti[AB[i][0]] = k + 1
      x[i] = -1
      idx.append(AB[i][0])
  j += 1

if 0 in miti[1:]:
  print('No')
else:
  print('Yes')
  for i in miti[1:]:
    print(int(i))

Submission status: Time Limit Exceeded

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

ans = [0 for _ in range(N+1)]
now = [1]
next = []

while len(now):
    for x in now:
        for y in L[x]:
            if (y not in now) and (ans[y] == 0):
                ans[y] = x
                next.append(y)
    now = next.copy()
    next = []

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from heapq import heappush, heappop


class Dijkstra:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.adj_list = [[] for _ in range(self.n)]

    # Edge数分回すことを想定
    def add_edge(self, start, end, weight=1, undirected=False):
        self.adj_list[start].append((end, weight))
        if undirected:
            self.adj_list[end].append((start, weight))

    def distance(self, start):
        # 始点から各頂点までの最短距離を格納する
        self.dist = [float('inf') for _ in range(self.n)]
        # 最短経路における, その頂点の前の頂点のIDを格納する
        self.prev = [-1 for _ in range(self.n)]
        self.dist[start] = 0
        # 各要素は，(頂点vのID, startからある頂点vまでの仮の距離)からなるタプル
        q = []
        heappush(q, (start, 0))
        while len(q) != 0:
            src, prov_cost = heappop(q)
            # プライオリティキューに格納されている最短距離が, 現在計算できている最短距離より大きければ，distの更新をする必要はない
            if self.dist[src] < prov_cost:
                continue
            # 他の頂点の探索
            for val in self.adj_list[src]:
                dest, cost = val
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost  # distの更新
                    heappush(q, (dest, self.dist[dest]))  # キューに新たな仮の距離の情報をpush
                    self.prev[dest] = src
        return self.dist

    def shortest_path(self, goal):
        path = [goal]
        dest = goal
        # 終点から最短経路を逆順に辿る
        while self.prev[dest] != float('inf'):
            if self.prev[dest] == -1:
                break
            path.append(self.prev[dest])
            dest = self.prev[dest]
        return path[::-1]


def get_result(data):
    N, M = data[0]
    A = data[1:]
    solver = Dijkstra(N)
    for val in A:
        solver.add_edge(val[0]-1, val[1]-1, undirected=True)
    _ = solver.distance(0)
    flag = [set() for _ in range(N)]
    for i in range(1, N):
        dest = i
        while solver.prev[dest] != float('inf'):
            if solver.prev[dest] == -1:
                break
            flag[dest].add(solver.prev[dest])
            dest = solver.prev[dest]

    flag = flag[1:]
    for val in flag:
        if len(val) != 1:
            print('No')
            return None

    print('Yes')
    for val in flag:
        print(list(val)[0]+1)
    return None


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    # print(result)

Submission status: Time Limit Exceeded

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

M_sign = {}
M_dis = {}
M_ne = {}
for i in range(M):
    M_sign[i+1] = 0
    M_dis[i+1] = 0
    M_ne[i+1] = []
for i in range(N):
    a, b = [int(i) for i in input().split()]
    M_ne[a].append(b)
    M_ne[b].append(a)

M_sign[1] = 1
M_dis[1] = 0
for i in M_ne[1]:
    M_sign[i] = 1
    M_dis[i] = 1

target = M_ne[1]

flag = 0
for i in range(M):
    for t in target:
        # tが探索完了してる場合
        if M_sign[t] != 0:
            target.remove(t)
            # t（探索完了）とつながってるものでループ
            for tt in M_ne[t]:
                # tのsignをつける
                if M_sign[tt] == 0:
                    # M_ne[t].remove(tt)
                    M_sign[tt] = t
                    M_dis[tt] = M_dis[t] + 1
                    target.append(tt)
                # すでにsignつけてたら無視
                # else:

    if len(target) == 0:
        flag = 1
        break
if flag == 1:
    for j in range(M):
        for i in range(1,M):
            # print(M_sign[i+1])
            for n in M_ne[i]:
                if M_dis[i] > (M_dis[n] + 1):
                    M_sign[i] = n
                    M_dis[i] = M_dis[n] + 1
    print('Yes')
    for i in range(1,M):
        print(M_sign[i+1])
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

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

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

new_places = [1]
max_N = N + 1



def check(targets, waras):
    for target in targets:
        if target in waras:
            return target
    return None

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

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

else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
l=[0]*N
que=deque([])
que.append(1)
while que:
  if 0 not in l:
    exit()
  p=que.popleft
  for i in range(M):
    if ab[i][0]==p:
      que.append(ab[i][1])
      l[ab[i][1]-1]=p
    if ab[i][1]==p:
      que.append(ab[i][0])
      l[ab[i][0]-1]=p
print("Yes")
print(*l)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N, M = map(int, input().split())
guidepost = [None] * N
distance = [0] + [10**9] * (N - 1)
dd = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
stack = deque([1])
checked = [False] * N
while len(stack) >= 1:
    i = stack.popleft()
    checked[i - 1] = True
    for j in dd[i]:
        distance[j - 1] = min(distance[j - 1], distance[i - 1] + 1)
        if guidepost[j - 1] is None:
            guidepost[j - 1] = i
        elif distance[guidepost[j - 1] - 1] > distance[i - 1]:
            guidepost[j - 1] = i
        if not checked[j - 1]:
            stack.append(j)
print('Yes')
for i in range(1, N):
    print(guidepost[i])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = [[0 for x in range(2)] for y in range(m)]
for i in range(m):
    l[i] = list(map(int,input().split()))
l2 = [m+1 for x in range(n)]
l2[0] = 1
l3 = [0 for x in range(n)]
key = 1
while (max(l2) == m+1):
    for j in range(m):
        if l2[l[j][0]-1] == key:
            l2[l[j][1]-1] = min(key+1,l2[l[j][1]-1])
            if l2[l[j][1]-1] == key+1:
                l3[l[j][1]-1] = l[j][0]
        if l2[l[j][1]-1] == key:
            l2[l[j][0]-1] = min(key+1,l2[l[j][0]-1])
            if l2[l[j][0]-1] == key+1:
                l3[l[j][0]-1] = l[j][1]            
    key += 1
print("Yes")
for k in range(n-1):
    print(l3[k+1])