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
import time
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M = IL()
ab = [IL() for i in range(M)]

ans = [-1]*(N+1)
visited = [False]*(N+1)
edge = [[] for i in range(N+1)]
for a,b in ab:
  edge[a].append(b)
  edge[b].append(a)

d = deque([[0, 0, 1]])
while d:
  num, rev, v = d.popleft()
  if visited[v] == False:
    visited[v] = True
    ans[v] = rev
  for x in edge[v]:
    if visited[x] == False:
      d.append([num+1, v, x])

if sum(visited) == N:
  print("Yes")
  for i in range(2,N+1):
    print(ans[i])
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop
N, M = map(int, input().split())

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

task = [] 
used = [0 for _ in range(N)]
min_len = [0 for _ in range(N)]
length = [10**20 for _ in range(N)]
prev_points = [0 for _ in range(N)]
heappush(task, (0, 0, -1))
print("Yes")

while task:
  while task:
    l, p, prev = heappop(task)    
    if used[p] == 0:
      break
  #print(task)
  used[p] = 1
  min_len[p] = l
  prev_points[p] = prev +1 #番号を1ずらす
  
  for j in range(N):
    if I[p][j] == 0: continue
    #print(p,j)
    if length[j] > l+1:
      length[j] = l+1
      heappush(task, (l+1, j, p))
    I[p][j] = 0
    I[j][p] = 0

for i in range(1, N):
  print(prev_points[i])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
start = 0
queue = [start]
pre = [None]*N
pre[0] = 0
while queue:
    v = queue.pop(0)
    for i in adj[v]:
        if pre[i] is None:
            pre[i] = v
            queue.append(i)
if None in pre:
    print("No")
else:
    print("Yes")
    for p in pre[1:]:
        print(p+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from heapq import *
class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)
    def __len__(self):
        return len(self.graph)
    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
    def get_nodes(self):
        return self.graph.keys()
    
class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q, (self.dist[start], start))
        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
    def shortest_distance(self, goal):
        return self.dist[goal]
    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

n,m = map(int,input().split())
g = Graph()
for _ in range(m):
    src,dst = map(int,input().split())
    src -= 1
    dst -= 1
    g.add_edge(src, dst, 1)
    g.add_edge(dst, src, 1)

d = Dijkstra(g, 0)
flag = True
ans = []
for i in range(1,n):
    tmp = d.shortest_path(i)
    if len(tmp) == 1:
        flag = False 
    else:
        ans.append(tmp[-2]+1)
if flag:
    print("Yes")
    for i in ans:
        print(i)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [0 for __ in range(N)] for _ in range(N)]
for path in P:
    A[path[1]-1][path[0]-1]=1
    A[path[0]-1][path[1]-1]=1
#print(A)
depth_list = [0 for _ in range(N)]
next_generation = set([0])
depth = 0
#old_generation = set()
direction = [0 for _ in range(N)]
used = [0 for _ in range(N)]
while len(next_generation)!=0:
    #print('next_gen',next_generation)
    current = next_generation
    for node in next_generation:
        used[node] = 1
    #[old_generation.add(node) for node in next_generation]
    next_generation = set()
    for index in current:
        depth_list[index]=depth
    for node in current:
        #print('node',node,':',A[node])
        
        #print('old',old_generation)
        for i,neighbor in enumerate(A[node]):
            #print("trm",neighbor)

            if neighbor == 1 and used[i]==0:
                #print("unseen",i)
                next_generation.add(i)
                direction[i]=node+1
    depth+=1
if used.count(1) != N:
    print('No')
else:
    print('Yes')
    for d in direction[1:]:
        print(d)
#print(depth_list)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [0 for __ in range(N)] for _ in range(N)]
for path in P:
    A[path[1]-1][path[0]-1]=1
    A[path[0]-1][path[1]-1]=1
#print(A)
depth_list = [0 for _ in range(N)]
next_generation = set([0])
depth = 0
old_generation = set()
direction = [0 for _ in range(N)]
while len(next_generation)!=0:
    #print('next_gen',next_generation)
    current = next_generation
    [old_generation.add(node) for node in next_generation]
    next_generation = set()
    for index in current:
        depth_list[index]=depth
    for node in current:
        #print('node',node,':',A[node])
        
        #print('old',old_generation)
        for i,neighbor in enumerate(A[node]):
            #print("trm",neighbor)

            if neighbor == 1 and i not in old_generation:
                #print("unseen",i)
                next_generation.add(i)
                direction[i]=node+1
    depth+=1
if len(old_generation) != N:
    print('No')
else:
    print('Yes')
    for d in direction[1:]:
        print(d)
#print(depth_list)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [0 for __ in range(N)] for _ in range(N)]
for path in P:
    A[path[1]-1][path[0]-1]=1
    A[path[0]-1][path[1]-1]=1
#print(A)
depth_list = [0 for _ in range(N)]
next_generation = set([0])
depth = 0
old_generation = set()
while len(next_generation)!=0:
    #print('next_gen',next_generation)
    current = next_generation
    [old_generation.add(node) for node in next_generation]
    next_generation = set()
    for index in current:
        depth_list[index]=depth
    for node in current:
        #print('node',node,':',A[node])
        
        #print('old',old_generation)
        for i,neighbor in enumerate(A[node]):
            #print("trm",neighbor)

            if neighbor == 1 and i not in old_generation:
                #print("unseen",i)
                next_generation.add(i)
    depth+=1
if len(old_generation) != N:
    print('No')
else:
    print('Yes')
    for node in range(1,N):
        neighbors = A[node]
        for i,neighbor in enumerate(neighbors):
            if neighbor == 1 and depth_list[i]<depth_list[node]:
                print(i+1)
                break
#print(depth_list)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
i=0
#for room_i in connected_list:
    #print(room_i)
while(True):
    try:
        room_i = connected_list[i]
    except:
        break
    next_room_set = connect_dic[room_i]-next_connect_dic.keys()
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = connect_dic[room_i]-next_connect_dic.keys()
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(list)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].append(b)
    connect_dic[b].append(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = set(connect_dic[room_i])-next_connect_dic.keys()
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(list)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].append(b)
    connect_dic[b].append(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = set(connect_dic[room_i])-set(connected_list)
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(list)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].append(b)
    connect_dic[b].append(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = set(connect_dic[room_i])-set(connected_list)
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        if room_dis_dic[next_room_i] > room_dis_dic[room_i]+1:
            room_dis_dic[next_room_i] = room_dis_dic[room_i]+1
            next_connect_dic[next_room_i] = room_i

if sys.maxsize in room_dis_dic.values():
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
edge = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, sys.stdin.readline().rstrip("\n").split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
footprint = [10**9+7]*n
q = deque()
footprint[0] = 0
for i in edge[0]:
    q.append((i,0))
while q:
    nn,fn = q.popleft()
    if footprint[nn] == 10**9+7:
        footprint[nn] = fn
    for i in edge[nn]:
        if footprint[i] == 10**9+7:
            q.append((i,nn))
if 10**9+7 in footprint:
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(footprint[i]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
roots = [[] for _ in range(n)]
signs = [-1 for _ in range(n)]

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

queue = deque([(0, 0)])

while queue:
    room, org = queue.popleft()
    if signs[room] == -1:
        signs[room] = org
    for root in roots[room]:
        if signs[root] == -1:
            queue.append((root, room))

print('Yes')
for i in signs[1:]:
    print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
def func(ans, dic, keylst):
    if keylst == []:
        return ans
    else:
        array = []
        for i in range(2, N + 1):
            if not(i in ans.keys()):
                for j in keylst:
                    if j in dic[i]:
                        ans[i] = j
                        array.append(i)
                        break
        func(ans, dic, array)


N, M = map(int, input().split())
dic = {}
for i in range(N):
    dic[i + 1] = []

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

ans = {}
keylst = [1]
func(ans, dic, keylst)

flg=True
for i in range(2,N + 1):
    if not(i in ans.keys()):
        flg=False
        break

if flg:
    print('Yes')
    for i in range(2,N + 1):
        print(ans[i])
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(i) for i in input().split()]
rooms=[[] for i in range(N+1)]
for m in range(M):
    a,b=[int(i) for i in input().split()]
    rooms[a]+=[b]
    rooms[b]+=[a]

mark=[0]*(N+1)
mark[1]=1
for i in rooms[1]:
    mark[i]=1
curMarks=set()
curMarks.add(1)
while True:
    nextMarks=set()
    for i in range(2,N+1):
        if mark[i] in curMarks:
            newDst=[]
            for j in rooms[i]:
                if mark[j]!=0:
                    continue
                else:
                    mark[j]=i
                    nextMarks.add(i)
                    newDst+=[j]
            rooms[i]=newDst
    if len(nextMarks)==0:
        break
    curMarks=nextMarks

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

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(i) for i in input().split()]
rooms=[[] for i in range(N+1)]
for m in range(M):
    a,b=[int(i) for i in input().split()]
    rooms[a]+=[b]
    rooms[b]+=[a]

mark=[0]*(N+1)
mark[1]=1
for i in rooms[1]:
    mark[i]=1
curMarks=set()
curMarks.add(1)
while True:
    nextMarks=set()
    for i in range(2,N+1):
        if mark[i] in curMarks:
            for j in rooms[i]:
                if mark[j]!=0:
                    continue
                else:
                    mark[j]=i
                    nextMarks.add(i)
    if len(nextMarks)==0:
        break
    curMarks=nextMarks

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

Submission status: Time Limit Exceeded

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

    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)
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg-1]:
            if an[j-2]==0 and j!=1:
                an[j-2]=itg
                tg.append(j)
            if all(an):
                print('Yes')
                for j in an:
                    print(j)
                sys.exit()

    if all(an):
        print('Yes')
        for j in an:
            print(j)
    else:
        print('No')

main()

Submission status: Time Limit Exceeded

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

    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)
    tg = deque([1])
    wwk =deque([])
    while not(all(an)):
        while len(tg):
            itg = tg.pop()
            for j in abl[itg-1]:
                if an[j-2]==0 and j!=1:
                    an[j-2]=itg
                    wwk.append(j)
                if all(an):
                    print('Yes')
                    for j in an:
                        print(j)
                    sys.exit()
        tg=deque(wwk)
        wwk =deque([])

    if all(an):
        print('Yes')
        for j in an:
            print(j)
    else:
        print('No')

main()

Submission status: Time Limit Exceeded

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

    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)
    tg = deque([1])
    wwk =deque([])
    con =0

    while con<=m*2:
        for i in range(len(tg)):
            itg = tg.pop()
            wk =deque(abl[itg-1])
            for j in range(len(wk)):
                iwk=wk.pop()
                con += 1
                if an[iwk-2]==0 and iwk!=1:
                    an[iwk-2]=itg
                    wwk.append(iwk)
                if all(an):
                    print('Yes')
                    for j in an:
                        print(j)
                    sys.exit()
        tg=deque(wwk)
        wwk =deque([])

    print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
con=[[] for i in range(n+1)]
check=[0 for i in range(n+1)]
for x in lst: con[x[0]].append(x[1]);con[x[1]].append(x[0])
check[1]=1
work=[1]
while check.count(0)>1:
    workc=[]
    for x in work:
        for y in con[x]:
            if check[y] : continue
            else : 
                workc.append(y)
                check[y]=x
    work=workc
print("Yes")
for j in range(2,n+1):
    print(check[j])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
con=[[] for i in range(n+1)]
check=[0 for i in range(n+1)]
for x in lst: con[x[0]].append(x[1]);con[x[1]].append(x[0])
check[1]=1
dis=[[1]]
i=0
while check.count(0)>1:
    work=[]
    for x in dis[i]:
        for y in con[x]:
            if check[y] : continue
            else : 
                work.append(y)
                check[y]=x
    dis.append(work)
    i+=1
print("Yes")
for j in range(2,n+1):
    print(check[j])

Submission status: Time Limit Exceeded

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

    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)
    tg = deque([1])
    wwk =deque([])
    con =0

    while con<=m*2:
        while len(tg)!=0:
            itg = tg.pop()
            wk =deque(abl[itg-1])
            for j in range(len(wk)):
                iwk=wk.pop()
                con += 1
                if an[iwk-2]==0 and iwk!=1:
                    an[iwk-2]=itg
                    wwk.append(iwk)
                if all(an):
                    print('Yes')
                    for j in an:
                        print(j)
                    sys.exit()
        tg=deque(wwk)
        wwk =deque([])

    print('No')


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

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)
tg = deque([1])
wwk =deque([])
con =0

while con<=m*2:
    while len(tg)!=0:
        itg = tg.pop()
        wk =deque(abl[itg-1])
        for j in range(len(wk)):
            iwk=wk.pop()
            con += 1
            if an[iwk-2]==0 and iwk!=1:
                an[iwk-2]=itg
                wwk.append(iwk)
            if all(an):
                print('Yes')
                for j in an:
                    print(j)
                sys.exit()
        
    tg=deque(wwk)
    wwk =deque([])

print('No')

Submission status: Time Limit Exceeded

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

ans = 'No'
st = deque([1])
check = [0]*(N+1)
check[1] = 1
mark = [0]*(N+1)

while st:
  s = st.popleft()
  for t in l[s]:
    if check[t] == 0:
      mark[t] = s
      check[t] = 1
      st.append(t)
  if sum(check) == N:
    ans = 'Yes'
    break

print(ans)
if ans == 'Yes':
  for i in range(2,N+1):
    print(mark[i])

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 len(wk)>0:
        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 len(wk)==0:
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import numpy as np

N, M = [int(x) for x in input().split(" ")]

e = {i: [] for i in range(N)}
for _ in range(M):
  a, b = [int(x)-1 for x in input().split(" ")]
  e[a] = e[a] + [b]
  e[b] = e[b] + [a]

d = np.ones(N, dtype=int) * -1
q = [0]
while len(q) != 0:
  v = q.pop(0)
  for ne in e[v]:
    if d[ne] == -1:
      d[ne] = v
      q.append(ne)

print("Yes")
# for p in prev[1:]:
#   print(p+1)
# print("\n".join([str(p+1) for p in d[1:]]))
for p in d[1:]:
  print(p+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def BFS(n,m,table,dist):
    next = deque([0])
    while next:
        tmp = next.popleft()
        for j in range(n):
            if table[tmp][j] and dist[j]==-1:
                table[tmp][j] = table[j][tmp] = 0
                dist[j] = tmp+1
                next.append(j)
    return not -1 in dist

def main():
    n,m = IL()
    table = [[0]*n for _ in range(n)]
    for _ in range(m):
        a,b = IL()
        table[a-1][b-1] = table[b-1][a-1] = 1
    dist = [-1]*n
    dist[0] = 0
    if BFS(n,m,table,dist):
        print('Yes')
        for i in range(1,len(dist)):
            print(dist[i])
    else:  print('No')
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())
edge=[[] for i in range(N)]
visited=[-1 for i in range(N)]
dist=[1000000000 for i in range(N)]
last=[-1 for i in range(N)]
i=0
dist[0]=0
for i in range(M):
    A,B=map(int,input().split())
    edge[A-1].append(B-1)
    edge[B-1].append(A-1)
Q=deque()
Q.append(0)
while Q:
    i=Q.popleft()
    for j in edge[i]:
        if dist[j]>dist[i]+1:
            dist[j]=dist[i]+1
            last[j]=i+1
        if visited[j]==-1 and (j not in Q):
            Q.append(j)
    visited[i]=1
print("Yes")
for i in range(1,N):
  print(last[i])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
P = [list(map(int,input().split())) for i in range(m)]
minimum=[0]+[n]*(n-1)
answer=[0]*(n-1)
for i in range(n):
  for j in range(m):
    tp=P[j]
    if minimum[tp[0]-1]==i:
      if(minimum[tp[1]-1]>i+1):
        minimum[tp[1]-1]=i+1
        answer[tp[1]-2]=tp[0]
    elif minimum[tp[1]-1]==i:
      if(minimum[tp[0]-1]>i+1):
        minimum[tp[0]-1]=i+1
        answer[tp[0]-2]=tp[1]
  if not n in minimum:
    break
print("Yes")
for i in range(n-1):
  print(answer[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
#import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


def sp_xnxn(n=0):
    """
    args:
        int n: a number of lows to read
    example
        input   1
        retrun  [1]

        input   123
        return  [1,2,3]

        input   123
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        return [int(k) for k in xsxs()]
    else:
        return [[int(k) for k in xsxs()] for _ in range(n)]


def xsxs(n=0):
    """
    args:
        int n: a number of lows to read 
    example:
        input   AA
        retrun  AA

        input   A BBB CC
        return  ["A","BBB","CC"]

        input   A BB CCC
                D
        return  [["A","BBB","CC"],
                ["D"]]
    """
    if n == 0:
        temp = list(input().split())
        if len(temp) == 1:
            return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        return [list(input().split()) for _ in range(n)]


def sp_xsxs(n=0):
    """
    args:
        int n: a number of lows to read 
        example:
            input   A
            retrun  ["A"]

            input   ABC
            return  ["A","B","C"]

            input   ABC
                    D
            return  [["A","B","C"],
                    ["D"]]
    """
    if n == 0:
        return [s for s in xsxs()]
    else:
        return [[s for s in xsxs()] for _ in range(n)]


n, m = xnxn()
a = xnxn(m)

graph = [[] for _ in range(n+1)]
for g in a:
    graph[g[0]].append(g[1])
    graph[g[1]].append(g[0])

# print(graph)

q = [1]
rout = [0]*(n+1)
while q != []:
    for i in graph[q[0]]:
        if rout[i] == 0:
            rout[i] = q[0]
            q.append(i)
    q = q[1:]


if rout != [0]*(n+1):
    print("Yes")
    for i in rout[2:]:
        print(i)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
edge = [[] for i in range(n+1)]
reached = [0 for _ in range(n+1)]
guide = [0 for i in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

print("Yes")
queue = [(e, 1) for e in edge[1]]
counter = 0
while counter < n-1:
    # print(queue)
    e, now = queue.pop(0)
    if reached[e] == 0:
        counter += 1
        reached[e] = 1
        guide[e] = now
        # edge[e].remove(now)
        for next in edge[e]:
            if next != 1 and reached[next] == 0:
                queue.append((next, e))

for i in range(2, n+1):
    print(guide[i])

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i:[] for i in range(n)}
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

que = [0]
res = {0:-1}
while len(que) > 0:
    cur = que.pop(0)
    for _next in graph[cur]:
        if _next in res:
            continue
        res[_next] = cur
        que.append(_next)
if len(res) < n:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(res[i]+1)