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=(int(x) for x in input().split())
map=[]
ikisaki=[]
ans=[0]*(N+1)
for n in range(M):
    A=list(int(x) for x in input().split())
    map.append(A)

for n in range(M):
    if map[n][0]==1:
        ikisaki.append(map[n][1])
        ans[map[n][1]]=1
    if map[n][1]==1:
        ikisaki.append(map[n][0])
        ans[map[n][0]]=1
ans[1]=1
while ikisaki:

    u=ikisaki.pop(0)
    for n in range(M):
        if (map[n][0]==u and ans[map[n][1]]==0):
            ikisaki.append(map[n][1])
            ans[map[n][1]]=map[n][0]
        if (map[n][1]==u and ans[map[n][0]]==0):
            ikisaki.append(map[n][0])
            ans[map[n][0]]=map[n][1]
c=0
for n in range(N-1):
    if ans[n+2]==0:
        c=1
if c==1:
    print('No')
else:
    print('Yes')
    for n in range(N-1):
        print(ans[n+2])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path

N, M = map(int, input().split())
a = [[0] * N for _ in range(N)]

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

a = np.array(a)
a, b = shortest_path(a, indices=0, return_predecessors=True)

if -1 in np.sign(b[1:]):
    print('No')
    exit()

print('Yes')

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
K = [list(map(int, input().split()))]
if M > 1:
    for i in range(M - 1):
        K.append(list(map(int, input().split())))
K = np.array(K)

S = [0] * N
x = []
l = []
for i in range(K.shape[0]):
    if K[i,0] == 1:
        S[K[i,1]-1] = 1
        x.append(K[i,1])
        l.append(i)
    elif K[i,1] == 1:
        S[K[i,0]-1] = 1
        x.append(K[i,0])
        l.append(i)
K = np.delete(K, l, 0)

while len(x) != 0:
    y = []
    l = []
    for i in range(K.shape[0]):
        for j in range(len(x)):
            if K[i,0] == x[j]:
                if S[K[i,1]-1] == 0:
                    S[K[i,1]-1] = x[j]
                    y.append(K[i,1])
                    l.append(i)
            elif K[i,1] == x[j]:
                if S[K[i,0]-1] == 0:
                    S[K[i,0]-1] = x[j]
                    y.append(K[i,0])
                    l.append(i)
    x = y
    K = np.delete(K, l, 0)

flag = 0
for i in range(1, len(S)):
    if S[i] == 0:
        flag = 1
        print("No")
        break
if flag == 0:
    print("Yes")
    for i in range(1, len(S)):
        print(S[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, M = map(int, input().split())
    route = [[] for _ in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        route[a-1].append(b-1)
        route[b-1].append(a-1)
    
    arrive_time = [0] + [-1] * (N - 1)
    arrive_route = [0] + [-1] * (N - 1)
    q = deque()
    q.append(0)
    while len(q):
        idx = q.pop()
        for c in route[idx]:
            if arrive_time[c] >= 0 and arrive_time[c] <= arrive_time[idx]+1:
                continue
            arrive_time[c] = arrive_time[idx]+1
            arrive_route[c] = idx
            q.append(c)
    if min(arrive_time) < 0:
        print("No") 
    else:
        print("Yes")
        for r in arrive_route[1:]:
            print(r+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

#room_li = list(range(1,n+1))

answer_li  = [0]*n

now_li  = [1]

next_now = []

delete_li = []

while True:
    for n in now_li:
        for i, r in enumerate(root):
            if n in r:
                #root.pop(i)
                delete_li.append(i)
                r.remove(n)
                dest = r[0]
                if answer_li[dest-1] == 0:
                    answer_li[dest-1] = n
                next_now.append(dest)
        cnt = 0
        for d in delete_li:
            root.pop(d-cnt)
            cnt += 1
        delete_li = []
    now_li = next_now
    next_now = []

    if len(root) <=1:
        break
answer_li = answer_li[1:]
if 0 not in answer_li:
    print('Yes')
    for i in answer_li:
        print(i)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[Tuple[int, int]], n: int) -> List[int]:
    passages = defaultdict(set)
    for a, b in values:
        passages[a].add(b)
        passages[b].add(a)
    to_visit = deque((1,))
    visited = set()
    distances = defaultdict(lambda: sys.maxsize)
    distances[1] = 0
    signs = {}
    while to_visit:
        cur = to_visit.popleft()
        for neighbour in passages[cur]:
            tmp = distances[cur] + 1
            if distances[neighbour] > tmp:
                distances[neighbour] = distances[cur] + 1
                signs[neighbour] = cur
            if neighbour not in visited:
                to_visit.append(neighbour)
        visited.add(cur)
    # LOG.debug((visited, to_visit))
    if len(visited) < n:
        return []
    return [signs[i] for i in range(2, n + 1)]


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    N, M = map(int, stdin.readline().split())
    values = []
    for _ in range(M):
        a, b = map(int, stdin.readline().split())
        values.append((a, b))
    result = solve(values, N)
    if not result:
        print("No", file=stdout)
    else:
        print("Yes", file=stdout)
        print("\n".join(map(str, result)), file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    # pylint: disable=super-init-not-called
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(v) for v in input().split(" ")]

paths = []
for i in range(M):
  paths.append([int(v) - 1 for v in input().split(" ")])

marks = [-1 for _ in range(N)]
hops = [999999999 for _ in range(N)]
marked = [0]
marks[0] = 0
hops[0] = 0

hops_prev = sum(hops)
break_ = False
while True:
  for path_index in range(len(paths)):
    path = paths[path_index]
    
    for path in [(path[0], path[1]), (path[1], path[0])]:
      if path[1] in marked:
        continue
        
      hop_ = hops[path[1]]
      hop = hops[path[0]] + 1
      if hop_ > hop:
        marks[path[1]] = path[0]
        hops[path[1]] = hop
        
        if path[0] in marked:
          marked.append(path[0])
          
          if len(marked) == M:
            break_ = True
            break
      if break_:
        break
  if break_:
    break
  if hops_prev == sum(hops):
    break
  else:
    hops_prev = sum(hops)
     

if min(hops) >= 999999999:
  print("No")
else:
  print("Yes")
  [print(v+1) for v in marks[1:]]

Submission status: Time Limit Exceeded

Solution code:
def readinput():
    n,m=list(map(int,input().split()))
    rooms = [
        [[],-1,-1] for _ in range(n)
        ]
    for _ in range(m):
        a,b = list(map(int,input().split()))
        rooms[a-1][0].append(b)
        rooms[b-1][0].append(a)
    return n,m,rooms

def labelNext(target, rooms, nokori, cost):
    oitaList=[]
    for i, room in enumerate(rooms):
        if (target in room[0]) and (room[1] == -1):
            room[1] = target
            room[2] = cost
            oitaList.append(i+1) # 道しるべをおいた部屋番号のリストにするので+1
    nokori -= set(oitaList)  #　道しるべを置いた部屋番号を削除
    return oitaList

def main(n,m,rooms):
    nokori=set(range(2,n+1))  # 道しるべを置いてない部屋番号の集合 (1を除くすべて)
    target=1
    cost=1
    nextList=labelNext(target,rooms, nokori, cost)
    while(len(nokori)>0):
        cost+=1
        nl=[]
        for n in nextList:
            nl.append(labelNext(n,rooms,nokori,cost))
            if(len(nokori)==0):
                break
        nextList=nl
    labelList=[]
    for room in rooms:
        labelList.append(room[1])   
    labelList.pop(0)     
    return labelList

if __name__=='__main__':
    n,m,rooms=readinput()
    labelList=main(n,m,rooms)
    print('Yes')
    for l in labelList:
        print(l)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
d = {}
for _ in range(M):
    tmp = list(map(int,input().split()))
    if tmp[0] in d.keys():
        d[tmp[0]].append(tmp[1])
    else:
        d[tmp[0]] = [tmp[1]]
    if tmp[1] in d.keys():
        d[tmp[1]].append(tmp[0])
    else:
        d[tmp[1]] = [tmp[0]]

check = [0 for _ in range(N+1)]
lv_check = [0 for _ in range(N+1)]
p = 0
q = [1]
lv = [0]
while len(q):
    p = q.pop(0)
    l = lv.pop(0)
    n = []
    ln = []
    for a in d[p]:
        if check[a] == 0 or lv_check[a] > l+1:
            check[a] = p
            lv_check[a] = l+1
            n.append(a)
            ln.append(l+1)
    q = n + q
    lv = ln + lv

for c in check[2:]:
    if c == 0:
        print('No')
        break
else:
    print('Yes')
    for c in check[2:]:
        print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

def bfs(graph, start):
    queue = deque([start])
    visited = set()
    distance = defaultdict(int)
    distance[start] = 0
    while queue:
        current_vertex = queue.popleft()
        visited.add(current_vertex)
        for v in graph[current_vertex]:
            if v not in visited and v not in queue:
                queue.append(v)
                distance[v] = distance[current_vertex] + 1
    return distance

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

distance = bfs(graph, 1)

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

    found = False
    for j in graph[i]:
        if distance[j] == distance[i] - 1:
            ans_list.append(j)
            found = True
            break
    if not found:
        ans = 'No'

if ans == 'No':
    print(ans)
else:
    print(ans)
    for x in ans_list:
        print(x)

Submission status: Time Limit Exceeded

Solution code:
s = input().split()

N = int(s[0])
M = int(s[1])

A = []
B = []

for i in range(M):
  t = input().split()
  A.append(int(t[0]))
  B.append(int(t[1]))

now = 1
d = []
for i in range(N):
  d.append(M*2)
d[0] = 0
Q = []
for i in range(N):
  Q.append(i+1)

result = []
for i in range(N):
  result.append(0)
    
while(len(Q) != 0):
  mi = 0
  le = 3 * M
  for i in Q:
    if d[i-1] < le:
      le = d[i-1]
      mi = i
  Q.remove(mi)
  
  for k in range(M):
    if A[k] == mi and result[B[k]-1] == 0:
      result[B[k]-1] = mi
      d[B[k]-1] = d[mi-1] + 1
    elif B[k] == mi and result[A[k]-1] == 0:
      result[A[k]-1] = mi
      d[A[k]-1] = d[mi-1] + 1

if all([k != 0 for k in result[1:]]):
  print("Yes")
  for i in result[1:]:
    print(i)
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = map(int,input().split())
route_list = [[0]*N for i in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  route_list[a-1][b-1] = 1
  route_list[b-1][a-1] = 1


node_num = N #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [math.inf] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

# @GDaigo さんのコメントより関数の追加 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = math.inf # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]: 
           posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

# 以下で結果の表示
#print("-----距離-----")
ans = ''
j = 1
for i in range(1,N):
  if(i != N-1):
    ans += str(previous_nodes[i]+1)+'\n'
  else:  
    ans += str(previous_nodes[i]+1)
  if(previous_nodes[i]<0):
    j = 0

if(j == 1):
  print('Yes')
  print(ans)
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
road = []
ans = [0] * n
prev = [1]

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

while 0 in ans[1:]:
    next = []
    for i in range(len(prev)):
        for j in range(len(road)):
            if road[j][0] == prev[i] and ans[road[j][1] - 1] == 0:
                ans[road[j][1] - 1] = prev[i]
                next.append(road[j][1])
            elif road[j][1] == prev[i] and ans[road[j][0] - 1] == 0:
                ans[road[j][0] - 1] = prev[i]
                next.append(road[j][0])
    prev = next
    
print('Yes')
for i in range(1, len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
rt = [[] for i in range(n)]
dk = [10**10] * n
srb = [None]*n

for i in range(m):
    a,b = mi()
    rt[a-1].append(b-1)
    rt[b-1].append(a-1)

d = dict()
dk[0] = 0
for i in rt[0]:
    d[i] = 1
    dk[i] = 1
    srb[i] = 1

while len(d) != 0:
# for j in range(20):
    # ルートが最小のnodeを見つける
    mincost = 10**6
    minnode, mincost = min(d.items(),key=lambda x: x[1])
    # for i in l:
    #     if mincost > dk[i]:
    #         mincost = dk[i]
    #         minnode = i
    # そのnodeの数字を確定し、
    del d[minnode]
        
    # 隣接する確定してないnodeにコストを上書き（小さければ）
    # queueに隣接nodeをappend
    for i in rt[minnode]:
        if dk[i] > dk[minnode]:
            dk[i] = dk[minnode]+1
            srb[i] = minnode+1
            d[i] = dk[minnode]+1

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

Submission status: Time Limit Exceeded

Solution code:
# https://qiita.com/kazukazukazukazu/items/e5db00a3aefb1f5ed72f
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

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

graph = Dijkstra()

for a, b in AB:
    graph.add(a, b, 1)

ans = []
for i in range(2, N+1):
    result = graph.getDijkstraShortestPath(i, 1)
    ans.append(result[1])
#     print(result[1])

if float('inf') in ans:
    print('No')
else:
    print('Yes')
    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*100000)
n, m = map(int,input().split())
mark = [-2] * (n-1)
dist = [0] * (n-1)
path = [[] for _ in range(n-1)]
path0 = []

def search(i):
    d = dist[i]
    p = []
    for p in path[i]:
        if dist[p] > d + 1 or dist[p] == 0:
            dist[p] = d + 1
            mark[p] = i
            search(p)

for _ in range(m):
    a, b = map(lambda x: int(x)-2, input().split())
    if a == -1:
        path0.append(b)
        dist[b] = 1
        mark[b] = -1
    elif b == -1:
        path0.append(a)
        dist[a] = 1
        mark[a] = -1
    else:
        path[a].append(b)
        path[b].append(a)

for p in path0:
    search(p)

if mark.count(-2) > 0:
    print("No")
else:
    print("Yes")
    for i in mark: print(i+2)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

ANS = [None]*(N+1)
Q = queue.Queue()
for i in L[1]:
    Q.put((i, 1))

Visited = [False]*(N+1)

while not Q.empty():
    n, p = Q.get()
    if Visited[n]:
        continue
    Visited[n] = True
    ANS[n] = p
    for i in L[n]:
        if i != p:
            Q.put((i, n))

    # print ("n: {}\tP: {}\tL:{}\tANS: {}".format(n, p, L, ANS))

    L[n] = set()
    for i in range(N+1):
        L[i].discard(n)

isYes = True
for a in ANS[2:]:
    if a == None:
        isYes = False
        break
if isYes:
    print ("Yes")
    for a in ANS[2:]:
        print (a)
else:
    print ("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import OrderedDict, defaultdict, deque
from enum import Enum
from typing import Dict, Optional


class State(Enum):
    UNVISITED = 0
    VISITED = 1


class Node(object):
    def __init__(self, key: int) -> None:
        self.adj_nodes: Dict[int, Node] = {}  # node key: node
        self.key: int = key
        self.state = State.UNVISITED

    def __repr__(self):
        return "<Node {}>".format(self.key)

    def add_adj_node(self, key) -> None:
        if key not in self.adj_nodes.keys():
            self.adj_nodes[key] = Node(key)


class Graph:
    def __init__(self) -> None:
        self.nodes: Dict[int, Node] = {}

    def add_node(self, key) -> None:
        if key not in self.nodes.keys():
            self.nodes[key] = Node(key)

    def add_edge(self, source: int, dest) -> None:
        if not self.get_node(source):
            self.add_node(source)
        if not self.get_node(dest):
            self.add_node(dest)

        self.get_node(source).add_adj_node(dest)

    def get_node(self, key) -> Optional[Node]:
        try:
            return self.nodes[key]
        except KeyError:
            return None


class DFS:
    def __init__(self, g: Graph, start_node_key: int):
        self.graph: Graph = g
        self.start_node_key: int = start_node_key
        # map node to prev_state
        # self.history = {}

    def solve(self):
        for start_node in self.graph.nodes.values():
            if start_node.state == State.UNVISITED:
                self._solve(node_key=start_node.key)

    def _solve(self, node_key: int):
        node = self.graph.get_node(node_key)
        node.state = State.VISITED
        self.visit_func(node_key)

        for adj_n_key in node.adj_nodes:
            adj_n = self.graph.get_node(adj_n_key)
            if adj_n.state == State.UNVISITED:
                self._solve(node_key=adj_n.key)

        self.finished(node_key)

    def visit_func(self, node_key: int):
        raise NotImplementedError

    def finished(self, node_key):
        raise NotImplementedError


class BFS:
    def __init__(self, g: Graph, start_key: int):
        self.graph = g
        self.start_key = start_key
        self.history: Dict[int, int] = {}

    def solve(self):
        n = self.graph.get_node(self.start_key)
        n.state = State.VISITED
        queue = deque()
        queue.append(n.key)
        while queue:
            n_key = queue.popleft()
            n = self.graph.get_node(n_key)

            for adj_node_key in n.adj_nodes:
                adj_node = self.graph.get_node(adj_node_key)
                if adj_node.state == State.UNVISITED:
                    self.history[adj_node_key] = n.key
                    adj_node.state = State.VISITED
                    self.visit_func(adj_node_key)
                    queue.append(adj_node_key)

    def visit_func(self, node_key):
        raise NotImplementedError


class Ans(BFS):
    def __init__(self, g, n, start_key=1):
        super().__init__(g, start_key)
        self.n = n
        self.dist = {x: -1 for x in range(1, n + 1)}
        self.dist[self.start_key] = 0

    def visit_func(self, node_key):
        if node_key != self.start_key:
            prev_dist = self.dist[self.history[node_key]]
            self.dist[node_key] = prev_dist + 1

    def show_results(self, n):
        if -1 in self.dist.values():
            print("No")
            return
        print("Yes")
        for i in range(2, n + 1):
            print(self.history[i])


if __name__ == "__main__":
    n, m = map(int, input().split(" "))
    G = Graph()
    for i in range(n):
        G.add_node(i + 1)

    for _ in range(m):
        a, b, = map(int, input().split(" "))
        # print(a, b)
        G.add_edge(a, b)
        G.add_edge(b, a)

    a = Ans(G, n)
    a.solve()
    # a.show_results()
    a.show_results(n)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline

N, M = map(int, readline().split())
ans = []
append_ans = ans.append
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)

root = 1
q = [root]
append_q = q.append
checked = [0] * (N + 1)
checked[root] = 1
order = []
append_order = order.append

while q:
    x = q.pop(0)
    for y in graph[x]:
        if checked[y]:
            continue
        append_ans(x)
        append_order(y-2)
        checked[y] = 1
        append_q(y)

if len(order) != N - 1:
    print('No')
else:
    print('Yes')
    for i in range(len(order)):
        j = order.index(i)
        print(ans[j])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
t = [[] for i in range(n)]
dis = [n for i in range(n)]
dis[0] = 0
near = [0 for i in range(n)]
c = []
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    dis[t[0][i]] = 1
    near[t[0][i]] = 0
    c.append(t[0][i])
while len(c) > 0:
    d = len(c)
    for i in range(d):
        e = c[0]
        for j in range(len(t[e])):
            if dis[t[e][j]] >= dis[e] +1:
                 dis[t[e][j]] = dis[e] +1
                 near[t[e][j]] = e
                 c.append(t[e][j])
        del c[0]
if max(dis) == n:
    print('No')
else:
    print('Yes')
    for i in range(1,len(near)):
        print(near[i]+1)

Submission status: Time Limit Exceeded

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

import networkx as nx

YES = "Yes"  # type: str
NO = "No"


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()
    G.add_nodes_from([1+n for n in range(N)])

    G.add_edges_from([(a,b) for a,b in zip(A,B)])

    paths = nx.single_source_shortest_path(G, 1)

    ans_list = []
    for key, val in sorted(paths.items()):
        if key != 1:
            ans_list.append((key,val[-2]))

    print(YES)
    ans_list.sort(key=lambda x: x[0])
    for key, val in ans_list:
        print(val)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
tmp = list(map(int, input().split()))
N, M = tmp[0], tmp[1]
A = []
B = []
for i in [0]*M:
    tmp = list(map(int, input().split()))
    A.append(tmp[0])
    B.append(tmp[1])

arranged = [[1]]
nextroom = []
ans = [0]*(N-1)
for j in [0]*M:
    flattenarr = sum(arranged, [])
    for i in range(M):
        for rooms in arranged:
            if A[i] in rooms and B[i] not in flattenarr:
                nextroom.append(B[i])
                if ans[B[i]-2] == 0:
                    ans[B[i]-2]=A[i]
                break

            if B[i] in rooms and A[i] not in flattenarr:
                nextroom.append(A[i])
                if ans[A[i]-2] == 0:
                    ans[A[i]-2]=B[i]
                break
    arranged.append(nextroom)
    nextroom = []

if 0 in ans:
    print('No')
else:
    print('Yes')
    for x in ans:
        print(x)