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:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[] for _ in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a].append(b)
    way[b].append(a)

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[] for _ in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a].append(b)
    way[b].append(a)

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[False for j in range(n+1)] for i in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a][b] = True
    way[b][a] = True

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in range(2,n+1):
        if way[room][i] == True:
            q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
n, m, *AB = map(int, open(0).read().split())
G = nx.Graph()
G.add_nodes_from(range(1, n+1))
G.add_edges_from(zip(AB[::2], AB[1::2]))
print('Yes')
T = nx.bfs_tree(G, 1)
for i in range(2, n+1):
    print(*T.predecessors(i))

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
n, m, *AB = map(int, open(0).read().split())
G = nx.Graph()
G.add_nodes_from(range(1, n+1))
for a, b in zip(AB[::2], AB[1::2]):
    G.add_edge(a, b)
print('Yes')
T = nx.bfs_tree(G, 1)
for i in range(2, n+1):
    print(*T.predecessors(i))

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
n, m, *AB = map(int, open(0).read().split())
G = nx.Graph()
G.add_nodes_from(range(1, n+1))
for a, b in zip(AB[::2], AB[1::2]):
    G.add_edge(a, b)
print('Yes')
for i in range(2, n+1):
    print(nx.shortest_path(G, 1, i)[-2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
n,m = map(int,input().split())
 
turo = [[] for i in range(n)]
q = deque()
his = []

for i in range(m):
    a,b = map(int,input().split())
    turo[a-1].append(b-1)
    turo[b-1].append(a-1)
 
par = [i for i in range(n)]
rank = [sys.maxsize for i in range(n)]
rank[0] = 0
q.append(0)

 
while len(q) > 0:
    #print(q)
    room = q.popleft()
    if room not in his:
        his.append(0)
    else:
        continue
    for room2 in turo[room]:
        if rank[room] < rank[room2]:
            q.append(room2)
            par[room2] = room
            rank[room2] = rank[room]+1

if len(his) < n:
    print("No")
    exit()
 
print("Yes")
for i in range(1,n):
    print(par[i]+1)

Submission status: Time Limit Exceeded

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

turo = [[] for i in range(n)]
q = deque()
his = []

def root(x):
    if par[x] == x:
        return x
    else:
        return root(par[x])

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

par = [i for i in range(n)]
q.append(0)
his.append(0)

while len(q) > 0:
    #print(q)
    room = q.popleft()
    #print(room+1)
    for room2 in turo[room]:
        if room2 not in his:
            his.append(room2)
            q.append(room2)
            par[room2] = room

if len(his) < n:
    print("No")
    exit()
 
print("Yes")
for i in range(1,n):
    print(par[i]+1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
graph=[[] for _ in range(n)]

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

sign=[-1]*n
sign[0]=0
work=[]
work_next=graph[0]
for x in work_next:
    sign[x]=0


while work_next:
    work=work_next[:]
    work_next=[]
    for x in work:
        for y in graph[x]:
            if sign[y]>=0 : continue
            if y in work_next : continue
            sign[y]=x
            work_next.append(y)

if -1 in sign : print("No");exit()
print("Yes")
for i in range(1,n):
    print(sign[i]+1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
g = [[] for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
import heapq
hq = []
dis = [float('inf')] * n
res = [-1]*(n-1)
prev = [0] * n
heapq.heappush(hq, (0,0,-1))
while hq:
    c,idx,pre = heapq.heappop(hq)
    if dis[idx] < c:
        continue
    dis[idx] = c
    res[idx-1] = pre
    for i in g[idx]:
        if dis[i] > c + 1:
            heapq.heappush(hq, (c+1, i,idx))
if -1 in res:
    print('No')
    exit()
print('Yes')
for i in range(n-1):
    print(res[i]+1)

Submission status: Time Limit Exceeded

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

m = [[0]*n for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1 and dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]

Submission status: Time Limit Exceeded

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

m = [[0]*n for _ in range(n)]
dp = [-1]*n
from collections import deque
for _ in range(M):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1

que = deque([0])
dp[0] = 0

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1:
      if dp[i] != -1 :continue
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]

Submission status: Time Limit Exceeded

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

m = [[0]*n for _ in range(n)]
dp = [-1]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1

que.append(0)
dp[0] = 0

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1:
      if dp[i] != -1 :continue
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]

Submission status: Time Limit Exceeded

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

m = [[0]*n for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1 and dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

#[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]

Submission status: Time Limit Exceeded

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

m = [[0]*n for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1 and dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

[exit(print('No')) for i in range(1,n)  if dp[i] == 0]

print('Yes')
[print(dp[i]) for i in range(1,n)]

Submission status: Time Limit Exceeded

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

if M < n-1:exit(print('No'))

m = [[0]*n for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1 and dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

for i in range(1,n):
  if dp[i] == 0:exit(print('No'))

print('Yes')
for i in range(1,n):
  print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
n,M = list(map(int,input().split()))
m = [[0]*n for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  m[a][b] = 1
  m[b][a] = 1
  if a == 0:
    que.append(b)
    dp[b] = 1
  if b == 0:
    que.append(a)
    dp[a] = 1

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1 and dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

for i in range(1,n):
  if dp[i] == 0:exit(print('No'))

print('Yes')
for i in range(1,n):
  print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
n,M = list(map(int,input().split()))
m = [[0]*n for _ in range(n)]
dp = [0]*n
from collections import deque
que = deque()
for _ in range(M):
  a,b = list(map(int,input().split()))
  m[a-1][b-1] = 1
  m[b-1][a-1] = 1
  if a == 1:
    que.append(b-1)
    dp[b-1] = 1
  if b == 1:
    que.append(a-1)
    dp[a-1] = 1

while que:
  c = que.popleft()
  for i in range(n):
    if m[c][i] == 1 and dp[i] == 0 :
      dp[i] = c+1
      que.append(i)

for i in range(1,n):
  if dp[i] == 0:exit(print('No'))

print('Yes')
for i in range(1,n):
  print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
#D
from collections import deque
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ans = [0] * (n+1)
for i in range(m):
    ab.append([ab[i][1], ab[i][0]])
ab.sort(key=lambda x: x[0])
#BPS幅優先探索を行う -> 前の座標を記入
nque = deque([1])
while nque:
    now_cave = nque.popleft()
    for i in ab:
        next_cave = i[1]
        if i[0] == now_cave and ans[next_cave] == 0:
            ans[next_cave] = now_cave
            nque.append(next_cave)
print("Yes")
for i in range(2, n + 1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
r=[0]*(n-1)
rr=[0]*(n-1)
ab=[]
lpath=1
for ii in range(m):
  abii=list(map(int,input().split()))
  abii.sort()
  if abii[0]==1:
    kk=abii[1]-1-1
    r[kk]=lpath
    rr[kk]=1
  else:
    ab.append(abii)
"""
print(r)
print(rr)
print(ab)
"""
lenab0=len(ab)
for ll in range(n):
  if lenab0==0:
    break

  lpath+=1
  lenab=lenab0
  nab=[]
  for jj in range(lenab0):
    jjj=(lenab0-1)-jj
    abj0=ab[jjj][0]
    abj02=abj0-2
    abj1=ab[jjj][1]
    abj12=abj1-2
    if r[abj02]==0 and r[abj12]==0:
      nab.append(ab.pop())
    elif r[abj02]>0 and r[abj02]<lpath and r[abj12]>0 and r[abj12]<lpath:
      #del ab[jjj]
      ab.pop()
      lenab-=1
    else:
      #print(ab[jjj])
      if r[abj02]==0 and r[abj12]<lpath:
        r[abj02]=lpath
        rr[abj02]=abj1
        #del ab[jjj]
        ab.pop()
        lenab-=1
      elif r[abj12]==0 and r[abj02]<lpath:
        r[abj12]=lpath
        rr[abj12]=abj0
        #del ab[jjj]
        ab.pop()
        lenab-=1
      else:
        nab.append(ab.pop())
  """
  print(r)
  print(rr)
  print(ab)
  """
  if lenab0==lenab:
    break
  else:
    lenab0=lenab
    ab=nab

if min(r)>0 and min(rr)>0:
  print("Yes")
  for ii in range(len(rr)):
    print(rr[ii])
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
r=[0]*(n-1)
rr=[0]*(n-1)
ab=[]
lpath=1
for ii in range(m):
  abii=list(map(int,input().split()))
  abii.sort()
  if abii[0]==1:
    kk=abii[1]-1-1
    r[kk]=lpath
    rr[kk]=1
  else:
    ab.append(abii)
"""
print(r)
print(rr)
print(ab)
"""
lenab0=len(ab)
for ll in range(n):
  if lenab0==0:
    break

  lpath+=1
  lenab=lenab0
  for jj in range(lenab0):
    jjj=(lenab0-1)-jj
    abj0=ab[jjj][0]
    abj02=abj0-2
    abj1=ab[jjj][1]
    abj12=abj1-2
    if r[abj02]==0 and r[abj12]==0:
      pass
    elif r[abj02]>0 and r[abj02]<lpath and r[abj12]>0 and r[abj12]<lpath:
      del ab[jjj]
      lenab-=1
    else:
      #print(ab[jjj])
      if r[abj02]==0 and r[abj12]<lpath:
        r[abj02]=lpath
        rr[abj02]=abj1
        del ab[jjj]
        lenab-=1
      elif r[abj12]==0 and r[abj02]<lpath:
        r[abj12]=lpath
        rr[abj12]=abj0
        del ab[jjj]
        lenab-=1
  """
  print(r)
  print(rr)
  print(ab)
  """
  if lenab0==lenab:
    break
  else:
    lenab0=lenab    

if min(r)>0 and min(rr)>0:
  print("Yes")
  for ii in range(len(rr)):
    print(rr[ii])
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
r=[0]*(n-1)
rr=[0]*(n-1)
ab=[]
lpath=1
for ii in range(m):
  abii=list(map(int,input().split()))
  abii.sort()
  if abii[0]==1:
    kk=abii[1]-1-1
    r[kk]=lpath
    rr[kk]=1
  else:
    ab.append(abii)
"""
print(r)
print(rr)
print(ab)
"""
for ll in range(n):
  lpath+=1
  lenab0=len(ab)
  if lenab0==0:
    break
  for jj in range(lenab0):
    jjj=(lenab0-1)-jj
    abj0=ab[jjj][0]
    abj02=abj0-2
    abj1=ab[jjj][1]
    abj12=abj1-2
    if r[abj02]==0 and r[abj12]==0:
      pass
    elif r[abj02]>0 and r[abj02]<lpath and r[abj12]>0 and r[abj12]<lpath:
      del ab[jjj]
    else:
      #print(ab[jjj])
      if r[abj02]==0 and r[abj12]<lpath:
        iii=abj1
        kk=abj02
        r[kk]=lpath
        rr[kk]=iii
        del ab[jjj]
      elif r[abj12]==0 and r[abj02]<lpath:
        iii=abj0
        kk=abj12
        r[kk]=lpath
        rr[kk]=iii
        del ab[jjj]

  """
  print(r)
  print(rr)
  print(ab)
  """
  if lenab0==len(ab):
    break
#import numpy as np
if min(r)>0 and min(rr)>0:
  print("Yes")
  for ii in range(len(rr)):
    print(rr[ii])
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
r=[0]*(n-1)
rr=[0]*(n-1)
ab=[]
lpath=1
for ii in range(m):
  abii=set(map(int,input().split()))
  #print(abii)
  if 1 in abii:
    abii.remove(1)
    kk=abii.pop()-1-1
    r[kk]=lpath
    rr[kk]=1
  else:
    ab.append(abii)
#print(r,ab)
while len(ab)>0:   
  lpath+=1
  for ii in range(n-1):
    iii=ii+1+1
    if r[ii]==lpath-1:
      lenab0=len(ab)
      for jj in range(lenab0):
        jjj=(lenab0-1)-jj
        if iii in ab[jjj]:
          ab[jjj].remove(iii)
          kk=ab[jjj].pop()-1-1
          if r[kk]==0:
            r[kk]=lpath
            rr[kk]=iii
          ab.pop(jjj)
        else:
          pass

import numpy as np
if min(r)>0 and min(rr)>0:
  print("Yes")
  for ii in range(len(rr)):
    print(rr[ii])
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
import queue

N, M = map(int, input().split())
g = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    g[A-1].append(B)
    g[B-1].append(A)

ans = [-1] * N
ans[0] = 0
q = queue.Queue()
q.put(1)
while any(i == -1 for i in ans) and not q.empty():
    now = q.get()
    for i in g[now-1]:
        if ans[i-1] != -1:
            continue
        ans[i-1] = now
        q.put(i)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
g = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    g[A-1].append(B)
    g[B-1].append(A)

ans = [-1] * N
ans[0] = 0
d = deque([1])
while any(i == -1 for i in ans) and len(d) != 0:
    now = d[0]
    d.popleft()
    for i in g[now-1]:
        if ans[i-1] != -1:
            continue
        ans[i-1] = now
        d.append(i)

if any(i == -1 for i in ans):
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]

ans = [-1] * N
ans[0] = 0
d = deque([1])
while any(i == -1 for i in ans) and len(d) != 0:
    now = d[0]
    d.popleft()
    for i in itertools.product(range(M), range(2)):
        if AB[i[0]][i[1]] == now:
            if ans[AB[i[0]][1 - i[1]] - 1] == -1:
                ans[AB[i[0]][1 - i[1]] - 1] = now
                d.append(AB[i[0]][1 - i[1]])

if any(i == -1 for i in ans):
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]

ans = [-1] * N
ans[0] = 0
d = deque([1])
while any(i == -1 for i in ans) and any(i != [-1, -1] for i in AB):
    now = d[0]
    for i in itertools.product(range(M), range(2)):
        if AB[i[0]][i[1]] == now:
            if ans[AB[i[0]][1 - i[1]] - 1] == -1:
                ans[AB[i[0]][1 - i[1]] - 1] = now
                d.append(AB[i[0]][1 - i[1]])
            AB[i[0]] = [-1, -1]
    d.popleft()

if any(i == -1 for i in ans):
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
inlist=input("").split(" ")
n=int(inlist[0])
m=int(inlist[1])
lista=[]
listb=[]
for i in range(n):
    lista+=[[]]
    listb+=[-1]
listb[0]=-2
listnum=[0]
for i in range(m):
    inlist=input("").split(" ")
    s=int(inlist[0])
    t=int(inlist[1])
    lista[s-1]+=[t-1]
    lista[t-1]+=[s-1]
k=0
while(k<len(listnum)):
    for i in lista[listnum[k]]:
        if not(i in listnum):
            listnum+=[i]
            listb[i]=listnum[k]
    k+=1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(graph, visited, ss, g):
  queue = deque([ss])
  visited[ss] = 0
  while queue:
    s = queue.popleft()
    #　返り値に関する条件
    if visited[g] != -1 :
        return visited
    for new_s in range(n) :
      if graph[new_s][s] == 1 and visited[new_s] == -1:
        #　移動回数の計算
        visited[new_s] = visited[s] + 1
        queue.append(new_s)
  return visited

n,m = map(int,input().split())
graph = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    a,b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
 
d = [0]*n
for g in range(1,n) :
    visited = [-1]*n
    d[g] = bfs(graph, visited, 0, g)[g]

maxd = max(d)
dpt = [[] for i in range(maxd+1)]
for i in range(maxd+1) :
    dpt[i] = [n for n, v in enumerate(d) if v == i]

if -1 in d :
    print('No')
else :
    print('Yes')
    for i in range(1,n) :
        print(dpt[d[i]-1][0]+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = [[] for _ in range(N+1)]
    for _ in range(M):
        (A,B) = map(int, input().split())
        neighbor[A] += B,
        neighbor[B] += A,

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor[n]
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: not d in checked, dests)
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            checked += d,
            # 探索候補の末尾に追加
            target += d,

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

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = {}
    for _ in range(M):
        (A,B) = map(int, input().split())
        na = neighbor.get(A, [])
        nb = neighbor.get(B, [])
        neighbor.update({A:(na+[B])})
        neighbor.update({B:(nb+[A])})

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor.get(n, [])
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: not d in checked, dests)
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            checked += d,
            # 探索候補の末尾に追加
            target += d,

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

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = {}
    for _ in range(M):
        (A,B) = map(int, input().split())
        na = neighbor.get(A, [])
        nb = neighbor.get(B, [])
        neighbor.update({A:(na+[B])})
        neighbor.update({B:(nb+[A])})

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor.get(n, [])
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: not d in checked, dests)
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            checked += d,
            # 探索候補の末尾に追加
            target += d,

    if set(range(1,N+1)) <= set(guide.keys()):
        print('Yes')
        for i in range(2,N+1):
            print(guide[i])
    else:
        print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = {}
    for _ in range(M):
        (A,B) = map(int, input().split())
        na = neighbor.get(A, [])
        nb = neighbor.get(B, [])
        neighbor.update({A:(na+[B])})
        neighbor.update({B:(nb+[A])})

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor.get(n, [])
        # すでに道しるべがあるものは除く
        dests = list(filter(lambda d: not d in guide.keys(), dests))
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            # 探索候補の末尾に追加
            target += d,

    if set(range(1,N+1)) <= set(guide.keys()):
        print('Yes')
        for i in range(2,N+1):
            print(guide[i])
    else:
        print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    path = []
    for _ in range(M):
        (A,B) = map(int, input().split())
        path += (A,B),

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びるパス
        pn = list(filter(lambda p: n in p, path))
        # nから伸びる行き先
        dests = list(map(lambda p: p[0] if p[0] != n else p[1], pn))
        # すでに道しるべがあるものは除く
        dests = list(filter(lambda d: not d in guide.keys(), dests))
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            # 探索候補の末尾に追加
            target += d,

    if set(range(1,N+1)) <= set(guide.keys()):
        print('Yes')
        for i in range(2,N+1):
            print(guide[i])
    else:
        print('No')

main()

Submission status: Time Limit Exceeded

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

while st:
  x,i=st.pop(0)
  if vi[x]==-1:
    vi[x]=i
    for k in l[x]:
      if vi[k]==-1:
        st.append([k,x])


print("Yes")
for m in vi[2:]:
  print(m)

Submission status: Time Limit Exceeded

Solution code:
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)
    
ans =[1]*2 + [0]*(n-1)
cnt = [1]

while len(A) != 0:
    new_cnt = []
    for c in cnt:
        for i in reversed(range(len(A))):
            if A[i] == c:
                new_cnt.append(B[i])
                del A[i]
                del B[i]
        for i in reversed(range(len(B))):
            if B[i] == c:
                new_cnt.append(A[i])
                del A[i]
                del B[i]
        for i in new_cnt:
            if ans[i] == 0:
                ans[i] = c
    cnt = new_cnt
if 0 in ans:
    print("No")
else:
    print("Yes")
    for i in range(2, n+1):
        print(ans[i])

Submission status: Time Limit Exceeded

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

def bfs(x,i):
  if vi[x]==-1:
    vi[x]=i
    for k in l[x]:
      if vi[k]==-1:
        st.append([k,x])
  return

while st:
  x,i=st.pop(0)
  bfs(x,i)

print("Yes")
for m in vi[2:]:
  print(m)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    n, m = map(int,raw_input().split())
    
    adj_list = [[] for _ in range(n+5)]
    
    q = []
    
    ans = [-1] * (n+5)
    
    failed = False
    
    for _ in range(m):
        a, b = map(int,raw_input().split())    
        adj_list[a].append(b)
        adj_list[b].append(a)
    
    q.append(1)
    
    #print(adj_list)
    
    visited = set()
    
    visited.add(1)
    
    while len(q):
        sz = len(q)
        for _ in range(sz):
            cur = q.pop(0)
            for nei in adj_list[cur]:
                if nei not in visited:
                    ans[nei] = cur
                    q.append(nei)
                    visited.add(nei)
    
    
    print('Yes')
    for i in range(2, n+1):
        print(ans[i])
            
            
        
        
    
    

main()