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
input = sys.stdin.readline
N, M = map(int, input().split())
g = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in g.keys():
    g[a].append(b)
  else:
    g[a] = [b]
  if b in g.keys():
    g[b].append(a)
  else:
    g[b] = [a]
ans = [0 for _ in range(N+1)]
#print(g)
current = [1]
while 0 in ans[2:]:
  #print(ans)
  next = []
  for i in current:
    #print('i',i)
    for j in g[i]:
      if ans[j] == 0:
        ans[j] = i
        next.append(j)
  current = next
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    n, m = map(int, input().split())

    nexts = [[] for i in range(n)]
    
    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        nexts[ai].append(bi)
        nexts[bi].append(ai)

    depth = [[0]]
    l = [0]
    new_l = []
    uncheck = [x + 1 for x in range(n - 1)]
    arrows = [0 for i in range(n)]

    while len(uncheck) > 0:
        for x in l:
            for nxt in nexts[x]:
                if (nxt in uncheck) and (nxt not in new_l):
                    new_l.append(nxt)
                    uncheck.remove(nxt)
        
        depth.append(new_l)
        l = new_l
        new_l = []

    for i, d in enumerate(depth):
        for room in d:
            for nxt in nexts[room]:
                if nxt in depth[i - 1]:
                    arrows[room] = nxt
                    break

    print("Yes")
    for arrow in arrows[1:]:
        print(arrow + 1)

Submission status: Time Limit Exceeded

Solution code:
import queue
n, m = map(int, input().split())
g = [[0] * n for i in range(n)]

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

root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in range(n):
        if root[i] <= 0 and g[p][i] > 0:
            q.put(i)
            root[i] = p + 1
            count += 1
            #print(p,i,count,root)
            if count >= n:
                break

if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
import math
import sys

def bfs(queue, visited):
    while len(queue) > 0:
        dest = queue.popleft()
        for i in G[dest]:
            if visited[i] == -1:
                visited[i] = visited[dest] + 1
                queue.append(i)
    return visited
# k = int(input())
# s =input()
# a = list(map(int, input().split()))
n,m= map(int, input().split())
G = defaultdict(set) 
for i in range(m):
    x,y= map(int,input().split())
    G[x].add(y)
    G[y].add(x)

print("Yes")
visited = [-1]*(n+1)
visited[1] = 0
q = deque([1])
visited = bfs(q,visited)

deep = {}
for i,j in enumerate(visited[2:]):
    if j not in deep:
        deep[j]={i+2}
    else:
        deep[j].add(i+2)

for i in range(2,n+1):
    d = visited[i]
    if d == 1:
        print(1)
    else:
        for j in deep[d-1]:
            if j in G[i]:
                print(j)
                break

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = {}
def trace():
    tasks = [(1, 0)]
    while tasks:
        no, lv = tasks.pop()
        for c in d[no]:
            if c != 1:
                if c not in r or (r[c][1] > lv and r[c][1] != 0):
                    r[c] = (no, lv)
                    tasks.append((c, lv + 1))
trace()

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
g = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in g.keys():
    g[a].append(b)
  else:
    g[a] = [b]
  if b in g.keys():
    g[b].append(a)
  else:
    g[b] = [a]
ans = [0 for _ in range(N+1)]
#print(g)
current = [1]
while 0 in ans[2:]:
  #print(ans)
  next = []
  for i in current:
    #print('i',i)
    for j in g[i]:
      if ans[j] == 0:
        ans[j] = i
        next.append(j)
  current = next
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[0] * (n+1) for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a][b] = 1
    ggg[b][a] = 1
    
  qq = deque()
  qq.append((1, 1))
  
  while qq:
    a, f = qq.popleft()
    if ff[a]:
      continue
    ff[a] = f
    for b in range(1, n+1):
      if ggg[a][b] and not ff[b]:
        qq.append((b, a))
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
d = deque()
As = [0] * m
Bs = [0] * m
Cs = [0] * max((m + 1), (n + 1))  # 標

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


def solver(i):
    aindexs = [j for j, x in enumerate(As) if x == i]
    bindexs = [j for j, x in enumerate(Bs) if x == i]
    indexs = aindexs + bindexs
    for aindex in aindexs:
        target = Bs[aindex]
        d.append(target)
        if Cs[target] == 0:
            Cs[target] = i
    for bindex in bindexs:
        target = As[bindex]
        d.append(target)
        if Cs[target] == 0:
            Cs[target] = i
    for index in indexs:
        As[index] = -1
        Bs[index] = -1


d.append(1)

while d:
    solver(d.popleft())

for i in range(2, n + 1):
    if (Cs[i] == 0):
        print('No')
        exit()
print('Yes')
for i in range(2, n + 1):
    print(Cs[i])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
PATHS = list([tuple(map(lambda t: int(t) - 1, input().split())) for i in range(M)])

depths = [None] * N
guides = [None] * N

def func(cuurent, paths, depth):
    depths[cuurent] = depth

    ls = []
    ls_ex = []

    for r1, r2 in paths:
        if r1 == cuurent and (depths[r2] == None or depths[r2] > depth + 1):
            depths[r2] = depth + 1
            guides[r2] = cuurent
            ls.append(r2)
        
        elif r2 == cuurent and (depths[r1] == None or depths[r1] > depth + 1):
            depths[r1] = depth + 1
            guides[r1] = cuurent
            ls.append(r1)
        
        else:
            ls_ex.append((r1, r2))
    
    for room in ls:
        func(room, ls_ex, depth + 1)

func(0, PATHS, 0)

#if not all([follow_guide(i, guides) == depths[i] for i in range(1, N)]):
if False:
    print("No")

else:
    print("Yes")

    for i in guides[1:]:#
        print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
g = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in g.keys():
    g[a].append(b)
  else:
    g[a] = [b]
  if b in g.keys():
    g[b].append(a)
  else:
    g[b] = [a]
ans = [0 for _ in range(N+1)]
#print(g)
current = [1]
while 0 in ans[2:]:
  #print(ans)
  for i in current:
    next = []
    #print('i',i)
    for j in g[i]:
      if ans[j] == 0:
        ans[j] = i
        next.append(j)
  current = next
print('Yes')
for i in range(2,N+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
ans = [-1 for i in range(n+1)]
def bfs():
    #start at 1
    que = deque([1])
    finished = set()
    while que:
        node = que.popleft()
        finished.add(node)
        for i in adjacent_list[node]:
            if i not in finished:
                que.append(i)
                if ans[i] == -1:
                    ans[i] = node
bfs()
print("Yes")
for i in range(2,n+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import queue

def dijkstra(g,node_count):
    
    root = [-1] * node_count

    q = queue.Queue()
    q.put(0)
    root[0] = 0
    conf[0] = 1
    while not q.empty():

        p = q.get()
        conf[p] = 1
        for i in range(node_count):
            if conf[i] == 0 and g[p][i] > 0 and i != p:
                q.put(i)
                root[i] = p
                conf[i] = 1
                if sum(conf) == node_count:
                    break

    return root


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

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

root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in range(n):
        if root[i] <= 0 and g[p][i] > 0:
            q.put(i)
            root[i] = p + 1
            count += 1
            #print(p,i,count,root)
            if count >= n:
                break

if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])

Submission status: Time Limit Exceeded

Solution code:
import queue
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)]
q = queue.Queue()
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
    q.put(t[0][i])
while not q.empty():
    e = q.get()
    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
            q.put(t[e][j])
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import deque

    n, m = map(int, input().split())
    d = {}
    par = [[] for i in range(n)]
    que = deque()
    for i in range(m):
        a, b = map(int, input().split())
        par[a - 1].append(b)
        par[b - 1].append(a)

    que.append(1)
    while(len(que) > 0):
        label = que.popleft()
        for i, p in enumerate(par):
            if label in p and i + 1 not in d.keys():
                que.append(i + 1)
                d[i + 1] = label

    if len(d) < n:
        print("No")
        return

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
d = deque()
As = [0] * m
Bs = [0] * m
Cs = [0] * max((m + 1), (n + 1))  # 標

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


def solver(i):
    aindexs = [j for j, x in enumerate(As) if x == i]
    bindexs = [j for j, x in enumerate(Bs) if x == i]
    indexs = aindexs + bindexs
    for aindex in aindexs:
        target = Bs[aindex]
        d.append(target)
        if Cs[target] == 0:
            Cs[target] = i
    for bindex in bindexs:
        target = As[bindex]
        d.append(target)
        if Cs[target] == 0:
            Cs[target] = i
    for index in indexs:
        As[index] = -1
        Bs[index] = -1


d.append(1)

while d:
    solver(d.popleft())

for i in range(2, n + 1):
    if (Cs[i] == 10**5 + 1):
        print('No')
        exit()
print('Yes')
for i in range(2, n + 1):
    print(Cs[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def resolve():
  N, M = map(int, input().split(" "))
  rooms = [None] * N

  def search_and_mark(recent_rooms, AB, depth):
    if None not in rooms:
      return rooms

    tmp_rooms = []
    for r in recent_rooms:
      tmp = AB[np.any(AB == r, axis=1)]
      target = tmp[tmp != r]
      tmp_rooms.extend(target)
      AB = AB[np.any(AB != r, axis=1)]
      
      for t in target:
        if rooms[t] == None:
          rooms[t] = r

    recent_rooms = list(set(tmp_rooms))
    return search_and_mark(recent_rooms, AB, depth+1)

  AB = []
  for m in range(M):
    AB.append([int(x) - 1 for x in input().split(" ")])

  AB = np.array(AB)
  result = search_and_mark([0], AB, 0)

  print("Yes")
  for r in result[1:]:
    print(r + 1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

root = [0]*n
for i in range(m):
    r = list(map(int, input().split()))
    if root[r[0]-1] == 0:
        root[r[0]-1] = [r]
    else:
        root[r[0]-1] = root[r[0]-1]+[r]
    if root[r[1]-1] == 0:
        root[r[1]-1] = [r]
    else:
        root[r[1]-1] = root[r[1]-1]+[r]

kakutei = [1]

answer_li = [0]*n

def dest(r,k):
    if r[0] == k:
        return r[1]
    else:
        return r[0] 

while kakutei:
    k = kakutei.pop(0)
    for r in root[k-1]:
        d = dest(r,k)
        if answer_li[d-1] == 0:
            kakutei.append(d)
            answer_li[d-1] = k

answer_li = answer_li[1:]
if 0 in answer_li:
    print('No')
else:
    print('Yes')
    for i in answer_li:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[0] * (n+1) for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a][b] = 1
    ggg[b][a] = 1
    
  qq = deque()
  qq.append((1, 1))
  
  while qq:
    a, f = qq.popleft()
    if ff[a]:
      continue
    ff[a] = f
    for b in range(1, n+1):
      if ggg[a][b]:
        qq.append((b, a))
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)
 
  
  
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
ans = [-1 for i in range(n+1)]
def bfs():
    #start at 1
    que = deque([1])
    finished = set()
    while que:
        node = que.popleft()
        finished.add(node)
        for i in adjacent_list[node]:
            if i not in finished:
                que.append(i)
                if ans[i] == -1:
                    ans[i] = node
bfs()
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())

cost = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(m):
    ai,bi=map(int, input().split())
    cost[ai-1][bi-1] = 1
    cost[bi-1][ai-1] = 1
    

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
        
q=dijkstra(0,n,m,cost)
r=[0]*n
for i in range(1,len(q)):
    qmin=10**10
    for j in range(n):
        if cost[i][j]==1:
            if qmin>q[j]:
                qmin=q[j]
                r[i]=j

if max(q)==float("inf"):
    print("No")
else:
    print("Yes")
    for i in range(1,len(q)):
        print(r[i]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
import math
import sys
sys.setrecursionlimit(10**7)
def bfs(queue, visited):
    while len(queue) > 0:
        dest = queue.popleft()
        for i in G[dest]:
            if visited[i] == -1:
                visited[i] = visited[dest] + 1
                queue.append(i)
    return visited
# k = int(input())
# s =input()
# a = list(map(int, input().split()))
n,m= map(int, input().split())
G = defaultdict(set) 
for i in range(m):
    x,y= map(int,input().split())
    G[x].add(y)
    G[y].add(x)

print("Yes")
visited = [-1]*(n+1)
visited[1] = 0
q = deque([1])
visited = bfs(q,visited)

deep = defaultdict(set)
for i,j in enumerate(visited[2:]):
    deep[j].add(i+2)

for i in range(2,n+1):
    d = visited[i]
    if d == 1:
        print(1)
    else:
        for j in deep[d-1]:
            if j in G[i]:
                print(j)
                break

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
cage = {}
for i in range (2,n+1):
    cage[i] = None
ab = [map(int, line.rstrip("\n").split()) for line in sys.stdin]
a,b = [list(i) for i in zip(*ab)]
room = [1]
nroom = []
while None in cage.values():
    for i in range(len(room)):
        j = 0
        while j < (len(a)):
            if a[j] == room[i]:
                if cage[b[j]] == None:
                    cage[b[j]] = a[j]
                nroom.append(b[j])
                a.pop(j)
                b.pop(j)
            elif b[j] == room[i]:
                if cage[a[j]] == None:
                    cage[a[j]] = b[j]
                nroom.append(a[j])
                a.pop(j)
                b.pop(j)
            else:
                j += 1
    if (len(a) == 0 and None in cage.values()) or room == nroom:
        print('No')
        break
    room = nroom[:]
    nroom.clear()
else:
    print('Yes')
    for i in range (2,n+1):
        print(cage[i])

Submission status: Time Limit Exceeded

Solution code:
room, path = map(int, input().split())

connect = []  # 通路がつなぐ部屋の組のリスト
for i in range(path):
  r1, r2 = map(int, input().split())
  connect.append([r1, r2])
                 
def next(list_name):  # 次の階層の部屋を探す
  len_li = len(list_name)  # 階層は何段目か
  new_stage = []  # 新しい階層に加える部屋番号
  for i in list_name[len_li - 1]:  # 最深の階層の部屋を取り出す
    for j, k in connect:  # 部屋のつながりを一つずる見る
      if i == j and k not in list_name[len_li - 2] and k not in list_name[len_li - 1]:
        new_stage.append(k)
      elif i == k and j not in list_name[len_li - 2] and j not in list_name[len_li - 1]:
        new_stage.append(j)
      else:
        pass
  if len(new_stage) != 0:
    way.append(new_stage)

a = 0
way = [[1]]  # 部屋のつながり
while a < 1000:
  a += 1
  way_len_i = len(way)
  next(way)
  way_len_l = len(way)
  if way_len_i == way_len_l:
    break
    
def search(room_num):
  stage = 0  # 最初に見つかる階層[0, 1, 2, 3, ...]
  for i in range(len(way)):
    if room_num in way[i]:
      stage = i
      
  clue = []
  for i in connect:  # この部屋とつながる部屋を探す
    if i[0] == room_num:
      clue.append(i[1])
    elif i[1] == room_num:
      clue.append(i[0])
    else:
      pass
  if len(clue) == 0:
    print("つながる部屋がありません")
    
  for j in way[stage - 1]:  # １つ浅い階層の部屋を取り出す
    for k in clue:
      if j == k:
        return j

result = []
for i in range(2, room + 1):  # 目印を探す
  result.append(search(i))

if len(result) == 0:
  print("No")
else:
  print("Yes")
  for i in result:
    print(i)

Submission status: Time Limit Exceeded

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

root = [0]*n
for i in range(m):
    r = list(map(int, input().split()))
    if root[r[0]-1] == 0:
        root[r[0]-1] = [r]
    else:
        root[r[0]-1] = root[r[0]-1]+[r]
    if root[r[1]-1] == 0:
        root[r[1]-1] = [r]
    else:
        root[r[1]-1] = root[r[1]-1]+[r]

kakutei = [1]

answer_li = [0]*n

mitou = [-1]*n

def dest(r,k):
    if r[0] == k:
        return r[1]
    else:
        return r[0] 

while len(kakutei)>=1:
    k = kakutei[0]
    for r in root[k-1]:
        d = dest(r,k)
        if mitou[d-1] == -1:
            mitou[d-1] = 0
            root[d-1].remove(r)
            kakutei.append(d)
            answer_li[d-1] = k

    kakutei = kakutei[1:]

answer_li = answer_li[1:]
if 0 in answer_li:
    print('No')
else:
    print('Yes')
    for i in answer_li:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    n, m = map(int, input().split())

    nexts = [[]] * n
    
    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        if len(nexts[ai]) == 0:
            nexts[ai] = [bi]
        else:
            nexts[ai].append(bi)
        if len(nexts[bi]) == 0:
            nexts[bi] = [ai]
        else:
            nexts[bi].append(ai)

    depth = [[0]]
    l = [0]
    new_l = []
    uncheck = [x + 1 for x in range(n - 1)]
    arrows = [0] * n

    while len(uncheck) != 0:
        for x in l:
            for nxt in nexts[x]:
                if (nxt in uncheck) and (nxt not in new_l):
                    new_l.append(nxt)
        
        depth.append(new_l)
        l = new_l
        new_l = []
    
    for i, d in enumerate(depth):
        for room in d:
            for nxt in nexts[room]:
                if nxt in depth[i - 1]:
                    arrows[room] = nxt
                    break

    print("Yes")
    for arrow in arrows[1:]:
        print(arrow + 1)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def dijkstra(s, n, cost, inf=float("inf")):
        d = [inf] * n
        used = [False] * n
        d[s] = 0
        p = [-9999] * n
        while True:
            v = -1
            for i in range(n):
                if not used[i]:
                    if v == -1:
                        v = i
                    elif d[i] < d[v]:
                        v = i
            if v == -1:
                break
            used[v] = True
            for j in range(n):
                k = d[v] + cost[v][j]
                if k < d[j]:
                    d[j] = k
                    p[j] = v
        return d, p
    n, m = map(int, input().split())
    inf = 10 ** 10
    cost = [[inf for i in range(n)] for i in range(n)]
    for _ in range(m):
        x, y = [int(x) - 1 for x in input().split()]
        cost[x][y] = 1
        cost[y][x] = 1
    l, p = dijkstra(0, n, cost, inf)
    if min(p[1:]) < -1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p = []
d1 = {}
d2 = {}
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        d1[b] = 1
        d2[b] = 1
    elif b == 1:
        d1[a] = 1
        d2[a] = 1
    else:
        p.append((a, b))
while p:
    pi = p.pop(0)
    if pi[0] in d1 and pi[1] not in d1:
        d1[pi[1]] = pi[0]
        d2[pi[1]] = d2[pi[0]] + 1
    elif pi[1] in d1 and pi[0] not in d1:
        d1[pi[0]] = pi[1]
        d2[pi[0]] = d2[pi[1]] + 1
    elif pi[0] in d1 and pi[1] in d1:
        if d2[pi[0]] > d2[pi[1]] + 1:
            d1[pi[0]] = pi[1]
            d2[pi[0]] = d2[pi[1]] + 1
        elif d2[pi[1]] > d2[pi[0]] + 1:
            d1[pi[1]] = pi[0]
            d2[pi[1]] = d2[pi[0]] + 1
    else:
        p.append(pi)
print("Yes")
for i in range(2, n + 1):
    print(d1[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

n, m = list(map(int, input().split()))
a = np.zeros((m,), dtype=np.int)
b = np.zeros((m,), dtype=np.int)
for i in range(m):
    a[i], b[i] = list(map(int, input().split()))
a -= 1
b -= 1

is_visited = np.zeros((n,), dtype=np.bool)
parent = np.zeros((n,), dtype=np.int)

q = deque()
q.append(0)
is_visited[0] = True
while len(q) != 0:
    node = q.popleft()
    for i in np.where(a == node)[0]:
        child = b[i]
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)
    for i in np.where(b == node)[0]:
        child = a[i]
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)

parent += 1

print('Yes')
for node in parent[1:]:
    print(node)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def resolve():
  N, M = map(int, input().split(" "))
  rooms = [None] * N

  def search_and_mark(recent_rooms, AB, depth):
    if None not in rooms:
      return rooms

    tmp_rooms = []
    for r in recent_rooms:
      tmp = AB[np.any(AB == r, axis=1)]
      target = tmp[tmp != r]
      tmp_rooms.extend(target)
      
      for t in target:
        if rooms[t] == None:
          rooms[t] = r

    recent_rooms = list(set(tmp_rooms))
    return search_and_mark(recent_rooms, AB, depth+1)

  AB = []
  for m in range(M):
    AB.append([int(x) - 1 for x in input().split(" ")])

  AB = np.array(AB)
  result = search_and_mark([0], AB, 0)

  print("Yes")
  for r in result[1:]:
    print(r + 1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
N, M= [int(i) for i in input().split(' ')]
graph = {}
 
for i in range(1,N+1):
  graph[i] = []
 
for j in range(M):
  a, b= [int(i) for i in input().split(' ')]
  graph[a].append(b)
  graph[b].append(a)
    
 
def bfs(graph, start):
  queue = [start]
  visited1 = []
  visited = {}
  for i in range(1,N+1):
    visited[i] = 0  
  miti = {}
  for i in range(1,N+1):
    miti[i] = 0
  where_from = [start-1]
  while queue:
    label = queue.pop(0)
    label2 = where_from.pop(0)
    if visited[label]==0:
      visited1.append(label)
      visited[label]=1
      if miti[label] != 0:
        return False
      miti[label] = label2
      queue += graph.get(label, [])
      where_from += [label]*len(graph.get(label, []))
    if len(visited1) == N:
      break
  if len(visited1) != N:
    return False
  return miti
 
miti = bfs(graph, 1)
if miti:
  print('Yes')
  for i in range(2,N+1):
    print(miti[i])
else:
  print('No')

Submission status: Time Limit Exceeded

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

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

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

ikeru = [set() for _ in range(n+1)]

for i,j in tsuro:
    ikeru[i].add(j)
    ikeru[j].add(i)

ans = [0]*(n+1)
visited = [n+5]*(n+1)

def dfs(mae,heya,kaiso):
    if visited[heya] <= kaiso:
        return True
    else:
        visited[heya] = kaiso
        ans[heya] = mae
        for j in ikeru[heya]:
            dfs(heya, j, kaiso+1)
        return True

hantei = True
dfs(0,1,0)
for i in range(1, n+1):
    if visited[i] == n+5:
        hantei = False
        break
if hantei:
    print('Yes')
    for k in range(2,n+1):
        print(ans[k])
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
for i in range(m):
    A[i], B[i] = map(int, input().split())

next_queue = deque()
delete_items = deque()
sign = [-1] * n

next_queue.append(1)

while next_queue:
    current_number = next_queue.popleft()
    for i, _ in enumerate(A):
        if A[i] == current_number:
            if sign[B[i] - 1] == -1:
                sign[B[i] - 1] = current_number
                if B[i] != 1:
                    next_queue.append(B[i])
                delete_items.append(i)
        if B[i] == current_number:
            if sign[A[i] - 1] == -1:
                sign[A[i] - 1] = current_number
                if A[i] != 1:
                    next_queue.append(A[i])
                delete_items.append(i)
    for i in sorted(list(delete_items), reverse=True):
        A.pop(i)
        B.pop(i)
    delete_items.clear()
print("Yes")
for i in range(1, n):
    print(sign[i])

Submission status: Time Limit Exceeded

Solution code:
N, M= [int(i) for i in input().split(' ')]
graph = {}
 
for i in range(1,N+1):
  graph[i] = []
 
for j in range(M):
  a, b= [int(i) for i in input().split(' ')]
  graph[a].append(b)
  graph[b].append(a)
    
 
def bfs(graph, start):
  queue = [start]
  miti = [-1 for _ in range(N)]

  while queue:
    label = queue.pop(0)
    for i in graph[label]:
      if miti[i-1] < 0:
        queue.append(i)
        miti[i-1] = label
  return miti
 
miti = bfs(graph, 1)
if miti:
  print('Yes')
  for i in range(2,N+1):
    print(miti[i-1])
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

n, m = map(int, input().split())
ab = np.zeros([m, 2], dtype=int)
for i in range(m):
    a, b = map(int, input().split())
    ab[i] = [a,b]

nodes = [None]*n

for i in range(n):
    t = []
    for j1 in np.where(ab[:,0]==i+1)[0]:
        t.append(ab[j1,1]-1)
    for j2 in np.where(ab[:,1]==i+1)[0]:
        t.append(ab[j2,0]-1)
    nodes[i] = t

mins = np.zeros([n], dtype=int)
used = np.zeros_like(mins)
used[0] = 1
q = deque()
q.append(0)
step = 0
while not len(q)==0:
    v = q.popleft()
    for i in nodes[v]:
        if not used[i]:
            used[i] = 1
            mins[i] = v
            q.append(i)

if all(used):
    print('Yes')
    for i in range(1,n):
        print(mins[i]+1)
else:
    print('No')