Problem:


Score: 400 points

Problem Statement

There is a cave.

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

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

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

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

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

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

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

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

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

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

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

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

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

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

Thus, the objective is satisfied.

Sample Input 2

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

Sample Output 2

Yes
6
5
5
1
1

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



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


Sample output:
Yes
1
2
2

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

d = deque()

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

dct = {}
for _ in range(M):
    a, b = map(int,input().split())
    if not a in dct:
        dct[a] = set()
    if not b in dct:
        dct[b] = set()
    dct[a].add(b)
    dct[b].add(a)

#print(dct)
answers = [0]*(N+1)

stack = deque([1,])
lst = []
while len(stack):
    s = stack.popleft()
    lst.append(s)
    #print(dct[s])
    for i in dct[s]:
        if i in lst:
            continue
        if i in stack:
            continue
        stack.append(i)
        answers[i] = s

if answers.count(0) != 2:
    print("No")
else:
    print("Yes")
    for ans in answers[2:]:
        print(ans)

Submission status: Time Limit Exceeded

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

dct = {}
for _ in range(M):
    a, b = map(int,input().split())
    if not a in dct:
        dct[a] = set()
    if not b in dct:
        dct[b] = set()
    dct[a].add(b)
    dct[b].add(a)

#print(dct)
answers = [0]*(N+1)

stack = [1]
lst = []
while len(stack):
    s = stack.pop(0)
    lst.append(s)
    #print(dct[s])
    for i in dct[s]:
        if i in lst:
            continue
        if i in stack:
            continue
        stack.append(i)
        answers[i] = s

if answers.count(0) != 2:
    print("No")
else:
    print("Yes")
    for ans in answers[2:]:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n,m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for i in range(1,m+1):
        a,b = map(int, input().split())
        graph[a-1].append(b)
        graph[b-1].append(a)
    
    q = deque([1])
    prev=[1]
    siru = [0] * (n-1)
    while q:
    
        now = q.popleft()
        
        next = graph[now-1]
    
        
        for n in next:
            if not n in prev: 
                q.append(n)
                prev.append(n)
                siru[n-2] = now
        if not 0 in siru:
            break
    
    
    
    print("Yes")
    print("\n".join(map(str, siru)))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

will.append(1)

while will:
    visit = will.pop(0)
    for i in root[visit]:
        if visited[i] != -1:
            continue
        if i in will:
            continue
        will.append(i)
        visited[i] = visit

if visited[1:] == -1:
    print('No')
else:
    print('Yes')
    for i in range(2,len(visited)):
        print(visited[i])

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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

A = []
B = []


# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)


# 隣接行列
route = [[0 for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = route[b - 1][a - 1] = 1


room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue)>0:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    # for i in route2[now]:
    #     if i not in visited:

    for i, node in enumerate(route[now]):
        if node == 0:
            continue
    #
        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1
            #
            # room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

q = deque([1])
prev=[1]
siru = [0] * (n-1)
while q:

    now = q.popleft()
    
    next = graph[now-1]

    
    for n in next:
        if not n in prev: 
            q.append(n)
            prev.append(n)
            siru[n-2] = now
    if not 0 in siru:
        break



print("Yes")
print("\n".join(map(str, siru)))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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

A = []
B = []

route = [[0 for j in range(N)] for i in range(N)]

for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)
    
    route[_a - 1][_b - 1] = route[_b - 1][_a - 1] = 1

# # 隣接行列
# for i in range(N):
#     for j in range(N):
# 
# for a, b in zip(A, B):
#     route[a - 1][b - 1] = route[b - 1][a - 1] = 1

# # 隣接リスト
# route2 = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for i, node in enumerate(route[now]):
        if node == 0:
            continue

        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1

            room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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)

# 隣接行列
route = [[0 for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = route[b - 1][a - 1] = 1

# # 隣接リスト
# route2 = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for i, node in enumerate(route[now]):
        if node == 0:
            continue

        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1

            room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

q = deque([1])
prev=[1]
siru = [0] * (n-1)
while q:

    now = q.popleft()
    
    next = graph[now-1]

    
    for n in next:
        if not n in prev: 
            q.append(n)
            prev.append(n)
            siru[n-2] = now
    if not 0 in siru:
        break

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

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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)

# # 隣接行列
# route = [[False for j in range(N)] for i in range(N)]
# 
# for a, b in zip(A, B):
#     route[a - 1][b - 1] = True
#     route[b - 1][a - 1] = True

# 隣接リスト
route2 = [[] for n in range(N)]

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque()
visited = []

queue.append(0)
visited.append(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)


    for r in route2[now]:
    # for r in range(N):
        if r not in visited:
        # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(r)
            visited.append(r)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[r]:
                room_depth[r] = min(room_depth[now] + 1, room_depth[r])
            else:
                room_depth[r] = room_depth[now] + 1

            room_sign[r] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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)

# 隣接行列
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True

# 隣接リスト
route2 = [[] for n in range(N)]

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque()
visited = []

queue.append(0)
visited.append(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    
    for r in route2[now]: 
    # for r in range(N):
        if r not in visited:
        # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(r)
            visited.append(r)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[r]:
                room_depth[r] = min(room_depth[now] + 1, room_depth[r])
            else:
                room_depth[r] = room_depth[now] + 1

            room_sign[r] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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)

# 隣接行列
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True

# room_connection = [[] for n in range(N)]
#
# for a, b in zip(A, B):
#     room_connection[a - 1].append(b - 1)
#     room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque()
visited = []

queue.append(0)
visited.append(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in range(N):
        if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(r)
            visited.append(r)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[r]:
                room_depth[r] = min(room_depth[now] + 1, room_depth[r])
            else:
                room_depth[r] = room_depth[now] + 1

            room_sign[r] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

q = deque([1])
prev=[1]
siru = [0] * (n-1)
while q:

    now = q.popleft()
    
    next = graph[now-1]

    
    for n in next:
        if not n in prev: 
            q.append(n)
            prev.append(n)
            siru[n-2] = now

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

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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)

room_connection = [[] for n in range(N)]

for a, b in zip(A, B):
    room_connection[a - 1].append(b - 1)
    room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []
queue = deque()
queue.append(0)
# pprint(room_connection)

while stack:
    now =queue.popleft()
    # now = stack.pop()
    next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in next_room:
        if r not in visited:
            queue.append(r)
            # stack.append(r)

        if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

    visited.append(now)

    if set(visited) == set(range(N)):
        break


    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path #dijkstra
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

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

d = [1 for _ in range(M)]
arr = np.array([list(map(int,input().split())) for _ in range(M)])
arr = arr.T - 1
graph = csr_matrix((d, (arr[0], arr[1])), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = shortest_path(graph,method='J', directed=False,indices=0,return_predecessors=True,unweighted=True)

pred = pred + 1
print("Yes")
print(*pred[1:],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = list(map(int, input().split()))
root_dict = {}

for _ in range(m):
    tmp = list(map(int, input().split()))
    if tmp[0] != tmp[1]:
        if tmp[0] not in list(root_dict.keys()):
            root_dict[tmp[0]] = [tmp[1]]
        else:
            root_dict[tmp[0]].append(tmp[1])
        if tmp[1] not in list(root_dict.keys()):
            root_dict[tmp[1]] = [tmp[0]]
        else:
            root_dict[tmp[1]].append(tmp[0])

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

done = deque([1])


while done:
    x = done.popleft()
    for i in root_dict[x]:
        if visited[i-1] < 0:
            visited[i-1] = x
            done.append(i)

if -1 in visited:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(visited[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

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

d = [1 for _ in range(M)]
arr = np.array([list(map(int,input().split())) for _ in range(M)])
arr = arr.T - 1
graph = csr_matrix((d, (arr[0], arr[1])), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True)

pred = pred + 1
print("Yes")
print(*pred[1:],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

def input_multiple_number_as_list():
    return list(map(int, input().split()))

N,M = input_multiple_number()

shilve = [-1]*(N+1)
michi = [[] for _i in range(N+1)]

for i in range(M):
	a,b = input_multiple_number()
	michi[a].append(b)
	michi[b].append(a)

que = [1]

while len(que) > 0:
	now_heya = que.pop(0)
	for nexthop in michi[now_heya]:
		if shilve[nexthop] == -1:
			shilve[nexthop] = now_heya
			que.append(nexthop)


print("Yes")
for i in shilve[2:]:
	print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

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

i = [] #頂点(始点)
j = [] #頂点(終点)
d = [] #頂点間の距離
for _ in range(M):
    A,B = map(int,input().split())
    i.append(A-1)
    j.append(B-1)
    d.append(1)

graph = csr_matrix((d, (i, j)), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True)

pred = pred + 1
print("Yes")
print(*pred[1:],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0] * (n+1)

#q = []

def bfs(x):
	q = deque()
	q.append(x)
	while(len(q) != 0):
		now = q.popleft()
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				reached.remove(k)
				q.append(k)

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

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

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

i = [] #頂点(始点)
j = [] #頂点(終点)
d = [] #頂点間の距離
for _ in range(M):
    A,B = map(int,input().split())
    i.append(A-1)
    j.append(B-1)
    d.append(1)

graph = csr_matrix((d, (i, j)), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0] * (n+1)

q = []

def bfs(x):
	q.append(x)
	while(len(q) != 0):
		now = q.pop(0)
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				#reached.remove(k)
				q.append(k)

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

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")

Submission status: Time Limit Exceeded

Solution code:
from numba import jit,njit
import numpy as np
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

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

i = [] #頂点(始点)
j = [] #頂点(終点)
d = [] #頂点間の距離
for _ in range(M):
    A,B = map(int,input().split())
    i.append(A-1)
    j.append(B-1)
    d.append(1)

graph = csr_matrix((d, (i, j)), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True)

@njit
def solve():
    print("Yes")
    for i in range(1,N):
        print(pred[i]+1)

solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0 for _ in range(n+1)]

q = []

def bfs(x):
	q.append(x)
	while(len(q) != 0):
		now = q.pop(0)
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				#reached.remove(k)
				q.append(k)

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

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0 for _ in range(n+1)]

q = []

def bfs(x):
	q.append(x)
	while(len(q) != 0):
		now = q.pop(0)
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				reached.remove(k)
				q.append(k)

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

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(len(reached)==0):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")

Submission status: Time Limit Exceeded

Solution code:
from numba import jit,njit
import numpy as np
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

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

@jit
def resieveInput(M):
    i = [] #頂点(始点)
    j = [] #頂点(終点)
    d = [] #頂点間の距離
    for _ in range(M):
        A,B = map(int,input().split())
        i.append(A-1)
        j.append(B-1)
        d.append(1)
    return i,j,d

i,j,d = resieveInput(M)

graph = csr_matrix((d, (i, j)), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True)
print("Yes")
print(*(pred[1:]+1),sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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

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

length = N
i = [] #頂点(始点)
j = [] #頂点(終点)
d = [] #頂点間の距離
for _ in range(M):
    A,B = map(int,input().split())
    i.append(A-1)
    j.append(B-1)
    d.append(1)

graph = csr_matrix((d, (i, j)), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True,)
pred = pred + 1
print("Yes")
print(*pred[1:],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
from collections import deque

def file_input():
    f = open('ABC168/input.txt', 'r')
    sys.stdin = f

def main():
    if os.getenv("ENV")=='LOCAL':
        file_input()

    N,M=map(int, input().split())
    r={}
    for i in range(M):
        A,B=map(int, input().split())
        # print("A:"+str(A[i])+" B:"+str(B[i]))
        if A not in r:
            r[A]=[B]
        else:
            r[A].append(B)
        if B not in r:
            r[B]=[A]
        else:
            r[B].append(A)
        # print(tmp[A[i]-1])
    # print(r)

    q=deque()
    q.append(1)
    visited=set()
    out=[0]*(N-1)
    while len(q)>0:
        # print("q="+str(q))
        position=q.popleft()
        # print("p="+str(position))
        visited.add(position)
        for des in r[position]: #今いる場所から行ける場所を探索
            if des in visited:  #すでに訪問済み
                continue
            if des in q:    #ループよけ 2→2みたいな
                continue
            q.append(des)   #行ける場所だった場合キューに追加
            # print("destination="+str(des)+" p="+str(position)+" q="+str(q))
            out[des-2]=position
    # print(visited)



    print('Yes')
    [print(x) for x in out]

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,*inp=map(int,open(0).read().split())
d=[[] for i in range(n)]
for i in range(m):
    j=2*i
    a,b=inp[j:j+2]
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
l=[-1 for i in range(n)]
q=deque([0])
#print(d)
while len(q)>0:
    x=q.popleft()
    for i in d[x]:
        #print(i)
        if i!=0 and l[i]==-1 and x not in q:
            q.append(i)
            #print(i)
            l[i]=str(x+1)
l=l[1:]
#print(l)
print('No' if 0 in l else 'Yes\n'+'\n'.join(l))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def bfs():
  n,m = map(int,input().split())
  g = [[] for i in range(n)]
  direction = [0]*n
  for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    
  d = [0]*n
  que = deque([])
  que.append(0)
  d[0] = 1 #到達済み
  
  while que:
    now = que.popleft() 
    if d == [1]*n: #全て到達したら終わり
      break
    for next in g[now]: #部屋1から行ける場所で回す
      if d[next] == 0:
        que.append(next)
        d[next] = 1
        direction[next] = now +1
        
  print('Yes')
  print(*direction[1:],sep='\n')
        


bfs()