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 = list(map(int, input().split()))
paths = [list(map(int, input().split())) for _ in range(M)]

result = []
passed_room = [1]
depth = 1

while paths and depth<N:
  tmp_passed = []
  del_path = []
  
  for i, path in enumerate(paths):
    if path[0] in passed_room:
      if path[1] in passed_room+tmp_passed:
        del_path.append(paths[i])
        continue
      result.append((path[1], path[0]))
      tmp_passed.append(path[1])
      del_path.append(paths[i])
      continue
    
    if path[1] in passed_room:
      if path[0] in passed_room+tmp_passed:
        del_path.append(paths[i])
        continue
      result.append((path[0], path[1]))
      tmp_passed.append(path[0])
      del_path.append(paths[i])
      continue
  depth += 1
  passed_room  = passed_room + tmp_passed
  paths = [path for path in paths if path not in del_path]
  
  if len(tmp_passed) == 0:
    break

if len(set(passed_room)) != N:
  print('No')
else:
  result = sorted(result)
  print('Yes')
  for i, j in result:
    print(j)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque
    from sys import stdin
    readline = stdin.readline

    n,m = map(int, readline().split())
    abl =[[]for i in range(n)]
    for i in range(m):
        a,b = map(int,readline().split())
        abl[a-1].append(b)
        abl[b-1].append(a)
    
    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while any(wk):
        i=wk.pop()
        il=deque(abl[i-1])
        lil=len(il)
        for k in range(lil):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if not(any(wk)):
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque
    from sys import stdin
    readline = stdin.readline
    n,m = map(int, readline().split())
    abl =[[]for i in range(n)]
    for i in range(m):
        a,b = map(int,readline().split())
        abl[a-1].append(b)
        abl[b-1].append(a)

    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while any(wk):
        i=wk.pop()
        il=deque(abl[i-1])
        for k in range(len(il)):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if not(any(wk)):
            wk=deque(wwk)
            j=len(wk)
            wwk=deque([])
    print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque
    from sys import stdin
    readline = stdin.readline
    n,m = map(int, readline().split())
    abl =[[]for i in range(n)]
    for i in range(m):
        a,b = map(int,readline().split())
        abl[a-1].append(b)
        abl[b-1].append(a)

    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while any(wk):
        i=wk.pop()
        il=deque(abl[i-1])
        for k in range(len(il)):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if not(any(wk)):
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque

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

    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while any(wk):
        i=wk.pop()
        il=deque(abl[i-1])
        for k in range(len(il)):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if not(any(wk)):
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque

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

    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while any(wk):
        i=wk.pop()
        il=deque(abl[i-1])
        while any(il):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if not(any(wk)):
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    import sys
    from collections import deque

    n,m = map(int,input().split())
    ab = [[int(i) for i in input().split()] for i in range(m)]
    abl=[[] for i in range(n)]
    for i in range(len(ab)):
        abl[ab[i][0]-1].append(ab[i][1])
        abl[ab[i][1]-1].append(ab[i][0])

    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while any(wk):
        i=wk.pop()
        il=deque(abl[i-1])
        while any(il):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if not(any(wk)):
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
from collections import deque

n,m = map(int,input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
abl=[[] for i in range(n)]
for i in range(len(ab)):
    abl[ab[i][0]-1].append(ab[i][1])
    abl[ab[i][1]-1].append(ab[i][0])

an=[0]*(n-1)
i=1
wk=deque([i])
wwk=deque([])
il=deque(abl[0])

while any(wk):
    i=wk.pop()
    il=deque(abl[i-1])
    while any(il):
        iwk=il.pop()
        if an[iwk-2]==0 and iwk>1:
            wwk.append(iwk)
            an[iwk-2]=i
            if all(an):
                print('Yes')
                for i in an:
                    print(i)
                sys.exit()
    if not(any(wk)):
        wk=deque(wwk)
        wwk=deque([])
print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
from collections import deque

n,m = map(int,input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
abl=[[] for i in range(n)]
for i in range(len(ab)):
    abl[ab[i][0]-1].append(ab[i][1])
    abl[ab[i][1]-1].append(ab[i][0])

an=[0]*(n-1)
i=1
wk=deque([i])
wwk=deque([])
il=deque(abl[0])

while any(wk):
    i=wk.pop()
    il=abl[i-1]
    while any(il):
        iwk=il.pop()
        if an[iwk-2]==0 and iwk>1:
            wwk.append(iwk)
            an[iwk-2]=i
            if all(an):
                print('Yes')
                for i in an:
                    print(i)
                sys.exit()
    if not(any(wk)):
        wk=deque(wwk)
        wwk=deque([])
print('No')

Submission status: Time Limit Exceeded

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

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

for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    x[x1].append(y1)
    x[y1].append(x1)

ans = [10**10] * n
ans[0] = 0
root = [10**10] * n
root[0] = 0

from collections import deque
q = deque() # FIFOキューの作成
for i in x[1]:
    q.append((1,i))#現在の深さ、次に行ける所
    root[i-1] = 1

while q:
    a,b = q.popleft() #aが現在の位置　bが次に行く所

    if (ans[a-1] + 1) < ans[b-1]:
        root[b-1] = a
    ans[b - 1] = min(ans[a - 1] + 1, ans[b - 1])

    for i in x[b]:
        if ans[i-1] > (ans[a-1]+1):
            q.append((b,i))


for i in ans[1:]:
    if i == 10**10:
        print("No")
        exit()

print("Yes")
for i in root[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1 for _ in range(N)]
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist,pre):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
        pre[vertex] = v
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist,pre)
N,M = map(int,input().split())
dist = [-1] * N
seen = [False] * N
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
pre = [0] * N
bfs(0,G,queue,dist,pre)
print("Yes")
for v in range(1,N): 
    print(pre[v]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist,pre):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
        pre[vertex] = v
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist,pre)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
pre = [0 for _ in range(N)]
bfs(0,G,queue,dist,pre)
print("Yes")
for v in range(1,N): 
    print(pre[v]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
print("Yes")
for v in range(1,N): 
    for el in G[v]:
        if dist[el] + 1 == dist[v]:
            print(el+1)
            break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
print("Yes")
for v in range(1,N): 
    L = [el for el in G[v] if dist[el] + 1 == dist[v]]
    ans.append(L[0])
    print(L[0]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
for v in range(1,N): 
    L = [el for el in G[v] if dist[el] + 1 == dist[v]]
    if L == []:
        print("No")
        sys.exit(0)
    else:
        ans.append(L[0])
print("Yes")
for el in ans:
    print(el+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
memo = [0] * (max(dist)+1)
for i in range(max(dist)+1):
    k = dist.count(i)
    memo[i] = k
for v in range(1,N): 
    for el in G[v]: 
        if dist[v] == dist[el] + 1:
            ans.append(el+1)
            count += 1
            break
    if count != v: 
        print("No")
        sys.exit(0)
print("Yes")
for el in ans:
    print(el)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
for v in range(1,N): 
    for el in G[v]: 
        if dist[v] == dist[el] + 1:
            ans.append(el+1)
            count += 1
            break
    if count != v : 
        print("No")
        sys.exit(0)
print("Yes")
for el in ans:
    print(el)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
for v in range(1,N): 
    for el in G[v]: 
        if dist[v] == dist[el] + 1:
            ans.append(el+1)
            count += 1
            break
if count == N-1:
  print("Yes")
  for el in ans:
    print(el)
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
for v in range(1,N): 
    for el in G[v]: 
        if dist[v] == dist[el] + 1:
            ans.append(el+1)
            count += 1
            break
if count == N-1:
  print("Yes")
  for el in ans:
    print(el)
else:
  print("No")

Submission status: Time Limit Exceeded

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

(N, M), *miti = [[*map(int, line.split())] for line in open(0)]

# print(miti)

A = [list() for _ in range(N+1)]
for m in miti:
    a, b = m
    A[a].append(b)
    A[b].append(a)

# print(A)

ans = [0] * (N + 1)
dist = [N] * (N + 1)


def check(p, d):
    for t in A[p]:
        if d + 1 < dist[t]:
            dist[t] = d + 1
            ans[t] = p
            check(t, d + 1)


dist[1] = 0
ans[1] = 88888
check(1, 0)

dist = dist[1:]
ans = ans[2:]
if all(d < N for d in dist):
    print("Yes")
    for a in ans:
        print(a)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import collections as cl

def bfs(queue, connection_nodes, cost, depth) :
    current_cost = 0
    current_depth = 0
    next_nodes = set()
    visited = set()

    while queue :
        node = queue.popleft()
        if (node in visited) :
            continue
        
        visited.add(node)

        if (current_cost < cost[node]) :
            cost[node] = current_cost
            # TODO あとから更新されるケースってあるですか？
            depth[current_depth].append(node)
        
        for n in connection_nodes[node] :
            next_nodes.add(n)

        if (len(queue) == 0) :
            # 一旦全部処理したら、次のノードを設定
            current_cost += 1
            current_depth += 1
            next_nodes = (next_nodes - visited)
            for item in next_nodes:
                queue.append(item)
            # queue = cl.deque(next_nodes - visited)

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

    connection_nodes = [set() for i in range(N)]
    for i in range(M) :
        a,b = map(int,input().split())
        a = a-1
        b = b-1
        connection_nodes[a].add(b)
        connection_nodes[b].add(a)

    # 各ノードに対する最短ステップのラベル
    cost = [1000000000] * N
    # 各深さのノードを保持するラベル
    #   = 各コストのノードを保持
    depth = [[] for i in range(N)]

    queue = cl.deque()
    queue.append(0) # 初期ノード
        
    bfs(queue, connection_nodes,cost,depth)

    # print(cost,depth)

    # 最初のノードは出力しない
    print("Yes")
    for i in range(1,N) :
        dep = cost[i]
        target_nodes = depth[dep-1]
        for tg in target_nodes :
            if (tg in connection_nodes[i]) :
                print(tg+1)
                break
        # for cn in connection_nodes[i] :
        #     if (cn in target_nodes) :
        #         print(cn+1) #0-indexを1-indexにする
        #         break


        



main()

Submission status: Time Limit Exceeded

Solution code:
import collections as cl

def bfs(queue, connection_nodes, cost, depth) :
    current_cost = 0
    current_depth = 0
    next_nodes = set()
    visited = set()

    while queue :
        node = queue.popleft()
        visited.add(node)

        if (current_cost < cost[node]) :
            cost[node] = current_cost
            # TODO あとから更新されるケースってあるですか？
            depth[current_depth].append(node)
        
        for n in connection_nodes[node] :
            next_nodes.add(n)

        if (len(queue) == 0) :
            # 一旦全部処理したら、次のノードを設定
            current_cost += 1
            current_depth += 1
            next_nodes = (next_nodes - visited)
            for item in next_nodes:
                queue.append(item)
            # queue = cl.deque(next_nodes - visited)

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

    connection_nodes = [set() for i in range(N)]
    for i in range(M) :
        a,b = map(int,input().split())
        a = a-1
        b = b-1
        connection_nodes[a].add(b)
        connection_nodes[b].add(a)

    # 各ノードに対する最短ステップのラベル
    cost = [1000000000] * N
    # 各深さのノードを保持するラベル
    #   = 各コストのノードを保持
    depth = [[] for i in range(N)]

    queue = cl.deque()
    queue.append(0) # 初期ノード
        
    bfs(queue, connection_nodes,cost,depth)

    # print(cost,depth)

    # 最初のノードは出力しない
    print("Yes")
    for i in range(1,N) :
        dep = cost[i]
        target_nodes = depth[dep-1]
        for tg in target_nodes :
            if (tg in connection_nodes[i]) :
                print(tg+1)
                break
        # for cn in connection_nodes[i] :
        #     if (cn in target_nodes) :
        #         print(cn+1) #0-indexを1-indexにする
        #         break


        



main()

Submission status: Time Limit Exceeded

Solution code:
import collections as cl

def bfs(queue, connection_nodes, cost, depth) :
    current_cost = 0
    current_depth = 0
    next_nodes = set()
    visited = set()

    while queue :
        node = queue.popleft()
        visited.add(node)

        if (current_cost < cost[node]) :
            cost[node] = current_cost
            # TODO あとから更新されるケースってあるですか？
            depth[current_depth].append(node)
        
        for n in connection_nodes[node] :
            next_nodes.add(n)

        if (len(queue) == 0) :
            # 一旦全部処理したら、次のノードを設定
            current_cost += 1
            current_depth += 1
            queue = cl.deque(next_nodes - visited)

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

    connection_nodes = [set() for i in range(N)]
    for i in range(M) :
        a,b = map(int,input().split())
        a = a-1
        b = b-1
        connection_nodes[a].add(b)
        connection_nodes[b].add(a)

    # 各ノードに対する最短ステップのラベル
    cost = [1000000000] * N
    # 各深さのノードを保持するラベル
    #   = 各コストのノードを保持
    depth = [[] for i in range(N)]

    queue = cl.deque()
    queue.append(0) # 初期ノード
        
    bfs(queue, connection_nodes,cost,depth)

    # print(cost,depth)

    # 最初のノードは出力しない
    print("Yes")
    for i in range(1,N) :
        dep = cost[i]
        target_nodes = depth[dep-1]
        for tg in target_nodes :
            if (tg in connection_nodes[i]) :
                print(tg+1)
                break
        # for cn in connection_nodes[i] :
        #     if (cn in target_nodes) :
        #         print(cn+1) #0-indexを1-indexにする
        #         break


        



main()

Submission status: Time Limit Exceeded

Solution code:
import collections as cl

def bfs(queue, connection_nodes, cost, depth) :
    current_cost = 0
    current_depth = 0
    next_nodes = set()
    visited = set()

    while queue :
        node = queue.popleft()
        visited.add(node)

        if (current_cost < cost[node]) :
            cost[node] = current_cost
            # TODO あとから更新されるケースってあるですか？
            depth[current_depth].append(node)
        
        for n in connection_nodes[node] :
            next_nodes.add(n)

        if (len(queue) == 0) :
            # 一旦全部処理したら、次のノードを設定
            current_cost += 1
            current_depth += 1
            queue = cl.deque(next_nodes - visited)

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

    connection_nodes = [set() for i in range(N)]
    for i in range(M) :
        a,b = map(int,input().split())
        a = a-1
        b = b-1
        connection_nodes[a].add(b)
        connection_nodes[b].add(a)

    # 各ノードに対する最短ステップのラベル
    cost = [1000000000] * N
    # 各深さのノードを保持するラベル
    #   = 各コストのノードを保持
    depth = [[] for i in range(N)]

    queue = cl.deque()
    queue.append(0) # 初期ノード
        
    bfs(queue, connection_nodes,cost,depth)

    # print(cost,depth)

    # 最初のノードは出力しない
    print("Yes")
    for i in range(1,N) :
        dep = cost[i]
        target_nodes = depth[dep-1]
        for cn in connection_nodes[i] :
            if (cn in target_nodes) :
                print(cn+1) #0-indexを1-indexにする
                break


        



main()

Submission status: Time Limit Exceeded

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

AB = dict()

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

    AB.setdefault(b, [])
    AB[b].append(a)

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

a[1] = 0
current = 1
pos = [1]

while True:
    next_pos = []

    for p in pos:
        for n in AB[p]:
            if a[n] == -1:
                a[n] = p
            next_pos.append(n)

    pos = next_pos

    if not next_pos or -1 not in a[2:]:
        break

if -1 in a[2:]:
    print('No')
else:
    print('Yes')
    for i in a[2:]:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
#inport
import sys
import numpy as np

#input
N,M = map(int, sys.stdin.readline().split())
P = [list(map(int, sys.stdin.readline().split())) for i in range(M)]

#shori
##初期化
P = np.array(P)     
ans = np.zeros((N,2))
tmp_latest = np.zeros(1)
tmp_latest_tmp = np.zeros(1)
tmp_latest[0] = 1
pos_latest = 0
num_latest = 1
ans[0][1] = 1 #部屋1をてがかりありに
flg_pos = 1
flg_fale = 0
num_crew = 1
num_left_room = N-1
left_room = np.zeros(N)

while num_crew < N:
    if flg_pos == 0:
        flg_fale = 1
        break

    flg_pos = 0
    for i in range(num_latest):
        tmp_room_num = tmp_latest[i]
        tmp_root_point = np.where(P == int(tmp_room_num))[0]
        root_loop_n = int(np.size(tmp_root_point))
        for j in range(root_loop_n):
            if P[tmp_root_point[j]][0]==tmp_latest[i]:
                if ans[P[tmp_root_point[j]][1]-1][1]==0:
                    tmp_latest_tmp = np.insert(tmp_latest_tmp, 0, P[tmp_root_point[j]][1])
                    ans[P[tmp_root_point[j]][1]-1][1] = tmp_latest[i]
                    num_crew = num_crew + 1
                    flg_pos = 1
            elif P[tmp_root_point[j]][1]==tmp_latest[i]:
                if ans[P[tmp_root_point[j]][0]-1][1]==0:
                    tmp_latest_tmp = np.insert(tmp_latest_tmp, 0, P[tmp_root_point[j]][0])
                    ans[P[tmp_root_point[j]][0]-1][1] = tmp_latest[i]
                    num_crew = num_crew + 1
                    flg_pos = 1               
        P = np.delete(P, tmp_root_point, axis=0)    

    #Nループ終了時にtmp_latestを更新
    tmp_latest = np.insert(tmp_latest, num_latest, tmp_latest_tmp)
    for j in range(num_latest):
        tmp_latest = np.delete(tmp_latest,0)
    num_latest = np.size(tmp_latest)
    tmp_latest = np.delete(tmp_latest,num_latest-1)
    num_latest = np.size(tmp_latest)
    tmp_latest_tmp = np.zeros(1)

    
if flg_fale == 0:
    print('Yes')
    for i in range(N-1):
        print(int(ans[i+1][1]))
else:
    print('No')