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:
from collections import deque
n,m=map(int,input().split())
d=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
l=[-1 for i in range(n)]
q=deque([0])
#print(d)
while len(q)>0:
    x=q.popleft()
    for i in d[x]:
        #print(i)
        if i!=0 and l[i]==-1 and x not in q:
            q.append(i)
            #print(i)
            l[i]=str(x+1)
l=l[1:]
#print(l)
print('No' if 0 in l else 'Yes\n'+'\n'.join(l))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split()) # ノード数, エッジ数
edges = [[] for i in range(N)] # エッジ
for i in range(M):
    A, B = map(int, input().split())
    edges[A - 1] += [B - 1]
    edges[B - 1] += [A - 1]

# 幅優先探索
que = deque([0]) # 探索用キュー
ans = [0] + [-1 for i in range(N - 1)] # 未探索ノード 兼 道しるべ
while -1 in ans: # 未探索ノードがある間
    node = que.popleft() # キューから取り出し
    for neighbor in edges[node]: # 全ての隣接ノードに対して
        if ans[neighbor] == -1: # 未探索なら
            ans[neighbor] = node + 1 # 道しるべを設定
            que.append(neighbor) # キューに入れる

print('Yes')
for a in ans[1:]:
    print(a)

Submission status: Time Limit Exceeded

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

root = [[pow(10,9)]*n for _ in range(n)]

from collections import deque

root=[0]*n
r=[[]for i in range(n)]

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

dist =[-1]*n
dist[0] = 0

q = deque([0])
prev=[-1] * n

while q:
    v = q.popleft()

    for j in r[v]:
        if dist[j]!=-1:
            continue
        else:
            dist[j] = dist[v] + 1
            prev[j] = v
            q.append(j)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
d={i:[] for i in range(1,n+1)}
for i in range(m):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
l=[0 for i in range(n+1)]
q=deque([1])
#print(d)
while len(q)>0:
    x=q.popleft()
    for i in d[x]:
        #print(i)
        if i!=1 and l[i]==0 and x not in q:
            q.append(i)
            #print(i)
            l[i]=str(x)
l=l[2:]
#print(l)
print('No' if 0 in l else 'Yes\n'+'\n'.join(l))

Submission status: Time Limit Exceeded

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

root = [[pow(10,9)]*n for _ in range(n)]

from collections import deque

root=[0]*n
r=[[]for i in range(n)]

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

dist =[-1]*n
dist[0] = 0

q = deque([0])
prev=[-1] * n

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

    for j in r[v]:
        if dist[j]!=-1:
            continue
        else:
            dist[j] = dist[v] + 1
            prev[j] = v
            q.append(j)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        edges[b].append(a)

    visited = [False] * N
    rooms = [-1] * N
    def bfs(u):
        q = deque()
        q.append((u, -1))
        while 0 < len(q):
            (v, p) = q.popleft()
            visited[v] = True
            if rooms[v] == -1 and p != -1:
                rooms[v] = p
            for e in edges[v]:
                if visited[e]:
                    continue
                q.append((e, v))

    bfs(0)
    print("Yes")
    for x in rooms[1:]:
        print(x + 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

root = [[pow(10,9)]*n for _ in range(n)]

from collections import deque

root=[0]*n

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

    if root[b]==0:
        root[b]=[a]
    else:
        root[b].append(a)
dist =[-1]*n
dist[0] = 0

q = deque([0])
prev=[-1] * n

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

    for j in root[v]:
        if dist[j]!=-1:
            continue
        else:
            dist[j] = dist[v] + 1
            prev[j] = v
            q.append(j)


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

Submission status: Time Limit Exceeded

Solution code:
import queue

def bfs(s):
    q = queue.Queue()
    q.put(s)
    d = [-1] * n
    d[s] = 0
    while not q.empty():
        u = q.get()
        for v in range(n):
            if M[u][v] == 0:
                continue
            if d[v] != -1:
                continue
            d[v] = u + 1
            q.put(v)
    print('Yes')
    for i in range(1, n):
        if d[i] == -1:
            print(-1)
        else:
            print(d[i])

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

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

bfs(0)

Submission status: Time Limit Exceeded

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

root = [[pow(10,9)]*n for _ in range(n)]

from collections import deque

root=[0]*n

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

    if root[b]==0:
        root[b]=[a]
    else:
        root[b].append(a)
dist =[-1]*n
dist[0] = 0

q = deque([0])
prev=[-1] * n

while len(q)!=0:
    v = q[0]
    q.popleft()

    for j in root[v]:
        if dist[j]!=-1:
            continue
        else:
            dist[j] = dist[v] + 1
            prev[j] = v
            q.append(j)


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

Submission status: Time Limit Exceeded

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

visited = [False] * N
rooms = [-1] * N
def bfs(u):
    q = deque()
    q.append((u, -1))
    while 0 < len(q):
        (v, p) = q.popleft()
        visited[v] = True
        if p != -1 and rooms[v] == -1:
            rooms[v] = p
        for e in edges[v]:
            if visited[e]:
                continue
            q.append((e, v))

bfs(0)
print("Yes")
for x in rooms[1:]:
    print(x + 1)

Submission status: Time Limit Exceeded

Solution code:
import queue
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

visited = [False] * N
rooms = [-1] * N
def bfs(u):
    q = queue.Queue()
    q.put((u, -1))
    while not q.empty():
        (v, p) = q.get()
        visited[v] = True
        if p != -1 and rooms[v] == -1:
            rooms[v] = p
        for e in edges[v]:
            if visited[e]:
                continue
            q.put((e, v))

bfs(0)
print("Yes")
for x in rooms[1:]:
    print(x + 1)

Submission status: Time Limit Exceeded

Solution code:
import queue
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

visited = [False] * N
dist = [float('inf')] * N
rooms = [-1] * N
def bfs(u):
    q = queue.Queue()
    q.put((u, 0, -1))
    while not q.empty():
        (v, d, p) = q.get()
        visited[v] = True
        if dist[v] > d:
            dist[v] = d
            if p != -1:
                rooms[v] = p
        for e in edges[v]:
            if visited[e]:
                continue
            q.put((e, d + 1, v))

dist[0] = 0
bfs(0)
print("Yes")
for x in rooms[1:]:
    print(x + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    elif not b in d[a]:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    elif not a in d[b]:
        d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    s  = "\n".join(map(str, ans[1:]))
    print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split()) # ノード数, エッジ数
edges = [set(map(int, input().split())) for i in range(M)] # エッジ
que = deque([1]) # 探索用キュー
ans = [0] + [-1 for i in range(N - 1)] # 未探索ノード 兼 道しるべ

while -1 in ans: # 未探索ノードがある間
    node = que.popleft() # キューから取り出し
    for edge in edges: # 全てのエッジに対して
        if node in edge: # 現在のノードを含むなら
            neighbor = (edge - {node}).pop() # 隣接ノードを確認
            if ans[neighbor - 1] == -1: # 隣接ノードが未探索なら
                ans[neighbor - 1] = node # 道しるべを設定
                que.append(neighbor) # キューに入れる

print('Yes')
for a in ans[1:]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().strip().split()]
graph = [[] for i in range(n + 1)]

for _ in range(m):
    i, j = [int(i) for i in input().strip().split()]
    graph[i].append(j)
    graph[j].append(i)
his = [1] 
queue = [[i, 1] for i in graph[1]]
path_to = [0 for i in range(n + 1)]
while len(queue):
    node, prev = queue.pop(0)
    if node not in his:
        his.append(node)
        queue.extend([[i, node] for i in graph[node]])
        path_to[node] = prev

if len(his) == n:
    print("Yes")
    for i in path_to[2:]:
        print(i)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    elif not b in d[a]:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    elif not a in d[b]:
        d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,raw_input().split())
d={}
for i in xrange(m):
	x,y=map(int,raw_input().split())
	if x in d:
		d[x].append(y)
	else:
		d[x]=[y]
	if y in d:
		d[y].append(x)
	else:
		d[y]=[x]

parent=[0]*(n+1)
bfs=[1]
visited=set([1])
while len(bfs)!=0:
	x=bfs.pop(0)
	visited.add(x)
	for i in d[x]:
		if i not in visited:
			bfs.append(i)
			parent[i]=x
			visited.add(i)


if len(visited)==n:
	print('Yes')
	for i in xrange(2,n+1):
		print(parent[i])
else:
	print('No')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    elif not b in d[a]:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    elif not a in d[b]:
        d[b].append(a)

q = [1]
while not len(q) == 0:
    x = q.pop(0)
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)
if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    elif not b in d[a]:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    elif not a in d[b]:
        d[b].append(a)

q = [1]
while not len(q) == 0:
    x = q.pop(0)
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        q.append(i)
if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os

def file_input():
    f = open('ABC168/input.txt', 'r')
    sys.stdin = f

def main():
    if os.getenv("ENV")=='LOCAL':
        file_input()

    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())
        # print("A:"+str(A[i])+" B:"+str(B[i])+" tmp:"+str(tmp))
        # print(tmp[A[i]-1])

    al=[False]*N    #すでに探索したか
    al[0]=True
    out=[0]*N   #何番目に通るか
    li=[]
    li.append([1])     #深さ毎の数値
    for de in range(N): #深さで探索
        tmp=[]
        # print(de)
        for l in li[de]:
            for i in range(M):  #A,Bの探索
                if A[i]==l and not al[B[i]-1]: #A[i]が一個前とつながってたら
                    tmp.append(B[i])
                    out[B[i]-1]=l
                    al[B[i]-1]=True
                    # print("A="+str(B[i])+" l="+str(l)+" out"+str([B[i]-1])+"="+str(out[B[i]-1]))
                if B[i]==l and not al[A[i]-1]:
                    tmp.append(A[i])
                    out[A[i]-1]=l
                    al[A[i]-1]=True
                    # print("B="+str(A[i])+" l="+str(l)+" out"+str([A[i]-1])+"="+str(out[A[i]-1]))
        li.append(tmp)
        # print(al)


    print('Yes')
    [print(x) for x in out[1:]]

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
d={}
for i in range(m):
	x,y=map(int,input().split())
	if x in d:
		d[x].append(y)
	else:
		d[x]=[y]
	if y in d:
		d[y].append(x)
	else:
		d[y]=[x]

parent=[0]*(n+1)
bfs=[1]
visited=set([1])
while len(bfs)!=0:
	x=bfs.pop(0)
	visited.add(x)
	for i in d[x]:
		if i not in visited:
			bfs.append(i)
			parent[i]=x
			visited.add(i)


if len(visited)==n:
	print('Yes')
	for i in range(2,n+1):
		print(parent[i])
else:
	print('No')

Submission status: Time Limit Exceeded

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

root = [[pow(10,9)]*n for _ in range(n)]

from collections import deque

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

    root[a][b]=1
    root[b][a]=1

dist =[pow(10,9)]*n
dist[0] = 0

q = deque([0])
prev=[-1] * n

while len(q)!=0:
    v = q[0]
    q.popleft()

    for j in range(n):
        if dist[j] > dist[v] + 1 and root[v][j]!=pow(10,9):
            dist[j] = dist[v] + 1
            prev[j] = v
            q.append(j)


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


# print(dist)
# print(prev)



# print(*root,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    elif not b in d[a]:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    elif not a in d[b]:
        d[b].append(a)

q = [1]
alr = [1]
while not len(q) == 0:
    x = q.pop(0)
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        if i in alr:
            continue
        alr.append(i)
        q.append(i)
if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)

q = deque([1])
alr = [1]
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        if i in alr:
            continue
        alr.append(i)
        q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)
    if a == 1:
        ans[b-1] = 1
    if b == 1:
        ans[a-1] = 1

q = deque([1])
alr = [1]
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        if i in alr:
            continue
        alr.append(i)
        q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  N,M=map(int,input().split())
  r=[[]for i in range(N)]
  d,p=[10**6]*N,[10**6]*N

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

  q=deque([0])
  p[0],d[0]=-1,0

  while len(q)!=0:
    i=q.pop()
    for j in r[i]:
      if d[j]>d[i]+1:
        d[j],p[j]=d[i]+1,i
        q.append(j)

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

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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())
A=np.array(A)
B=np.array(B)

C = np.array([1])
C_old = np.array([0])
D = np.array(list(range(M)))
D_old=np.array([0]*M)
E = np.array([0]*N)
F = np.array([0]*N)
#print("{}".format(D))
for i in range(M):
    if not 0 in F[1:N]:
        break
    #print("{}".format(i))
    C_old=[0]
#    print("{}".format(C))
#    print("{}".format(D))
    for j in D:
        #print("A={},B={},j={}".format(A[j],B[j],j))
        if A[j] in C:
            if E[B[j]-1]==0:
                C_old = np.append(C_old, B[j])
                E[B[j]-1]=A[j]
                F[B[j]-1]=1
                D_old[j]=1
             #else:
            #     E[B[j]-1]=min(A[j],E[B[j]-1])
            #print("D={}".format(D))
            #print("{}".format(E))

        elif B[j] in C:
             if E[A[j]-1]==0:
                 C_old = np.append(C_old, A[j])
                 E[A[j]-1]=B[j]
                 F[A[j]-1]=1
                 D_old[j]=1
             #else:
            #     E[A[j]-1]=min(B[j],E[A[j]-1])
             #print("D={}".format(D))
             #print("{}".format(E))

    C = np.append(C, C_old[1:])
    D=[i for i in D if D_old[i]== 0]


if not 0 in F[1:N]:
    print("Yes")
    for i in range(N-1):
        print("{}".format(E[i+1]))

else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)
    if a == 1:
        ans[b-1] = 1
    if b == 1:
        ans[a-1] = 1

q = [1]
alr = [1]
while not len(q) == 0:
    x = q.pop(0)
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        if i in alr:
            continue
        alr.append(i)
        q.append(i)
if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)
    if a == 1:
        ans[b-1] = 1
    if b == 1:
        ans[a-1] = 1

q = [1]
alr = [1]
while not len(q) == 0:
    x = q.pop(0)
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        if i in alr:
            continue
        alr.append(i)
        q.append(i)
if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in range(1, n):
        print(ans[j])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ANS = [-1]*(n+1)
P = []
L = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())

    if a == 1:
        ANS[b] = 1
        P.append(b)
    elif b == 1:
        ANS[a] = 1
        P.append(a)
    else:    
        L[a].append(b)
        L[b].append(a)

# print(L, ANS, P)

i = 0
while len(P) < n-1:
    for j in range(1, n+1):
        if P[i] in L[j] and ANS[j] == -1:
            P.append(j)
            L[j].remove(P[i])
            ANS[j] = P[i]
            # print(i, P[i], j, L, ANS, P)
    i += 1

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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())
A=np.array(A)
B=np.array(B)

C = [1]
C_old = [0]
D = np.array(list(range(M)))
D_old=np.array([0]*M)
E = np.array([0]*N)
F = np.array([0]*N)
#print("{}".format(D))
for i in range(M):
    if not 0 in F[1:N]:
        break
    #print("{}".format(i))
    C_old=[0]
#    print("{}".format(C))
#    print("{}".format(D))
    for j in D:
        #print("A={},B={},j={}".format(A[j],B[j],j))
        if A[j] in C:
            if E[B[j]-1]==0:
                C_old = np.append(C_old, B[j])
                E[B[j]-1]=A[j]
                F[B[j]-1]=1
                D_old[j]=1
             #else:
            #     E[B[j]-1]=min(A[j],E[B[j]-1])
            #print("D={}".format(D))
            #print("{}".format(E))

        elif B[j] in C:
             if E[A[j]-1]==0:
                 C_old = np.append(C_old, A[j])
                 E[A[j]-1]=B[j]
                 F[A[j]-1]=1
                 D_old[j]=1
             #else:
            #     E[A[j]-1]=min(B[j],E[A[j]-1])
             #print("D={}".format(D))
             #print("{}".format(E))

    C = np.append(C, C_old[1:])
    D=[i for i in D if D_old[i]== 0]


if not 0 in F[1:N]:
    print("Yes")
    for i in range(N-1):
        print("{}".format(E[i+1]))

else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
q = deque()
keys = [0] * n
dic = {i: [] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        dic[a - 1].append(b -1)
        q.append(b - 1)
        keys[b - 1] = 1
    elif b == 1:
        dic[b - 1].append(a - 1)
        q.append(a - 1)
        keys[a - 1] = 1
    else:
        dic[a - 1].append(b - 1)
        dic[b - 1].append(a - 1)

while len(q) > 0:
    next = q.popleft()
    for i in dic[next]:
        if keys[i]:
            continue
        if i not in q:
            q.append(i)
            keys[i] = next + 1
print('Yes')
print(*keys[1:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import cos, radians, pi, sqrt
import numpy as np

head = input().split()
N = int(head[0])
M = int(head[1])
inputs = [input() for i in range(M)]

i = 1
dic = {}
for i in range(0, M):
#	print("探索%d回目" % i)
	param = inputs[i].split()
	A = param[0]
	B = param[1]

	if A in dic.keys():
		dic[A].append(B)
	else:
		dic[A] = []
		dic[A].append(B)

	if B in dic.keys():
		dic[B].append(A)
	else:
		dic[B] = []
		dic[B].append(A)
	
depth = {'1': 0}
que = dic['1']
count=1

while not que == []:
	next_que = []
	for room in que:
		if room in depth.keys():
			continue

		depth[room] = count
		for next_room in dic[str(room)]:
			if not next_room in next_que:
				next_que.append(next_room)
	count += 1
	que = next_que
print("Yes")
for i in range(1, N+1):
	for room, dep in depth.items():
		if depth[str(i)]-1 == dep:
			print(room)
			break

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import cos, radians, pi, sqrt
import numpy as np

head = input().split()
N = int(head[0])
M = int(head[1])
inputs = [input() for i in range(M)]

i = 1
dic = {}
for i in range(0, M):
#	print("探索%d回目" % i)
	param = inputs[i].split()
	A = param[0]
	B = param[1]

	if A in dic.keys():
		dic[A].append(B)
	else:
		dic[A] = []
		dic[A].append(B)

	if B in dic.keys():
		dic[B].append(A)
	else:
		dic[B] = []
		dic[B].append(A)
	
depth = {'1': 0}
que = dic['1']
count=1

while not que == []:
	next_que = []
	for room in que:
		if room in depth.keys():
			continue

		depth[room] = count
		for next_room in dic[str(room)]:
			if not next_room in next_que:
				next_que.append(next_room)
	count += 1
	que = next_que

dist = {}
for i in range(1, N+1):
	for room, dep in depth.items():
		if depth[str(i)]-1 == dep:
			dist[str(i)] = room
			break

print("Yes")
for opt in dist.items():
	print(opt[1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
queue=[0]
ans=[-1]*n
ans[0]=0
while len(queue)!=0:
    now_check=queue.pop(0)
    for i in ab[now_check]:
        if ans[i]==-1:
            queue.append(i)
            ans[i]=now_check
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
queue=[0]
ans=[-1]*n
ans[0]=0
while queue:
    now_check=queue.pop(0)
    for i in ab[now_check]:
        if ans[i]==-1:
            queue.append(i)
            ans[i]=now_check
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M = map(int,input().split())

r = [[] for i in range(N+1)]

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

miteru = deque([1])
mita = {1}
res = [-1]*(N+1)

while  miteru: 
    now = miteru.popleft()
    x =set( r[now])
    x = x - mita
    for i in x:
        miteru.append(i)
        if res[i] == -1:res[i] =now
    mita.add(now)
    
print("Yes")
for i in res[2:]:
    print(i)
#print("\n".join(res))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M = map(int,input().split())

r = [[] for i in range(N+1)]

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

miteru = deque([1])
mita = {1}
res = [-1]*(N+1)

while  len(miteru) != 0: 
    now = miteru.popleft()
    x =set( r[now])
    x = x - mita
    for i in x:
        miteru.append(i)
        if res[i] == -1:res[i] =now
    mita.add(now)
    
print("Yes")
for i in res[2:]:
    print(i)
#print("\n".join(res))

Submission status: Time Limit Exceeded

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

for i in range(m):
    AB.append(sorted(map(int,input().split())))
    
AB = sorted(AB)
    
import collections
que = collections.deque()
que.append(1)
    
while que:
    x = que.popleft()
    
    for i in AB:
        a = i[0]
        b = i[1]
        
        if x < a:
            break
        
        if a == x:
            if ans[b-2] == 0:
                ans[b-2] = x
                que.append(b)
        elif b == x:
            if ans[a-2] == 0:
                ans[a-2] = x
                que.append(a)
            
if 0 in ans:
    print("No")
else:
    print("Yes")
    
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

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

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

ld = {}

for i in range(m):
    t = input().split()
    if int(t[0]) in ld:
       ld[int(t[0])].add(int(t[1]))
    else:
       ld[int(t[0])] = {int(t[1])}
    if int(t[1]) in ld:
        ld[int(t[1])].add(int(t[0]))
    else:
        ld[int(t[1])] = {int(t[0])}


if sum(ld.keys()) < int(((n + 1) * n ) / 2):
    print("No")
else:
    s1 = {1}
    s2 = set()
    count = 0
    mydict = {}

    while len(ld) > 0:
        s2.clear()
        for i in ld:
            if len(s1 & ld[i]) != 0:
                #s3 = list(s1 & ld[i])
                mydict.setdefault(i,list(s1 & ld[i])[0])
                s2.add(i)
        for i in s2:
            del ld[i]
        s1 = s2.copy()

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

Submission status: Time Limit Exceeded

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

for i in range(m):
    AB.append(list(map(int,input().split())))
    
import collections
que = collections.deque()
que.append(1)
    
while que:
    x = que.popleft()
    
    for i in AB:
        a = i[0]
        b = i[1]
        
        if a == x and ans[b-2] == 0:
            ans[b-2] = x
            que.append(b)
        elif b == x and ans[a-2] == 0:
            ans[a-2] = x
            que.append(a)
            
if 0 in ans:
    print("No")
else:
    print("Yes")
    
    for i in ans:
        print(i)