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: Runtime Error

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
    a, b  = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(i, d, frag):
    for j in d[i]:
        if j not in frag:
            frag[j] = i
            dfs(j, d, frag)

frag = defaultdict()
dfs(1, graph, frag)
if len(frag.keys()) < n - 2:
    print('No')
else:
    print('Yes')
    for i in range(2, n + 1):
        print(frag[i])

Submission status: Runtime Error

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

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

ikeru = [set() for _ in range(m+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
if hantei:
    print('Yes')
    for j in range(2,n+1):
        print(ans[j])
else:
    print('No')

Submission status: Runtime Error

Solution code:
import sys, math, bisect

N, M= map(int, sys.stdin.readline().split())
AB = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]

edge =[[] for _ in range(N)]
for ab in AB:
    bisect.insort(edge[ab[0]-1], (ab[1]-1))
    bisect.insort(edge[ab[1]-1], (ab[0]-1))
    
#print(edge)
sys.setrecursionlimit(100000)


def dfs(now, cnt =1, before=-1):#before:一つ前に通ったノード
    #if before==-1:
        #print(now)
    for c in edge[now]: #c:子
        if not c ==before: #無限ループを防ぐ
            #print(c)
            if c==0:
                L.append(cnt)
                break
            else:
                dfs(c, cnt+1, now) #再帰

ans = []
for i in range(1, N):
    L = []
    dfs(i)
    ans.append(min(L))
print('Yes')
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import math


def to_minutes(hour: int, minute: int) -> int:
    return 60 * hour + minute


def to_degree(total_minutes: int, unit_of_rotation: int) -> float:
    number_of_rotation = total_minutes / unit_of_rotation

    fractional_part = math.modf(number_of_rotation)[0]

    return 360 * fractional_part


def actual(a, b, hour, minute):
    """作戦: それぞれの回転数 → それぞれの角度 → 狭角の角度 → 余弦定理"""
    total_minutes = to_minutes(hour, minute)

    unit_of_rotation_hours = 720
    degree_of_hours = to_degree(total_minutes, unit_of_rotation_hours)

    unit_of_rotation_minute = 60
    degree_of_minutes = to_degree(total_minutes, unit_of_rotation_minute)

    degree_of_C = abs(degree_of_hours - degree_of_minutes)
    C_radian = math.radians(degree_of_C)

    cosC = math.cos(C_radian)

    return math.sqrt(a ** 2 + b ** 2 - 2 * a * b * cosC)
  
a, b, h, m = map(int, input().split())

print(actual(a, b, h, m))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N,M = map(int,input().split())
graph = np.zeros((N,N),dtype=int)
for _ in range(M):
    A,B = map(int,input().split())
    A,B = A-1,B-1
    graph[A,B] = 1
    graph[B,A] = 1
print("Yes")
for i in range(1,N):
    d,p = shortest_path(graph,directed=False,return_predecessors=True)
    print(p[0][i]+1)

Submission status: Runtime Error

Solution code:
// 
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
namespace you {
    std::string to_string(char val) {
        return std::string(1, val);
        // return std::string{val};
        // you::to_string(char)
    }
}

int num=pow(10,5)+10;
vector<vector<int>> node(num);
vector<int> seen(num,0);
vector<int> miti(num);
vector<int> setu(num,0);
vector<int> ans(num,0);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        node[a].push_back(b);
        node[b].push_back(a);
        setu[a]+=1;
        setu[b]+=1;
    }
    vector<int> next(num,1);
    vector<int> hen(num,0);
    int sou=1;
    int total=0; //今まで見た数
    while(total<=n){
        int ne=0;
        for(int i=0;i<sou;i++){
            int now=next[total+(i+1)];
            //cout<<now<<endl;
            seen[now]=1;
            for(int j=0;j<setu[now];j++){
                if(seen[node[now][j]]==1) continue;
                ne+=1;
                next[total+sou+ne]=node[now][j];
                if(hen[node[now][j]]==0){
                    ans[node[now][j]]=now;
                    hen[node[now][j]]=1;
                }
            }
        }
        total+=sou;
        sou=ne;
    }
    cout<<"Yes"<<endl;
    for(int i=2;i<=n;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
def main(AB, N, M):

    def serch(st = {1}, already = {1}, dict = {1:1}):
        next_dict = dict.copy()
        # for l in st:
        #     for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]:
        #         next_dict.setdefault(i, l)
        # next_dict.update({i:l for l in st for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]})
        [next_dict.setdefault(i, l) for l in st for i in [ab[0] if ab[1] == l else ab[1] for ab in AB if l in ab]]
        next_st = {k for k in next_dict if k not in already}
        [already.add(k) for k in next_st]
        if len(already) == N:
            return next_dict
        elif len(next_st) == 0:
            print('No')
            exit()
        else:
            return serch(next_st, already, next_dict)

    ans = serch()
    print('Yes')
    [print(ans[i + 1]) for i in range(1, N)]



if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    AB = []
    for _ in range(M):
        AB.append(list(map(int, input().split())))
    main(AB, N, M)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
root_list = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    if tmp[0] != tmp[1] and tmp not in root_list
    root_list.append(list(map(int, input().split())))

answer_list = [0] * (n-1)
done_list = [1]
already_list = [1]
while len(root_list) > 0 and 0 in answer_list:
    if len(done_list) == 0:
        break
    tmp_list = []
    copy_root_list = root_list.copy()
    for num in done_list:
        for l in root_list:
            if l[1] == num:
                if answer_list[int(l[0]-2)] == 0:
                    answer_list[int(l[0]-2)] = num
                    tmp_list.append(l[0])
                    already_list.append(l[0])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
            elif  l[0] == num and l[0] != l[1]:
                if answer_list[int(l[1]-2)] == 0:
                    answer_list[int(l[1]-2)] = num
                    tmp_list.append(l[1])
                    already_list.append(l[1])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
    root_list = copy_root_list
    done_list = tmp_list

if 0 not in answer_list:
    print("Yes")
    for i in answer_list:
        print(int(i))
else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
    a, b  = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(i, d, frag):
    for j in d[i]:
        if j not in frag:
            frag[j] = i
            dfs(j, d, frag)

frag = defaultdict()
dfs(1, graph, frag)
if len(frag.keys()) < n - 2:
    print('No')
else:
    print('Yes')

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
arr = [[] for i in range(N+1)]
ret = [0]*(N+1)
for i in range(M):
    a,b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

def dfs(nd,vi):
    if nd == 1:
        if len(vi):
            print(vi[1])
    v[nd] = 1
    for i in arr[nd]:
        if not v[i]:
            dfs(i,vi+[i])
print("YES")
for i in range(2,N+1):
    v = [0]*(N+1)
    dfs(i,[i])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
#signにはみちしるべを置くべき場所のリストを保存する
sign = [0] * N
roads = []
for i in range(N):
    roads.append(list(map(int, input().split())))
#print(sign)
#print(roads)
tmp = [1]
tmp_now = []
#print(len(roads))
while len(roads) > 0:
    for road in roads:
        if road[0] in tmp:
            sign[road[1]-1] = road[0]
            roads.remove(road)
            tmp_now.append(road[1])
            #print(sign)
            #print(roads)
        elif road[1] in tmp:
            sign[road[0]-1] = road[1]
            roads.remove(road)
            tmp_now.append(road[0])
            #print(sign)
            #print(roads)
    tmp = tmp_now
#print(sign)
#print(roads)
sign[0] = "Yes"
#print(sign)
for _ in sign:
    print(_)

Submission status: Runtime Error

Solution code:
import queue

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

road = [[] for i in range(m)]

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

# cost to isMin
result = [[999999999999999, None, False] for i in range(n)]

# from tom
q = queue.Queue()

result[0] = [0, None, True]
for i in road[0]:
    q.put([0,i])

while not q.empty():
    n = q.get()
    result[n[1]]=[result[n[0]][0]+1, n[0], True]
    for i in road[n[1]]:
        if(not result[i][2]):
            q.put([n[1], i])

flag = True
for i in result:
    if(not i[2]):
        flag = False
        break

if(flag):
    print("Yes")
    for i in range(1,len(result)):
        print(result[i][1]+1)
else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,m = map(int,input().split())
graph = defaultdict(list)
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

ans = [None]*(n-1)
check = [i for i in range(2,n+1)]
tmp = []
for j in graph[1]:
    ans[j-2] = 1
    check.remove(j)
    tmp.append(j)

while check != []:
    new_tmp = []
    for i in tmp:
        for j in graph[i]:
            if ans[j-2] == None and j != 1:
                ans[j-2] = i
                check.remove(j)
                new_tmp.append(j)
    tmp = new_tmp
print(ans)

Submission status: Runtime Error

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

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

# print(G)

ans = [-1] * n
d = [10**9] * n
d[0] = 1

ans[0] = 'Yes'
# print(ans)

from collections import deque

q = deque([0])

pos = 0
while q:
    _q = q.popleft()
    # print(ans, q, d)
    for x in G[_q]:
        if ans[x] == -1:
            ans[x] = _q
            q.append(x)
    pos += 1

# print(ans)

if -1 in ans:
    print('No')
else:
    print('Yes')
    for _ans in ans[1:]:
        print(_ans+1)

Submission status: Runtime Error

Solution code:
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
if hantei:
    print('Yes')
    for j in range(2,n+1):
        print(ans[j])
else:
    print('No')

Submission status: Runtime Error

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

if __name__ == '__main__':    
    N, M = map(int, input().split())
    p = np.zeros((N, N))
    for m in range(M):
        A, B = map(int, input().split())
        p[A-1, B-1] = 1
        p[B-1, A-1] = 1
    csr = csr_matrix(p)
    _, predecessors = dijkstra(csr, directed=False, indices=0, return_predecessors=True)
    if -9999 in predecessors[1:]:
        print('No')
    else:
        print('Yes')
        for n in range(N-1):
            print(predecessors[n+1]+1)

Submission status: Runtime Error

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

N, M = map(int, input().split())
a = np.zeros((N, N))

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

a, b = shortest_path(a, indices=0, return_predecessors=True)

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

print('Yes')

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

Submission status: Runtime Error

Solution code:
import sys
import networkx as nx
n,m=map(int,input().split())
g = nx.Graph()
l = sys.stdin.readlines()
for x in l:
    g.add_edge(int(x[0]), int(x[2]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = [int(i) for i in input().split()]
route = np.zeros([N, N])
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    route[A-1, B-1] = 1
    route[B-1, A-1] = 1
op = np.zeros([N])
for i in range(N):
    if route[0][i] == 1:
        op[i] = 1
for l in range(N):
    for j in range(N):
        if op[j] == l+1:
            for k in range(N):
                if route[j][k] == 1:
                    if op[k] == 0:
                        op[k] = j+1
flag = 0
for i in op:
    if i == 0:
        print("No")
        flag = 1
        break
if flag == 0:
    print("Yes")
    for i in range(len(op) - 1):
        print(int(op[i+1]))

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

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

base = np.zeros((n,n))
ans_base = np.zeros(n)

for i in range(m):
  a,b = map(int,input().split())
  base[a-1][b-1] = 1
  base[b-1][a-1] = 1
  
temp = deque([])
temp.append(0)

while temp:
  a = temp.popleft()
  for i in range(n):
    if base[a][i] == 1:
      temp.append(i)
      if ans_base[i] == 0:
        ans_base[i] = a+1
      base[i][a] = 0

ans_ini = "Yes"

if 0 in ans_base[1:]:
  ans_ini = "No"
  
print(ans_ini)

if ans_ini == "Yes":
  for i in range(1,n):
    print(int(ans_base[i]))

Submission status: Runtime Error

Solution code:
def fn(d, tmpkey, ans):
  for each in d[tmpkey]:
    ans[each-1] = tmpkey

  if 0 not in set(ans):
    return ans
  else:
    return fn(d, each, ans)


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

d = {}
for _ in range(m):
  a, b = map(int, input().split())
  d[a] = d.get(a, []) + [b]
  d[b] = d.get(b, []) + [a]

print(d)
ans = fn(d, 1, [0 for _ in range(n)])
print("Yes")
for s in ans[1:]:
  print(s)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N,M = map(int,input().split())
ans = [[0,0]] * (N+1)
road = defaultdict(list)
checked = [0] * (N+1)

def check(x,r):
    global ans
    if checked[x] == 0 or checked[x] > r:
        checked[x] = r
        for i in road[x]:
            if ans[i][0] == 0 or ans[i][1] > r:
                ans[i] = [x,r]
        for i in road[x]:
            check(i,r+1)

for i in range(M):
    A,B = map(int,input().split())
    road[A].append(B)
    road[B].append(A)
check(1,0)
print("Yes")
for i in ans[2:]:
    print(i[0])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N,M = map(int,input().split())
graph = np.zeros((N,N),dtype=int)
for _ in range(M):
    A,B = map(int,input().split())
    A,B = A-1,B-1
    graph[A,B] = 1
    graph[B,A] = 1
print("Yes")
for i in range(1,N):
    d,p = shortest_path(graph,directed=False,return_predecessors=True,unweighted=True)
    print(p[0][i]+1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = []
B = []

count = [0 for i in range(N - 1)]
points = [[] for i in range(N - 1)]
flag = False
for i in range(M):
    a, b = map(int, input().split())
    if a != 1:
        points[a - 2].append(b)
    if b != 1:
        points[b - 2].append(a)

for i in range(N - 1):
    tmp = set(points[i])
    nodes = []
    while True:
        if 1 in tmp:
            count[i] += 1
            break
        else:
            count[i] += 1
            for t in tmp:
                nodes.extend(points[t - 2])
            nodes = set(nodes)
        if count[i] == N:
            flag = True
            break
        tmp = nodes
if flag:
    print('No')
else:
    print('Yes')
    for c in count:
        print(c)

Submission status: Runtime Error

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)
                j += 1
            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)
                j += 1
            else:
                j += 1
    room = nroom
    if len(a) == 0 and None in cage.values():
        print('No')
        break
else:
    print('Yes')
    for i in range (2,n+1):
        print(cage[i])

Submission status: Runtime Error

Solution code:
MAX_INT = 10**6
N, M = map(int, input().split())
room = [set() for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    room[a].add(b)
    room[b].add(a)

dis = [MAX_INT] * (N + 1)
sign = [-1] * (N + 1)
dis[1] = 0
def sign_root(n):
    for i in room[n]:
        if dis[n] + 1 < dis[i]:
            sign[i] = n
            dis[i] = dis[n] + 1
            sign_root(i)
sign_root(1)
if MAX_INT in dis[2:]:
    print("No")
else:
    print("Yes")
    for i in sign[2:]:
        print(i)

Submission status: Runtime Error

Solution code:
from collections import deque
n, m  = map(int, input().split())
a  = []
b = [[] for _ in range(m)]
for i in range(m):
    a.append(list(map(int, input().split())))
    

for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])

seen = [-1]*n
seen[0] = 1
que = deque([1])
while que:
    v = que.popleft()
    for i in b[v-1]:
        if seen[i-1] != -1:
            continue
        que.append(i)
        seen[i-1] = v

for i in range(n):
    if seen[i] == -1:
        print("No")
else:
    del seen[0]
    print("Yes")
    for i in range(n-1):
        print(seen[i])

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = map(int,input().split())
G = [set() for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)
ans = [-1 for _ in range(n)]

ans[0]=0
q = deque([0])
q2 = deque()

seen = set()
seen.add(0)

for _ in range(n):
    while q:
        q2 = deque()
        #print(ans,q,q2,seen)
        i = q.pop()
        for j in G[i]:
            if j in seen:
                continue
            q2.append(j)
            ans[j] = i+1
            seen.add(j)
            '''if cost[i] ==-1:
                cost[i] = c
                ans[i] = j
            elif cost[i] > cost[j] + 1:
                cost[i] = cost[j] + 1
                ans[i] = j
            else:
                pass'''
    q = q2
    if len(seen) == n:
        print("Yes")
        print(*ans[1:], sep="\n")
        sys.exit()
        
print("No")

Submission status: Runtime Error

Solution code:
N, M = list(map(int,input().split()))
A = [0] * M
B = [0] * M
X = [float('inf')] * N
for i in range(M):
  A[i], B[i] = map(int,input().split())
  if A[i] == 1:
    X[B[i]-1] = 1
    box = B[i]
    cout = i
  elif B[i] == 1:
    X[A[i]-1] = 1
    box = A[i]
    cout = i
for j in range(1,N):
  for i in range(M):
    if i == cout:
      continue
    if A[i] == box:
      X[B[i]-1] = j+1
      box = B[i]
      cout = i
    elif B[i] == box:
      X[A[i]-1] = j+1
      box = A[i]
      cout = i
print('Yes')
for i in range(1,N+1):
  print(X[i])

Submission status: Runtime Error

Solution code:
import sys
import os
import bisect, collections, copy, itertools, math, string
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int, input().split()))
def LS(): return list(input().split())

def solve():
	n, m = LI()
	a = []
	for i in range(m):
		c, d = LI()
		a.append((c-1, d-1))

	# 隣接行列の作成
	l = np.zeros((n,n))
	for _a in a:
		l[_a[0]][_a[1]] = 1
		l[_a[1]][_a[0]] = 1

	d, p = shortest_path(csr_matrix(l), return_predecessors=True)

	def get_path(start, goal, pred):
		return get_path_row(start, goal, pred[start])

	def get_path_row(start, goal, pred_row):
		path = []
		i = goal
		while i != start and i >= 0:
			path.append(i)
			i = pred_row[i]
		if i < 0:
			return []
		path.append(i)
		return path[::-1]

	dic = {}
	flag = True
	for i in range(1, n):
		path = get_path(0, i, p)
		path.reverse()
		for j in range(len(path)-1):
			dic.setdefault(path[j]+1, path[j+1]+1)
			if not dic[path[j]+1] == path[j+1]+1:
				print('No')
				return
	print('Yes')
	for i in range(2, n+1):
		print(dic[i])







if __name__ == '__main__':
	solve()

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split(" "))
l=[]
for i in range(m):
  l.append(list(map(int,input().split(" "))))


d=[n+1 for i in range(n)]
d[0]=0

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


d=[n+3 for i in range(n)]
d[0]=0

for i in range(n):
    for j in l:
        if j[0]-1==i:
            d[j[1]-1]=min(d[j[1]-1], d[i]+1)
            l.remove(j)
        elif j[1]-1==i:
            d[j[0]-1]=min(d[j[0]-1],d[i]+1)
            l.remove(j)
            
            
j="Yes"
for i in range(n):
    if d[i]==n+3:
        j="No"
print(j)
for i in range(1,n):
    print(d[i])

Submission status: Runtime Error

Solution code:

def solve(a, b, ab_list):

    route = {}

    for a, b in ab_list:
        if a not in route:
            route[a] = []
        if b not in route:
            route[b] = []

        route[a].append(b)
        route[b].append(a)

    def func(x, memo):
        if  1 in route[x]:
            return True
        else:
            tmp = False
            for y in route[x]:
                if y not in memo:
                    memo.append(y)
                    tmp = func(y, memo)
                if tmp:
                    return True
            return False
    ans = []
    flg = True
    for i in range(2, n+1):
        memo = []
        if func(i, memo):
            if len(memo) == 0:
                memo.append(1)
            ans.append(memo[-1])
        else:
            flg = False
            break

    if flg:
        print("Yes")
        for i in ans:
            print(i)
    else:
        print("No")

if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    ab_list = [[int(i) for i in input().split()] for j in range(m)]
    solve(n, m, ab_list)

Submission status: Runtime Error

Solution code:
import numpy as np
import copy

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

edge = np.zeros([N,N])
for i in range(M):
    e = [int(x) for x in input().split()]
    edge[e[0]-1,e[1]-1] = 1
    edge[e[1]-1,e[0]-1] = 1

sign = np.zeros(N-1)
room = np.ones(N)
room[0] = 0
n_check = 0

# edge luck
if M<N-1:
    print('No')
else:
    check = [0]
    flag = 1
    
    for i in range(N):
        if flag:
            check_ = []
                
            for c in check:
                connect = np.nonzero(edge[int(c)])[0]
                nogo = np.nonzero(room)[0]
                if len(nogo)==0:
                    flag = 0
                    break
                """
                for con in list(set(connect)&set(nogo)):
                    room[con] = 0
                    check_.append(con)
                    sign[con-1] = int(c+1)
                """
                cons = np.array(list(set(connect)&set(nogo)))
                room[cons] = 0
                check_ = np.append(check_,list(cons))
                ind = cons-1
                val = cons+1
                sign[ind] = val
                
                
            if len(check_) == 0:
                flag = 0
                break
            else:
                check = copy.deepcopy(check_)
        else:
            break
    if len(np.nonzero(sign)[0]) == N-1:
        print('Yes')
        for s in sign:
            print(int(s))
    else:
        print('No')

Submission status: Runtime Error

Solution code:
import heapq

max_v,m = input().split()
max_v = int(max_v)
m = int(m)

class Edge(object):
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


edges = [[] for j in range(max_v)]
for i in range(max_v):
  a, b = input().split()
  a = int(a)
  b = int(b)
  edges[a-1].append(Edge(b-1,1))
  edges[b-1].append(Edge(a-1,1))

d = [float("inf")]*max_v
fire = [-1]*max_v
def dijkstra(s):
	h = []
	d[s] = 0
	heapq.heappush(h, [0,0])
	while(len(h) != 0):
		p = heapq.heappop(h)
		v = p[1]
		if d[v] < p[0]:continue
		for i in range(len(edges[v])):
			e = edges[v][i]
			if d[e.to] > d[v] + e.cost:
				d[e.to] = d[v] + e.cost
				heapq.heappush(h, [d[e.to], e.to])
				fire[e.to] = v
dijkstra(0)
if 2 <= fire.count(-1):
  print("No")
else:
  print("Yes")
  for i in range(max_v-1):
    print(d[i+1])

Submission status: Runtime Error

Solution code:
import sys
import networkx as nx
n,m=map(int,input().split())
g = nx.Graph()
l = sys.stdin.readlines()
for x in l:
    g.add_edge(int(x[0]), int(x[2]))
l=[None]*(n-1)
for i in range(2,n+1):
    l[i-2] = nx.shortest_path(g, source=1, target=i)[-2]
if None in l:
    print("No")
else:
    print("Yes")
    for x in l:
        print(x)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import copy

def input():
    return sys.stdin.readline()[:-1]

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

"""
MAP = np.zeros(N*N).reshape(N, N)

for ab in AB:
	MAP[ab[0]-1, ab[1]-1] = 1

print(MAP)
"""

ans = [[i, 0] for i in range(1, N+1)]


temae = []
rm = []
count = 0
for i, [a, b] in enumerate(AB):

	if a == 1:
		ans[b-1][1] = 1
		temae.append(b)
		rm.append(i)
		count += 1
	elif b == 1:
		ans[a-1][1] = 1
		temae.append(a)
		rm.append(i)
		count += 1

for i in sorted(rm, reverse=True):
	AB.pop(i)

while count < N-1:
	temae2 = []
	rm = []
	#print("AB", AB)
	#print("temae", temae)
	#print("ans", ans)
	for i, [a, b] in enumerate(AB):
		if a in temae:
			if ans[b-1][1] == 0:
				ans[b-1][1] = a
				temae2.append(b)
				rm.append(i)
				count += 1
			else:
				pass
		elif b in temae:
			if ans[a-1][1] == 0:
				ans[a-1][1] = b
				temae2.append(a)
				rm.append(i)
				count += 1
			else:
				pass

	if len(temae2) == 0:
		break
	else:
		for i in sorted(rm, reverse=True):
			AB.pop(i-1)
		temae = copy.copy(temae2)

for i in ans[1:]:
	print(i[1])

Submission status: Runtime Error

Solution code:
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[ i ], b[ i ] )


def search( x ):
    for i, ai in enumerate( a ):
        y = b[ i ]
        if ai == x and l[ y-1 ] > l[ x-1 ]:
            l[ y-1 ] = l[ x-1 ] + 1
            s[ y-1 ] = x
            search( y )
    for i, bi in enumerate( b ):
        y = a[ i ]
        if bi == x and l[ y-1 ] > l[ x-1 ]:
            l[ y-1 ] = l[ x-1 ] + 1
            s[ y-1 ] = x
            search( y )



l = [ 10000000000 ] * n
l[ 0 ] = 0
s = [ 0 ] * n
search( 1 )

print( "Yes" )
for i in range( n ):
#    print( l[ i ], s[ i ] )
    print( s[ i ] )

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
data = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    data[a - 1].append(b - 1)
    data[b - 1].append(a - 1)

ans = [0] * (n - 1)

def bfs(i, queue, p):
    if len(queue) == 0:
        return 
    while len(queue) > 0:
        x = queue.pop(0)
        pre = p.pop(0)
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                queue.append(data[x[j]])
                p.append(x[j])
        bfs(x[j], queue, p)

queue = []
pre = [0]
queue.append(data[0])
bfs(0, queue, pre)

if 0 not in ans:
    print("Yes")
    for i in range(len(ans)):
        print(ans[i])
else:
    print("No")