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())
G = [[0]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1][b-1] = 1
    G[b-1][a-1] = 1

def bfs(u=0):
    Q = deque([])
    color = ['White']*N
    d = [-1]*N
    d[0] = 0
    Q.append(u)

    while Q:
        u = Q.popleft()
        for v in range(N):
            if G[u][v] == 1 and color[v] == 'White':
                if d[v] != -1:
                    continue
                color[v] = 'Gray'
                d[v] = d[u] + 1
                Q.append(v)
        color[u] = 'Black'
    return d

D = bfs()

if 0 not in D[1:]:
    print('Yes')
    for i in range(1, N):
        print(D.index(D[i]-1)+1)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import deque
N, M = map(int, input().split())
d = [[10^6 for _ in range(N)] for _ in range(N)]
dd = {i:[] for i in range(N)}
for i in range(N):
    d[i][i] = 0
for i in range(M):
    a, b = map(int, input().split())
    dd[a-1].append(b-1)
    dd[b-1].append(a-1)
ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
queue = []
for i in range(len(dd[0])):
    queue.append([0, dd[0][i]])
queue = deque(queue)
while queue:
    q = queue.popleft()
    if visited[q[1]]:
        continue
    visited[q[1]] = True
    ans[q[1]] = q[0] + 1
    for v in dd[q[1]]:
        queue.append([q[1], v])
print("Yes")
print(*ans[1:], sep="\n")

Submission status: Time Limit Exceeded

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

# print(edge)
edge_from = [1]
while sum(reached.values()) < n-1:
    new_edge = []
    for now in edge_from:
        # print(edge[now])
        for e in edge[now]:
            if e != 1 and reached[e] == 0:
                reached[e] = 1
                guide[e] = now
                new_edge.append(e)
    edge_from = new_edge.copy()

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
INF=float("inf")

#始点,頂点の数,辺(頂点ごとの隣接行列)
def dijkstra(start,v,e):
    pre=[i for i in range(v)]
    x=set([i for i in range(v)])
    dist=[INF for _ in range(v)]

    dist[start]=0

    s=start
    while(len(x)>0):
        x.remove(s)

        min_x=-1
        min_dx=float("inf")
        for xi in x:
            if(dist[xi]>dist[s]+e[s][xi]):
                dist[xi]=dist[s]+e[s][xi]
                pre[xi]=s

            if(min_dx>dist[xi]):
                min_dx=dist[xi]
                min_x=xi

        s=min_x

    return pre

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

mark=dijkstra(0, n, edge)
#print(mark)
print('Yes')
for i in range(1,len(mark)):
    print(mark[i]+1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    mark = [-1] * (N+1)
    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if mark[current] == -1:
            mark[current] = prev
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    for s in mark[2:]:
        print(s)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# D

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

 
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np
 
adj_matrix = [[10**9] * N for i in range(N)]
for ab in ABs:
    adj_matrix[ab[0]-1][ab[1]-1] = adj_matrix[ab[1]-1][ab[0]-1] = 1
 
csr = csgraph_from_dense(adj_matrix, null_value=10**9)
from_starts, procs = dijkstra(csr, indices=[0], return_predecessors =True)
from_start = from_starts[0]
proc = procs[0]
 
if -9999 in proc[1:]:
  print('No')
else:
  print('Yes')
  for i in range(N-1):
    print(int(proc[i+1]) + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

n, m = list(map(int, input().split()))
a, b = [], []
d = defaultdict(list)
for i in range(m):
    data = list(map(int, input().split()))
    a.append(data[0])
    b.append(data[1])
    d[data[0]].append(data[1])
    d[data[1]].append(data[0])

mindist = defaultdict(lambda: 1000000)
mindist[1] = 0
sign = defaultdict(int)

dq = deque()
dq.append([1, 0])
while len(dq) > 0:
    room, dist = dq.pop()
    for nroom in d[room]:
        if dist + 1 < mindist[nroom]:
            mindist[nroom] = dist + 1
            sign[nroom] = room
            dq.append([nroom, dist + 1])

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

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    root =[[] for _ in range(N+1)]
    for _ in range(M):
        a,b = LI()
        root[a].append(b)
        root[b].append(a)

    node = [INF] * (N+1)
    ans = [-1] * (N+1)

    q = []
    heapify(q)
    node[1] = 0
    q.append((0,1,-1))

    while q:
        d,v,f = q.pop()
        node[v] = d
        ans[v] = f
        for u in root[v]:
            if node[u] <= d+1: continue
            node[u] = d+1
            q.append((d+1,u,v))

    print('Yes')
    print(*ans[2:],sep='\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int, input().split())

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

D = [10000000 for _ in range(N+1)]
V = [False for _ in range(N+1)]
P = [None for _ in range(N+1)]

D[1] = 0
V[0] = True
P[1] = 1

while True:
    if all([V[i] for i in range(1, N+1)]):
        break

    ti, ic = 10000000, None
    for i in range(1, N+1):
        if not V[i] and D[i] < ti:
            ti = D[i]
            ic = i

    if ic == None:
        print("No")
        sys.exit(0)

    for e in E:
        if e[0] == ic or e[1] == ic:
            if e[0] == ic:
                hi = e[1]
            else:
                hi = e[0]

            if D[hi] > D[ic] + 1:
                D[hi] = D[ic] + 1
                P[hi] = ic
                uf = True

    V[ic] = True

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

Submission status: Time Limit Exceeded

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

pathes = {i: set() for i in range(1, n + 1)}
for _ in range(m):
  ai, bi = map(int, input().split()) 
  pathes[ai].add(bi)
  pathes[bi].add(ai)

queue = [None] * n
queue[0] = 1
idx = 1

ans = [None] * n 

for i in queue:
  next_room = pathes[i] - set(queue)
  for j in next_room:
    ans[j-1] = str(i)
    queue[idx] = j
    idx += 1

ans[0] = "Yes"

print("\n".join(ans))

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, M = nm()
adj = [[] for _ in range(N)]
for i in range(M):
    a, b = nm()
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


def solve():
    INF = 1 << 62
    q = collections.deque([(0, 0, -1)])
    dist = [INF] * N
    prev = [None] * N
    while q:
        l, node, pnode = q.popleft()
        if dist[node] < l:
            continue
        dist[node] = l
        prev[node] = pnode
        for nxt in adj[node]:
            if nxt != pnode and dist[nxt] > l + 1:
                q.append((l + 1, nxt, node))
    if any(x is None for x in prev):
        print("No")
        return
    print("Yes")
    for i in range(1, N):
        print(prev[i] + 1)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
x=[set() for _ in range(n+1)]
lift=[-1 for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    x[a].add(b)
    x[b].add(a)

cnt=0
next={1}
while len(next)>0:
    tmp=set()
    for p in next:
        for q in x[p]:
            if lift[q]==-1: lift[q]=p
            if p in x[q]: x[q].remove(p)
            tmp.add(q)
    next=tmp

if -1 in x[2:]: print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        print(lift[i])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
k=[[] for i in [0]*n]
for i in range(m):
    a,b=map(int,input().split())
    k[a-1]+=[b-1]
    k[b-1]+=[a-1]
l=[0]*n
q=[]
p=[0]
while True:
    q+=p
    s=[]
    for i in p:
        r=k[i]
        for j in r:
            if not j in q:
                l[j]=i+1
                s+=[j]
    p=s
    if len(p)==0:
        break
print("Yes")
for i in l[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
table=[-1]*n
edges=[[] for i in range(n)]
costs=[n]*n
for i in range(m):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)
def dfs(now,pre,cost):
    if costs[now]>cost:
        costs[now]=cost
        table[now]=pre+1
        for i in edges[now]:
            dfs(i,now,cost+1)
dfs(0,0,0)
if -1 not in table[1:]:
    print("Yes")
    for i in range(1,n):
        print(table[i])
else:print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
q = deque()
q.append(0)

ans = [-1 for _ in range(n)]
distance = [float('inf') for _ in range(n)]
distance[0] = 0
ans[0] = 0

visited = set({})

while q:
    start = q.popleft()
    visited.add(start)
    for i in graph[start]:
        distance[i] = min(distance[i], distance[start] + 1)
        if i not in visited:
            q.append(i)
            if (ans[i] == -1):
                ans[i] = start
                
if -1 not in ans:
    print('Yes')
    for i in range(1, n):
        print(ans[i] + 1)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:

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

path = [[] for i in range(N)]
indicator = [None] * N
indicator[0] = (0, 0)
for i in range(M):
    a, b = map(int, input().split())
    a-=1
    b-=1
    path[a].append(b)
    path[b].append(a)

def solve(path, indicator):
    visit = set()
    visit.add(0)
    p = 0
    l = 0

    q = [(0, 0)]

    while q:
        (p, l), q = q[0], q[1:]
        for room in path[p]:
            if room in visit:
                continue
            if indicator[room] is None:
                indicator[room] = (p, l+1)
                q.append((room, l+1))
            elif indicator[room][1] > l+1:
                return []
            visit.add(room)
L = solve(path, indicator)
if L == []:
    print("No")
else:
    print("Yes")
    for p, l in indicator[1:]:
        print(p+1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
N,M = map(int,input().split())
T = [[] for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)

INF = float("inf")
D = [INF]*N
A = [0]*N
Q = [[0,0,-1]]
while Q:
    d,v,p = heappop(Q)
    if d >= D[v]:continue
    A[v] = p
    D[v] = d
    d += 1
    for c in T[v]:
        heappush(Q,[d,c,v])
if INF in D:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(A[i]+1)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import networkx as nx

N, M = map(int, input().split())
G = nx.Graph()

for i in range(N):
    G.add_node(i+1)

for i in range(M):
    a,b = map(int, input().split())
    G.add_edge(a,b)
    
pred, dist = nx.dijkstra_predecessor_and_distance(G, 1)

pred = sorted(pred.items())

print("Yes")
for i in range(1,N):
    print(pred[i][1][0])

Submission status: Time Limit Exceeded

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

v = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in v:
        v[a] = [b]
    else:
        v[a].append(b)

    if b not in v:
        v[b] = [a]
    else:
        v[b].append(a)

st = [1]

ans = [-1 for i in range(n)]
ans[0] = 0

while True:
    buf = []
    updates = {}
    for s in st:
        nex = v[s]
        for to in nex:
            if ans[to-1] != -1:
                continue
            else:
                buf.append(to)
                updates[to-1] = s
    for u in updates.keys():
        ans[u] = updates[u]
    st = buf
    if len(buf) == 0:
        break

print("Yes")
for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,m = na()
    path = [[] for _ in range(n)]
    ans = [0 for i in range(n)]
    check = [1]+[0 for _ in range(n-1)]
    for _ in range(m):
        a,b = na()
        a -= 1
        b -= 1
        path[a] += [b]
        path[b] += [a]
    que = [0]
    while que != []:
        now = que.pop(0)
        for nxt in path[now]:
            if check[nxt] == 0:
                ans[nxt] = now
                check[nxt] = 1
                que.append(nxt)
    if sum(check) == n:
        print('Yes')
        for i in ans[1:]:
            print(i+1)
    else:
        print('No')
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

g = [[] for _ in range(N)]

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

ans_list = [-1] * N

queue = [0]
seen = []

while queue:
    Q = len(queue)
    #print("now", queue, ans_list)
    for _ in range(Q):
        now = queue.pop(0)
        seen.append(now)
        for n in g[now]:
            if ans_list[n] == -1:
                ans_list[n] = now
            # キューに次の距離の要素を追加
            if n not in seen:
                queue.append(n)

print("Yes")
for ans in ans_list[1:]:
    print(ans+1)  # 1-index に直す

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n , m = map(int, input().split())
g = [[0]*n for i in range(n)]
v = [0]*n
v[0]=1
f = [0]*n
for i in range(m):
    a , b = map(int, input().split())
    a-=1
    b-=1
    g[a][b]=1
    g[b][a]=1

d=deque()
d.append(0)

while d:
    room = d.popleft()
    for i in range(n):
        if v[i]==1:
            continue
        if g[room][i]==1:
            d.append(i)
            v[i]=1
            f[i]=room

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
P = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    P[A-1].append(B)
    P[B-1].append(A)
V = [[N,N] for i in range(N)]
V[0] = [0,0]
W = [1]
while(W):
    a = W.pop(0)
    p,q = V[a-1]
    while(P[a-1]):
        s = P[a-1].pop(0)
        if q + 1 <= V[s-1][1]:
            V[s-1] = [a,q+1]
        W.append(s)
print("Yes")
for i in range(N-1):
    print(V[i+1][0])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
q = deque()
q.append(0)

ans = [-1 for _ in range(n)]
distance = [float('inf') for _ in range(n)]
distance[0] = 0
ans[0] = 0

visited = set({})

while q:
    start = q.popleft()
    visited.add(start)
    for i in graph[start]:
        distance[i] = min(distance[i], distance[start] + 1)
        if i not in visited:
            q.append(i)
            if (ans[i] == -1):
                ans[i] = start
                
if -1 not in ans:
    print('Yes')
    for i in range(1, n):
        print(ans[i] + 1)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0
    
    q = deque([0])
    while q:
        now = q.pop()
        for next in g[now]:
            if prev[next] < 0 or dist[now] + 1 < dist[next]:
                prev[next] = now + 1
                dist[next] = dist[now] + 1
                q.append(next)
    if all(prev[i] > 0 for i in range(1, n)):
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    edge[u].append(v)
    edge[v].append(u)

ans = [-1] * n
def bfs(p, v):
    dq = deque()
    dq.append((p, v))
    while dq:
        p, v = dq.popleft()
        if ans[v] == -1:
            ans[v] = p
        for nv in edge[v]:
            if nv == p:
                continue
            if ans[nv] == -1:
                dq.append((v, nv))

bfs(-1, 0)
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    for item in ans[1:]:
        print(item + 1)

Submission status: Time Limit Exceeded

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

d = {}

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

for i in range(M):
    a, b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)
que = [1]
checked = set()
ans = {}
while que:
    now = que.pop(0)
    for h in d[now]:
        if not h in ans and not h == 1:
            ans[h] = now
            que.append(h)
    
if len(ans) == N-1:
    print('Yes')
    for i in range(N-1):
        print(ans[i+2]) 
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    edge = [[] for _ in range(N)]
    
    for _ in range(M):
        a,b = map(int,input().split())
        a -= 1;b -= 1
        edge[a].append(b)
        edge[b].append(a)
        
    d = [10**10]*N
    d[0] = 0
    bef = [-1]*N
    
    q = deque([0])
    while q:
        now = q.pop()
        for fol in edge[now]:
            if d[fol] > d[now]+1:
                d[fol] = d[now]+1
                bef[fol] = now
                q.append(fol)

    if 10**10 not in d:
        print("Yes")
        for i in range(1,N):
            print(bef[i]+1)
    else:
        print("No")
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

INF = float('inf')
dist = [INF]*n # dfsの条件式の書き換えに注意

ans = [-1]*(n)

def dfs(now):
    for next_v in es[now]:
        if dist[next_v] > dist[now]+1:
            dist[next_v] = dist[now]+1
            ans[next_v] = now+1
            dfs(next_v)

start = 0
dist[start]=0 #初期化
dfs(start)

print('Yes')
print(*ans[1:],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
P = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    P[A-1].append(B)
    P[B-1].append(A)
T = 2*M
V = [[N,N] for i in range(N)]
V[0] = [0,0]
W = [1]
while(T >= 0 and W):
    a = W.pop(0)
    p,q = V[a-1]
    for i in range(len(P[a-1])):
        s = P[a-1].pop(0)
        T -= 1
        if q + 1 <= V[s-1][1]:
            V[s-1] = [a,q+1]
        W.append(s)
print("Yes")
for i in range(N-1):
    print(V[i+1][0])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq


class Dijkstra:
    """
    dijkstraの最短経路問題を解く
    input:
        S: start node
        mat : mat[a][b] = edge_weight(a,b)
    """

    def __init__(self, start, num_node, mat):
        """
        mat: mat[a][b] = edge_weight(a,b)
        num_node: num of nodes
        dist: dist from start_node
        prev: 最短経路において、一つ前のノードを記憶。経路復元に使う?
        """
        self.start_node = start
        self.mat = mat
        self.num_node = num_node
        self.dist = [float('inf')]*num_node
        self.prev = defaultdict(lambda: None)

        # dist form S to S = 0
        self.dist[start] = 0

    def calc_dist(self):
        """
        最短経路 distを計算する
        Q: content (dist_from_start,node)
        Qはheapqとして使う。dist_from_startの小さい順になる
        """
        Q = []
        heapq.heappush(Q, (0, self.start_node))
        while Q:
            dist_to_node, node = heapq.heappop(Q)
            # 現在の値よりも大きくて、更新にならない場合
            if self.dist[node] < dist_to_node:
                continue

            # 次のホップを計算する
            for nex in range(self.num_node):
                weight = self.mat[node][nex]
                cand = dist_to_node + weight

                if self.dist[nex] > cand:  # update
                    self.dist[nex] = cand
                    self.prev[nex] = node
                    heapq.heappush(Q, (cand, nex))

    def get_dist(self, d):
        """
            startからdまでの距離を返す
            これの前にcalc()を実行しておく
            たどり着けない場合は、float('inf')がかえる
        """
        return self.dist[d]
    def get_path(self,dst):
        """
        startからdstまでのpathをlistでreturn
        valifyしてないので怪しい
        """
        cur=dst
        ret=[cur]
        while cur!=self.start_node:
            cur=self.prev[cur]
            ret.append(cur)
        return list(reversed(ret))

N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

grid=[[float("inf")]*N for _ in range(N)]

for a,b in edges:
    grid[a][b]=1
    grid[b][a]=1

D = Dijkstra(0,N,grid)
D.calc_dist()

ans=[]
for i in range(1,N):
    ans.append(D.prev[i]+1)
print("Yes")
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
# ABC168d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))
    from collections import deque
    INF = 10**12

    class Edge:  # 通常の辺
        def __init__(self, to, cost):
            self.to = to
            self.cost = cost

    class Dijkstra:  # ダイクストラ法 O((V+E) * logV)

        def __init__(self, vCount):
            self.vCount = vCount
            self.dist = [INF for _ in range(vCount)]
            self.frm = [-1]*vCount
            self.edges = [list() for _ in range(vCount)]
            self.q = deque()

        def calcShortest(self, start):
            self.q.append((start, 0, -1))
            while(len(self.q) != 0):
                v, cost, frm = self.q.popleft()  # 頂点vへのコストをcostで更新
                if self.dist[v] < cost:
                    continue
                self.dist[v] = cost
                self.frm[v] = frm
                for edge in self.edges[v]:
                    self.q.append((edge.to, cost+edge.cost, v))

        def addEdge(self, st, gl, cost):
            self.edges[st].append(Edge(gl, cost))

    n, m = map(int, input().split())
    graph = Dijkstra(n)
    for _ in range(m):
        a, b = map(int, input().split())
        graph.addEdge(a - 1, b - 1, 1)
        graph.addEdge(b - 1, a - 1, 1)
    graph.calcShortest(0)
   # print(graph.dist)
    # print(graph.frm)
    if INF in graph.dist:
        print('No')
        exit(0)
    print('Yes')
    for i in graph.frm[1:]:
        print(i+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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


que = collections.deque()
que.append([0])
visited = [0] * n
visited[0] = []
while que:
  way = que.popleft()
  for gi in G[way[-1]]:
    if visited[gi] == 0:
      visited[gi] = way 
      que.append(way + [gi])
for vi in visited:
  if vi == 0:
    print("No")
else:
  print("Yes")
  for i in range(1,n):
    print(visited[i][-1]+1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
G = [[] for i in range(N+1)]
ans = [0 for i in range(N+1)]
S = []
A = [1]
for i in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
while len(A) > 0:
    c = A.pop(0)
    for s in G[c]:
        if s not in S:
            S.append(s)
            ans[s] = c
            A.append(s)
print('Yes')
for i in range(2,N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:

import sys
import queue
sys.setrecursionlimit(10**7)


def inpl():
    return list(map(int, input().split()))


N, M = inpl()

lines = [[] for _ in range(N)]
for _ in range(M):
    a, b = inpl()
    a -= 1
    b -= 1
    lines[a].append(b)
    lines[b].append(a)


ans = [-1] * N


q = queue.Queue()
q.put((0, 0))
while not q.empty():
    s, b = q.get()

    if ans[s] != -1:
        continue
    else:
        ans[s] = b
        for t in lines[s]:
            q.put((t, s))


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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
route = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  route[A-1].append(B-1)
  route[B-1].append(A-1)
ans = [-1]*(N)

def bfs():
  tmp = 0
  prv = 0
  visited = [False]*N
  kouho = deque()


  for room in route[0]:
    kouho.append([room,0])
  while True:
    visited[tmp] = True
    ans[tmp] = prv
    for room in route[tmp]:
      if not visited[room]:
        kouho.append([room,tmp])
    if len(kouho) == 0:
      return
    while True:
      tmp_ = kouho.popleft()
      tmp = tmp_[0]
      prv = tmp_[1]
      if not visited[tmp]:
        break
      if len(kouho) == 0:
        return
bfs()
print("Yes")
for n in range(1,N):
  print(ans[n]+1)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
adjacent=[set() for x in range(N)]
for m in range(M):
    A,B=map(int,input().split())
    adjacent[A-1].add(B-1)
    adjacent[B-1].add(A-1)
ans=[0]*N
deque1=deque()
already=set()
already.add(0)
num_already=1
for j in adjacent[0]:
    deque1.append(j)
    already.add(j)
    num_already+=1
    ans[j]=1
while(num_already!=N):
    now=deque1.popleft()
    for k in adjacent[now]:
        if k not in already:
            num_already+=1
            already.add(k)
            ans[k]=now+1
            deque1.append(k)
print("Yes")
for i in range(1,N):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,m=input2()
g=[[] for _ in range(n+1)] #引数->要素で道しるべを保存
for i in range(m):
	a,b=input2()
	g[a].append(b)
	g[b].append(a)

q=deque() #bfs用
q.append(1) #始点

check=[0]*(n+1) #既に訪問している(1)か否(0)か
check[1]=1

ans=[0]*(n+1) #始点に近い側の，一つ前の要素(解答)
ans[1]=1
for _ in range(10**5+1):
	if len(q)==0:
		break
	v=q.popleft() #頂点を一つ取り出す
	for u in g[v]: #vとの通路を全て探索
		if check[u]==0: 
			check[u]=1 #探索済み==1
			ans[u]=v 
			q.append(u)
print("Yes")
for i in range(2,n+1):
	print(ans[i])