Problem:


Score: 400 points

Problem Statement

There is a cave.

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

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

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

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

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

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

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

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

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

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

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

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

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

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

Thus, the objective is satisfied.

Sample Input 2

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

Sample Output 2

Yes
6
5
5
1
1

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



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


Sample output:
Yes
1
2
2

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
b=[]
C=[]
s=[0 for i in range(n)]
s[0] = "Yes"
 
for i in range(m):
  c,d=map(int,input().split())
  a.append(c)
  b.append(d)
 
def Next(be):
  C.clear()
  for j in be:
    for i in range(len(a)):
      if a[i] == j:
        
        if s[b[i]-1]==0 and 0 == be.count(b[i]):
          C.append(b[i])
          s[b[i]-1]=j
        continue
      if b[i] == j:
        
        if s[a[i]-1]==0 and 0 == be.count(a[i]):
          C.append(a[i])
          s[a[i]-1]=j
        continue
  return C
co=[1]
for i in range(m):
  if s.count(0) == 0:
    break
  co = Next(list(co))
 
for i in s:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
b=[]
C=[]
s=[0 for i in range(n)]
s[0] = "Yes"
 
for i in range(m):
  c,d=map(int,input().split())
  a.append(c)
  b.append(d)
 
def Next(be):
  C.clear()
  for j in be:
    for i in range(len(a)):
      if a[i] == j:
        
        if s[b[i]-1]==0 and 0 == be.count(b[i]):
          C.append(b[i])
          s[b[i]-1]=j
        continue
      if b[i] == j:
        
        if s[a[i]-1]==0 and 0 == be.count(a[i]):
          C.append(a[i])
          s[a[i]-1]=j
        continue
  return C
co=[1]
while True:
  if s.count(0) == 0:
    break
  co = Next(list(co))
 
for i in s:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split())
a=[]
ans=[0]*n
ok=[1]
nnn=0
count=0
for x in range(m):
    b=list(map(int, input().split()))
    a.append(b)
for c in range(n):
    for t in range(m):
        for s in range(2):
            if a[t][s] in ok:
                ss=abs(s-1)
                nn=a[t][ss]
                my=a[t][s]
                if ans[nn-1]==0:
                    ans[nn-1]=my
                    count+=1
                    if count==n:
                        ans[0]="Yes"
                        for x in ans:
                            print(x)
                        break
    for x in range(n):
        if ans[x]!=0:
            ok.append(x+1)
if count!=n:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

ab = np.array([], int)
n,m = map(int, input().split())

for i in range(m):
    ab = np.append(ab, list(map(int, input().split())), axis=0)

ab = ab.reshape(m,2)

path = [[] for _ in range(n)]


for i in range(m):
    path[ab[i][0]-1].append(ab[i][1])
    path[ab[i][1]-1].append(ab[i][0])
    
d = deque([0])
dis = np.ones(n, int) * -1
dis[0] = 0

while d:
    hop = d.popleft()
    for i in path[hop]:
        if dis[i-1] == -1:
            d.append(i-1)
            dis[i-1] = hop+1
            
if np.count_nonzero(dis)+1 != n:
    print('No')
else:
    print('Yes')
    for i in range(1,len(dis)):
        print(dis[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

ab = np.array([], int)
n,m = map(int, input().split())

for i in range(m):
    ab = np.append(ab, list(map(int, input().split())), axis=0)

ab = ab.reshape(m,2)

path = []

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

for i in range(m):
    path[ab[i][0]-1].append(ab[i][1])
    path[ab[i][1]-1].append(ab[i][0])
    
d = deque([0])
dis = np.ones(n, int) * -1
dis[0] = 0

while len(d) != 0:
    hop = d.popleft()
    for i in path[hop]:
        if dis[i-1] == -1:
            d.append(i-1)
            dis[i-1] = hop+1
    
    hop += 1
    
if np.count_nonzero(dis)+1 != n:
    print('No')
else:
    print('Yes')
    for i in range(1,len(dis)):
        print(dis[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)] #各node(index)から繋がるnode(value)
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [0 for i in range(N+1)]
    q = deque([1])
    visited = []
    while q:
        node = q.popleft()
        visited.append(node)
        for e in edge[node]:
            if e in visited:
                continue
            if signpost[e] == 0:
                signpost[e] = node
                q.append(e)
    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print('{:.1g}'.format(i))        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

done=[False for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True or i in stack:
        continue
      ans[i]=now+1
      done[i]=True
      stack.append(i)

bfs()
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

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

done=[False for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True or i in stack:
        continue
      ans[i]=now+1
      done[i]=True
      stack.append(i)

bfs()
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

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

done=[False for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True or i in stack:
        continue
      ans[i]=now+1
      stack.append(i)

bfs()
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

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

done=[False for i in range(n)]
dist=[0 for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  dist[0]=0
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True or i in stack:
        continue
      dist[i]=dist[now]+1
      ans[i]=now+1
      stack.append(i)

bfs()
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import copy
import time
import queue
from collections import deque

def main():
    N, M = map(int, input().split(' '))
    root = [list(map(int, input().split(' '))) for i in range(M)]
    signpost = [0 for i in range(N+1)]

    q = deque([1])
    visited = []
    while len(q)!=0:
        #print(q)
        node = q.popleft()
        visited.append(node)
        #探索
        for nodes in root:
            if nodes[0] == node:
                if not (nodes[1] in visited or nodes[1] in q):
                    signpost[nodes[1]] = node
                    q.append(nodes[1])
            elif nodes[1] == node:
                if not (nodes[0] in visited or nodes[0] in q):
                    signpost[nodes[0]] = node
                    q.append(nodes[0])
    #print(visited)
    print('Yes')
    for i in signpost[2:]:
        print('{:.1g}'.format(i))        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
nm = list(map(int,input().split()))
n = nm[0]
m = nm[1]
a = []
b = []
for i in range(0, m):
    ab = list(map(int,input().split()))
    a.append(ab[0])
    b.append(ab[1])
signs = [0]*(n+1)
signs[1]=-1
now = [1]
nexx = []
while True:
    for i in now:
        for j in range(0,m):
            if a[j] == i:
                if signs[b[j]] == 0:
                    signs[b[j]] = i
                    nexx.append(b[j])
            elif b[j] == i:
                if signs[a[j]] == 0:
                    signs[a[j]] = i
                    nexx.append(a[j])
    now=nexx.copy()
    if len(nexx)==0:
        break
    nexx = []
flag = 0
for i in range(2, n+1):
    if signs[i]==0:
        print("No")
        flag = 1
        break
if flag == 0:
    print("Yes")
    for k in range(2,n+1):
        print(signs[k])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

path = [[0] * n for _ in range(n)]
dist = [-1] * n
signs = [-1] * n

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

q = deque()
dist[0] = 0
q.append(0)

while len(q) != 0:
    node = q.popleft()

    for i in range(n):
        if path[node][i] == 0:
            continue
        if dist[i] != -1:
            continue
        dist[i] = dist[node] + 1
        q.append(i)

for i in range(1, n):
    for j in range(n):
        if dist[i] - 1 == dist[j]:
            signs[i] = j + 1
            break
        if j == n - 1:
            print('No')
            exit()

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = [0 for i in range(M)]
B = [0 for i in range(M)]
for i in range(M):
    A[i],B[i] = map(int,input().split())

queue = [1]
check = [1]
next_queue = []
ans = [0 for i in range(N)]
ans[0] = 'Yes'

while(1):
    for i in queue:
        for j in [k for k, x in enumerate(A) if x == i]:
            if B[j] not in check:
                check.append(B[j])
                next_queue.append(B[j])
                ans[B[j]-1] = A[j]
        for j in [k for k, x in enumerate(B) if x == i]:
            if A[j] not in check:
                check.append(A[j])
                next_queue.append(A[j])
                ans[A[j]-1] = B[j]
    queue = next_queue
    next_queue = []
    if len(check) == N:
        break
    
for i in range(N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
def main():
    line = input().split(' ')
    N, M = int(line[0]), int(line[1])
    root = np.asarray([list(map(int, input().split(' '))) for i in range(M)])
    #signpost = [0 for i in range(N+1)]
    signpost = np.zeros(N+1)

    mem1 = [1]
    for i in range(M):
        mem2 = []
        for node in root:
            if node[0] in mem1:
                if signpost[node[1]] == 0 and node[1] != 1:
                    signpost[node[1]] = node[0]
                    mem2.append(node[1])
            elif node[1] in mem1:
                if signpost[node[0]] == 0 and node[0] != 1:
                    signpost[node[0]] = node[1]
                    mem2.append(node[0])
        if len(mem2) == 0:
            break
        mem1.clear()
        #list(set(mem2))
        mem1 = copy.copy(mem2)

    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print('{:.1g}'.format(i))        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    line = input().split(' ')
    N, M = int(line[0]), int(line[1])
    root = [list(map(int, input().split(' '))) for i in range(M)]
    signpost = [0 for i in range(N+1)]

    mem1 = [1]
    while True:
        mem2 = []
        for node in root:
            if node[0] in mem1:
                if signpost[node[1]] == 0 and node[1] != 1:
                    signpost[node[1]] = node[0]
                    mem2.append(node[1])
            elif node[1] in mem1:
                if signpost[node[0]] == 0 and node[0] != 1:
                    signpost[node[0]] = node[1]
                    mem2.append(node[0])
        if len(mem2) == 0:
            break
        mem1.clear()
        #list(set(mem2))
        mem1 = copy.copy(mem2)

    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    line = input().split(' ')
    N, M = int(line[0]), int(line[1])
    root = [list(map(int, input().split(' '))) for i in range(M)]
    signpost = [0 for i in range(N+1)]

    mem1 = [1]
    while True:
        mem2 = []
        for node1, node2 in root:
            if node1 in mem1:
                if signpost[node2] == 0 and node2 != 1:
                    signpost[node2] = node1
                    mem2.append(node2)
            if node2 in mem1:
                if signpost[node1] == 0 and node1 != 1:
                    signpost[node1] = node2 
                    mem2.append(node1)
        if len(mem2) == 0:
            break
        mem1.clear()
        list(set(mem2))
        mem1 = copy.copy(mem2)

    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
path=[[False]*N for i in range(N)]
for i in range(M):
  x,y=map(int,input().split())
  path[x-1][y-1]=True
  path[y-1][x-1]=True

minm=[float('inf')]*N
result=[0]*N
flag=[False]*N
minm[0]=0

while True:
  v=-1
  for i in range(N):
    if (not flag[i]) and (v==-1):
      v=i
    elif (not flag[i]) and minm[i]<minm[v]:
      v=i
  if v==-1:
    break
  flag[v]=True
    
  for j in range(N):
    if path[v][j]==True and minm[j]>minm[v]+1:
      minm[j]=minm[v]+1
      result[j]=v+1
      

print('Yes')
for i in range(N-1):
  print(result[i+1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
path=[[False]*N for i in range(N)]
for i in range(M):
  x,y=map(int,input().split())
  path[x-1][y-1]=True
  path[y-1][x-1]=True

minm=[float('inf')]*N
result=[0]*N
flag=[False]*N
minm[0]=0

while True:
  v=-1
  for i in range(N):
    if (not flag[i]) and (v==-1):
      v=i
    elif (not flag[i]) and minm[i]<minm[v]:
      v=i
  if v==-1:
    break
  flag[v]=True
    
  for j in range(N):
    if path[v][j]==True and minm[j]>minm[v]+1:
      minm[j]=minm[v]+1
      result[j]=v+1
      
if float('inf') in minm:
  print('No')
else:
  print('Yes')
  for i in range(N-1):
    print(result[i+1])

Submission status: Time Limit Exceeded

Solution code:
import math
N, M = [int(s) for s in input().split(" ")]
adj_list = {}
for i in range(N):
  adj_list[i] = []

for _ in range(M):
  a, b = [int(s) for s in input().split(" ")]
  adj_list[a-1].append(b-1)
  adj_list[b-1].append(a-1)

dist = [math.inf for i in range(N)]
prev = [-1 for i in range(N)]
dist[0] = 0
prev[0] = 0
q = [True for i in range(N)]
while any(q):
  mv = math.inf
  idx = -1
  for i, d in enumerate(dist):
    if idx < 0 and q[i]:
      idx = i
    if q[i] and mv > d:
      mv = d
      idx = i
  q[idx] = False
  for j in adj_list[idx]:
    if (dist[j] > dist[idx] + 1):
      dist[j] = dist[idx] + 1
      prev[j] = idx

if math.inf in dist:
  print("No")
else:
  print("Yes")
  for j in prev[1:]:
    print(j + 1)

Submission status: Time Limit Exceeded

Solution code:

def check_room(ans_data, len_data, length, michi_data):
    for michi in michi_data:
        if (len_data[michi[0] - 1] == length) and (ans_data[michi[1] - 1] == 0):
            len_data[michi[1] - 1] = length + 1
            ans_data[michi[1] - 1] = michi[0]
        elif (len_data[michi[1] - 1] == length) and (ans_data[michi[0] - 1] == 0):
            len_data[michi[0] - 1] = length + 1
            ans_data[michi[0] - 1] = michi[1]
    
    return ans_data, len_data
        
        
n, m = tuple([int(x) for x in input().split(' ')])
michi_data = []
ans_data = [0 for _ in range(n)]
ans_data[0] = -1
len_data = [0 for _ in range(n)]
for _ in range(m):
    a, b = tuple([int(x) for x in input().split(' ')])
    michi_data.append([a,b])

len_data[0] = 1
length = 1

while ( 0 in  ans_data):
    old_ans_data = [x for x in ans_data]
    new_ans_data, len_data = check_room(ans_data, len_data, length, michi_data)
    if new_ans_data == old_ans_data:
        break
    length += 1

if 0 not in ans_data:
    print ('Yes')
    for i in range(1,n):
        print(ans_data[i])
else:
    print ('No')

Submission status: Time Limit Exceeded

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

import math

def nearby(room, pathes):
    r = []
    for path in pathes:
        if path[0] == room:
            r.append(path[1])
        elif path[1] == room:
            r.append(path[0])
    return r



numbers = input().split(" ")

n = int(numbers[0])
m = int(numbers[1])

pathes = []
rooms = [-1] * (n + 1)

for i in range(m):
    numbers = input().split(" ")
    pathes.append([int(numbers[0]), int(numbers[1])])


rooms[0] = 0
rooms[1] = 0

flag = True
while flag:
    flag = False
    for i in list(range(n+1))[1:]:
        if rooms[i] != -1:
            for j in nearby(i, pathes):
                if rooms[j] == -1:
                    rooms[j] = i
                    flag = True

if -1 not in rooms:
    print("Yes")
    for i in list(range(n+1))[2:]:
        print(rooms[i])
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
br = [0 for i in range(n-1)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
del ar[0]
cr = [0]
dr = []
for r in cr:
    for i in range(n-1):
        if r in ar[i] and br[i] == 0:
            br[i] = r + 1
            cr.append(i+1)
print("Yes")
for r in br:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
br = [0 for i in range(n-1)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
del ar[0]
cr = [0]
dr = []
while True:
    for r in cr:
        for i in range(n-1):
            if r in ar[i] and br[i] == 0:
                br[i] = r + 1
                dr.append(i+1)
    cr = dr.copy()
    dr.clear()
    if br.count(0) == 0:
        break
print("Yes")
for r in br:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
newarr = input()
newarr = newarr.split()
n = int(newarr[0])
m = int(newarr[1])
dicts = {}
ans = [0] * (n + 1)
for line in range(m):
    newarr = input()
    newarr = newarr.split()
    froom = int(newarr[0])
    sroom = int(newarr[1])
    if froom not in dicts:
        dicts[froom] = []
    if sroom not in dicts:
        dicts[sroom] = []
    dicts[froom].append(sroom)
    dicts[sroom].append(froom)
queue = []
if 1 not in dicts:
    print("No")
else:
    ans[1] = 1
    curarr = dicts[1]
    for i in curarr:
        queue.append(i)
        ans[i] = 1 
    while queue:
        curitem = queue.pop(0)
        if curitem not in dicts:
            continue 
        curarr = dicts[curitem]
        for i in curarr:
            if ans[i] == 0:
                ans[i] = curitem 
                queue.append(i)

    finalans = []
    flag = 0 
    for i in range(2, n + 1):
        if i == 0 :
            flag = 1 
            break 
        finalans.append(ans[i])
    if flag == 1:
        print("No")
    else:
        print("Yes")
        for i in finalans:
            print(i)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
 
#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1].append(b)
    l[b-1].append(a)

#深さのリストを作る
l1=sum(l, []) #一次元化
l1.insert(0,1)
l_depth=list(dict.fromkeys(l1))#深さのリスト
 
#解の出力
print('Yes')
for i in range(1,n):
    #各部屋の通じてる部屋リストを浅い順にソート
    ll=sorted(l[i], key=lambda data:l_depth.index(data))
    print(ll[0])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int, input().split())
alist = []
blist = []
for _ in range(M):
    a,b=map(int, input().split())
    alist.append(a)
    blist.append(b)
rdic = {}
d = deque()
def find_index(n):
    returnlist = []
    for indexa,i in enumerate(alist):
        if i == n:
            returnlist.append(blist[indexa])
    for indexb,i in enumerate(blist):
        if i == n:
            returnlist.append(alist[indexb])
    return returnlist
d.append(1)
rdic[1] = 0
c = 0
while True:
    getlist = find_index(d[0])
    for i in getlist:
        if i not in rdic:
            rdic[i] = d[0]
            d.append(i)
            c+=1
    if c == N-1:
        break
    d.popleft()
print('Yes')
for n in range(2,N+1):
    print(rdic[n])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int, input().split())
alist = []
blist = []
for _ in range(M):
    a,b=map(int, input().split())
    alist.append(a)
    blist.append(b)
rdic = {}
d = deque()
def find_index(n):
    returnlist = []
    for indexa,i in enumerate(alist):
        if i == n:
            returnlist.append(blist[indexa])
    for indexb,i in enumerate(blist):
        if i == n:
            returnlist.append(alist[indexb])
    return returnlist
d.append(1)
rdic[1] = 0
while len(rdic)!=N:
    getlist = find_index(d[0])
    for i in getlist:
        if i not in rdic:
            rdic[i] = d[0]
            d.append(i)
    d.popleft()
print('Yes')
for n in range(2,N+1):
    print(rdic[n])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
 
#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1].append(b)
    l[b-1].append(a)

#深さのリストを作る
l1=sum(l, []) #部屋番のリストを一次元化
l_depth=[1]
l_depth_sub=[0]*n
l_depth_sub[0]+=1
for i in range(len(l1)):
    if l_depth_sub[l1[i]-1]==0:
        l_depth_sub[l1[i]-1]+=1
        l_depth.append(l1[i])
    if l_depth_sub.count(0)==0:break

#解の出力
print('Yes')
for i in range(1,n):
    #各部屋の通じてる部屋リストを浅い順にソート
    ll=sorted(l[i], key=lambda data:l_depth.index(data))
    print(ll[0])

Submission status: Time Limit Exceeded

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

#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1].append(b)
    l[b-1].append(a)

#深さのリストを作る
l_depth=[1]
l_depth_sub=[0]*n
l_depth_sub[0]+=1
for i in range(n):
    for j in range(len(l[i])):
        if l_depth_sub[l[i][j]-1]==0:
            l_depth_sub[l[i][j]-1]+=1
            l_depth.append(l[i][j])               
    if l_depth_sub.count(0)==0:break

#解の出力
print('Yes')
for i in range(1,n):
    #各部屋の通じてる部屋リストを浅い順にソート
    ll=sorted(l[i], key=lambda data:l_depth.index(data))
    print(ll[0])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
l=[[] for _ in range(n)]
for i in range(m):#各部屋の通じてる部屋番のリストを作る
    a=ab[i][0]
    b=ab[i][1]
    l[a-1].append(b)
    l[b-1].append(a)

l_depth=[]
l_depth.append(1)
l_depth_sub=[0]*n
l_depth_sub[0]+=1

for i in range(n):#深さのリストを作る
    for j in range(len(l[i])):
        if l_depth_sub[l[i][j]-1]==0:
            l_depth_sub[l[i][j]-1]+=1
            l_depth.append(l[i][j])
                
    if l_depth_sub.count(0)==0:break

print('Yes')
for i in range(1,n):
    k=10**9
    for j in range(len(l[i])):
        if l_depth.index(l[i][j])<k:
            k=l_depth.index(l[i][j])
    print(l_depth[k])

Submission status: Time Limit Exceeded

Solution code:
#Breadth First Search

#for every node, print the last visited node before reaching itself
#starting from the source
from collections import deque

def bfs(graph,N,source):
    visited=[0]*N
    visited[source]=1
    q=deque([source])
    while len(q)>0:
        node=q.popleft()
        for i in graph[node]:
            if visited[i]==0:
                visited[i]=node+1
                q.append(i)
    return visited

n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
print('Yes')
for i in range(1,n):
    print(bfs(graph,n,0)[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())

b = [[] for i in range(n)]
for i in range(m):
    a=list(map(int,input().split()))
    b[a[1]-1].append(a[0])
    b[a[0]-1].append(a[1])
    
c = [-1 for i in range(n)]
c[0] = 0
q = deque([1])
now = 0
count = 0
while q:
    #print(c,q, now)
    count = count + 1
    if count > n:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        if c[b[now][i] - 1] == -1 and b[now][i] not in q:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            #print(c)
            
#print(c)
print("Yes")
for i in range(1,len(c)):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())

b = [[] for i in range(n)]
for i in range(m):
    a=list(map(int,input().split()))
    b[a[1]-1].append(a[0])
    b[a[0]-1].append(a[1])
    
c = [-1 for i in range(n)]
c[0] = 0
q = deque([1])
now = 0
count = 0
while q:
    #print(c,q, now)
    count = count + 1
    if count > 2 * m:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        if c[b[now][i] - 1] == -1 and b[now][i] not in q:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            #print(c)
            
#print(c)
print("Yes")
for i in range(1,len(c)):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())

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

b = [[] for i in range(n)]
for i in range(m):
    b[a[i][1]-1].append(a[i][0])
    b[a[i][0]-1].append(a[i][1])
    
c = [-1 for i in range(n)]
c[0] = 0
q = deque([1])
now = 0
count = 0
while q:
    #print(c,q, now)
    count = count + 1
    if count > 2 * m:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        if c[b[now][i] - 1] == -1 and b[now][i] not in q:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            #print(c)
            
#print(c)
print("Yes")
for i in range(1,len(c)):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m = map(int,input().split())

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

b = [[] for i in range(n)]
for i in range(m):
    b[a[i][1]-1].append(a[i][0])
    b[a[i][0]-1].append(a[i][1])
    
c = [-1 for i in range(n)]
c[0] = 0
q = deque([1])
now = 0
count = 0
while q:
    #print(c,q, now)
    count = count + 1
    if count > 10 ** 5:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        if c[b[now][i] - 1] == -1 and b[now][i] not in q:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            #print(c)
            
#print(c)
print("Yes")
for i in range(1,len(c)):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
a = list(map(int,input().split()))
k = []
count = []
ans = []
room = []
for i in range(0,a[0]) :
    k.append([])
    count.append([])
    ans.append([])
    if i == 0 :
        room.append(0)
    else :
        room.append(-1)
for i in range(0,a[1]) :
    b = list(map(int,input().split()))
    k[b[0]-1].append(b[1])
    k[b[1]-1].append(b[0])
#print(k)
M = []
poi = []
for i in range(0,a[0]) :
    poi = []
    for j in range(0,len(room)) :
        if j in poi :
            continue
        if 1 in count[j] :
            continue
        if room[j] != -1 :
            count[j].append(1)
            for t in k[j] :
                if room[t-1] == -1 :
                    room[t-1] = j + 1
                    poi.append(t-1)
        else :
            continue
    #print(room)
    if M == room :
        break
    else :
        M = list(room)

room = room[1:]
if -1 in room :
    print("No")
else :
    print("Yes")
    for i in room:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import copy

line_1= input().split(' ')
N= int(line_1[0])
M= int(line_1[1])

passages= []
for x in range(1, M+1):
	line= input().split(' ')
	A= int(line[0])
	B= int(line[1])
	passages.append([A,B])
	passages.append([B,A])

exit_steps={1:[0]}

while 1:
	prev_vers= copy.deepcopy(exit_steps)
	for p in passages:
		if p[0] in exit_steps:
			if p[1] in exit_steps:
				if exit_steps[p[0]][0]+1<exit_steps[p[1]][0]:
					exit_steps[p[1]]= [exit_steps[p[0]][0]+1, p[0]]
			else:		
				exit_steps[p[1]]= [exit_steps[p[0]][0]+1, p[0]]
	if exit_steps== prev_vers:
		break
if len(exit_steps)!= N:
	print('No')
else:
	print('Yes')
	for num in range(2, N+1):		
		print(exit_steps[num][1])