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: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
from collections import deque


def resolve():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]

    graph = [[] for _ in range(n)]
    ans = [-1 for _ in range(n - 1)]

    for a, b in ab:
        graph[a - 1].append(b)
        graph[b - 1].append(a)

    # 1につながっている部屋にはすべて置く
    # for i in graph[0]:
    #     if ans[i - 2] != -1:
    #         ans[i - 2] = 1
    #
    # while next_l:
    #     i = next_l.pop()
    #     if ans[i - 2] != -1:
    #         ans[i - 2] =
    #         next_l.append(graph[i - 1])

    d = deque()
    d.append([1, graph[0]])

    while d:
        # print(d, ans)
        node, l = d.popleft()

        for i in l:
            if ans[i - 2] == -1:
                ans[i - 2] = node
                d.append([i, graph[i - 1]])

        if -1 not in set(ans):
            break

    if -1 in set(ans):
        print('No')
    else:
        print('Yes')
        for a in ans:
            print(a)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 4
1 2
2 3
3 4
4 2"""
        output = """Yes
1
2
2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6"""
        output = """Yes
6
5
5
1
1"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

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

path = []

for _ in range(m):
    ai, bi = map(int, input().split())
    path.append([ai, bi])

# print(path)

linked = [[]]

ans = {}


for pi in path:
    for i, l in enumerate(linked):
        flg = False
        if pi[0] in l:
            flg = True
            l.add(pi[1])
            if pi[1] not in ans:
                ans[pi[1]] = pi[0]
        elif pi[1] in l:
            flg = True
            l.add(pi[0])
            if pi[0] not in ans:
                ans[pi[0]] = pi[1]

        if flg:
            break
        if i == len(linked) - 1:
            linked.append(set(pi))
            ans[pi[1]] = pi[0]
            ans[pi[0]] = pi[1]


linked.pop(0)
# print(linked)
# print(ans)

len_l = len(linked)

max_len = -1
ans_idx = -1


tmp_l = [[]]
for i in range(len_l):
    for j in range(len_l):
        if not linked[i].isdisjoint(linked[j]):
            tmp_l.append(linked[i] | linked[j])


for i in range(len(tmp_l)):
    if 1 in tmp_l[i]:
        max_len = max(len(tmp_l[i]), max_len)
        if max_len == len(tmp_l[i]):
            ans_idx = i

if len(tmp_l[ans_idx]) == n:
    print('Yes')
    for i in range(1, n):
        print(ans[i+1])
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())

road = [[] for _ in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    road[A].append(B)
    road[B].append(A)
# print(road)


ans = [-1] * (N + 1)
ans[1] = 0
ans[0] = 0

stack = deque([])
for r in road[1]:
    stack.append(r)


def dfs(s):
    now = s
    while len(stack) > 0:
        for r in road[now]:
            if ans[r] == -1:
                stack.append(r)
                ans[r] = now
        # print(now)
        now = stack.popleft()
        # print(ans)
        # print("stack", stack)
        # print()

dfs(1)
temp = set(ans)
if ((-1) in temp):
    print("No")
else:
    print("Yes")
    for a in ans[2:]:
        print(a)

Submission status: Wrong Answer

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

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

row = list(ABs.T[0]-1) + list(ABs.T[1]-1)
col = list(ABs.T[1]-1) + list(ABs.T[0]-1)
data = [1] * (2 * M)

csr = csr_matrix((data, (row, col)), shape=(N, N))
from_starts, procs = dijkstra(csr, indices=[0], return_predecessors=True)
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: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB_list = []
dist_list = [-1] * N
dist_list[0] = 0
pre_list = []
for _ in range(M):
    a, b = [int(i)-1 for i in input().split()]
    AB_list.append([a, b])
    if a == 0:
        dist_list[b] = 0
        pre_list.append(b)
    elif b == 0:
        dist_list[a] = 0
        pre_list.append(a)

while True:
    tmp = []
    for a, b in AB_list:
        for p in pre_list:
            if a == p and dist_list[b] == -1:
                dist_list[b] = a
                tmp.append(b)
            if b == p and dist_list[a] == -1:
                dist_list[a] = b
                tmp.append(a)
    if tmp == []:
        break

if -1 in dist_list:
    print('No')
    
print('Yes')
for dist in dist_list[1:]:
    print(dist+1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    import math
    def input():
        return sys.stdin.readline()[:-1]
    N,M=map(int,input().split())
    A=[list(map(int,input().split())) for _ in range(M)]
    answer=[0]*(N-1)
    
    i=1
    l=A
    nexti=[1]
    inLoop=True
    while inLoop:

        for i in nexti:
            nexti.remove(i)
            j_root=[x for x in l if i in x]
            for y in j_root:
                if y[0]==i:
                    j=y[1]
                else:
                    j=y[0]
                if answer[j-2]==0:
                    answer[j-2]=i
                l.remove(y)
                nexti.append(j)
            if 0 not in answer:
                inLoop=False        
    print("Yes")
    for k in answer:
        print(k)        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
arr = [list(map(int,input().split())) for i in range(m)]
costheya = {i:[9999999,0] for i in range(2,n+1)}
arr.sort()

for turo in arr:
    left = turo[0]
    right = turo[1]
    if left == 1:
        costheya[right] = [1,1]
    elif right == 1:
        costheya[left] = [1,1]
    else:
        if costheya[left][0] > costheya[right][0]+1:
            costheya[left] = [costheya[right][0]+1,right]
        if costheya[right][0] > costheya[left][0]+1:
            costheya[right] = [costheya[left][0]+1,left]
arr.reverse()
for turo in arr:
    left = turo[0]
    right = turo[1]
    if left == 1:
        costheya[right] = [1,1]
    elif right == 1:
        costheya[left] = [1,1]
    else:
        if costheya[left][0] > costheya[right][0]+1:
            costheya[left] = [costheya[right][0]+1,right]
        if costheya[right][0] > costheya[left][0]+1:
            costheya[right] = [costheya[left][0]+1,left]
    
for i in costheya.values():
    if i[0] == 9999999:
        print('No')
        exit()

print('Yes')
for i in costheya.values():
    print(i[1])

Submission status: Wrong Answer

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

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

for i in range(m):
    chizu[ab[i][0]].append(ab[i][1])
    chizu[ab[i][1]].append(ab[i][0])

kaisu=[chizu[1]]
for i in chizu[1]:
    ans[i]=1

error=0
j=-1
counter=len(chizu[1])
while True:
    j+=1
    if len(kaisu)<=j:
        error=1
        break
    for now in kaisu[j]:#スタートからj+1距離の点たちについて操作
        kari=[]
        for i in chizu[now]:#ある点から隣り合う点決めていく
           if ans[i]==0:#未到達であれば
                ans[i]=now
                kari.append(i)
                counter+=1
        kaisu.append(kari)
    if counter==n-1:
        break

if error==0:
    print("Yes")
    for i in range(2,n+1):
        print(ans[i])
    

elif error==1:
    print("No")

Submission status: Wrong Answer

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

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

ans = []
for l in range(1, n):
  que = [path[l]]
  count = 0
  flag = True
  while(flag):
    tmp = que.pop(0)
    count+=1
    t = []
    for i in tmp:
      if i == 0:
        flag = False
        break
      else:
        for k in path[i]:
          t.append(k)
      que.append(t)
  ans.append(count)

print("Yes")
for i in ans:
  print(i)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import math

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]

hist= []
visited_pos = [-1] * n

#初期情報
#print(ab)
ts = {}
for el in ab:
  wk = ts.get(el[0]) 
  if wk is None:
    sss  = set()
    ts[el[0]] = sss
  ts[el[0]].add(el[1])
  wk = ts.get(el[1]) 
  if wk is None:
    sss  = set()
    ts[el[1]] = sss
  ts[el[1]].add(el[0])
#print(ts)


#幅優先探索
def tsk(pos):
  wk = ts.get(pos)
  if ts.get(pos) is None:
    return
  else:
    #print(wk)
    for e in wk:
      if visited_pos[e-1] < 0:
        visited_pos[e-1] = pos
        hist.append(e)

idx = 1
hist.append(1)
while True:
  if idx > len(hist):
    break
  else:
    tsk(idx)
    idx += 1
#print(hist)
#print(visited_pos)
ans = 'Yes'
for i in range(n):
  if visited_pos[i] < - 1:
    ans = 'No'
    break

print(ans)
if ans == 'Yes':
  for i in range(1,n):
    print(visited_pos[i])

Submission status: Wrong Answer

Solution code:
inf = 10**5+1
n,m = map(int,input().split())
p = [inf]*n
AA = [0]*m
BB = [0]*m
for i in range(m):
  a,b = map(int,input().split())
  A = max(a,b)
  B = min(a,b)
  AA[i] = A
  BB[i] = B
for i in range(len(AA)):
  if p[AA[i]-1] > BB[i]:
    p[AA[i]-1] = BB[i]
  if p[BB[i]-1] > AA[i]:
    p[BB[i]-1] = AA[i]
p[0] = 'Yes'

if max(p[1:]) == 10**5+1:
  print('No')
else:
  for i in range(len(p)):
    print(p[i])

Submission status: Wrong Answer

Solution code:
#D

from collections import defaultdict
CH = defaultdict(list)

N, M = map(int, input().split())
P = [[] for _ in range(N)]
ans = [0] * (N-1)

for _ in range(M):
  A, B = map(int, input().split())
  P[A-1].append(B)
  P[B-1].append(A)

#print(P)

def bfs(s):
    d = [-1] * N
    d[s] = 0
    q = [1]
    c = 1
    while q:
        q1 = []
        for i in q:
            for j in P[i-1]:
                if d[j-1] == -1:
                    d[j-1] = c
                    q1.append(j)
        q = q1
        c += 1
    return d

b = bfs(0)
#print(b)

for i in range(len(b)):
  CH[b[i]].append(i+1)

for i in range(1, N):
  if len(set(CH[ b[i] - 1 ] + P[i])) == 0:
    continue
  else:
    ans[i-1] += list(set(CH[ b[i] - 1 ] + P[i]))[0]

if min(ans) == 0:
  print("No")
else:
  print("Yes")
  for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
def dij(s,n,m,cost):
    d = [float("inf")] * n
    used = [False]*n
    d[s] = 0
    
    while True:
        v = -1
        
        for i in range(n):
            if (not used[i]) and (v ==-1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        
        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
    return d

cost = [[float("inf") for i in range(n)] for i in range(n)] 
for i in range(m):
    x,y = map(int,input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
#print(cost)
sa = dij(0,n,m,cost)
#print(sa)
if float("inf") in sa:
    print("No")
else:
    print("Yes")

    for i in range(1, n):
        print(sa[i])

Submission status: Wrong Answer

Solution code:
import math


n, m = list(map(int, input().split()))
a = []
b = []
g = {1: (None, 0)}
for i in range(2, n + 1):
    g.update({i: (None, math.inf)})

def update_g(x, y):
    if g[x][1] >= g[y][1] + 1:
        g.update({x: (y, g[y][1] + 1)})

for _ in range(m):
    ai, bi = list(map(int, input().split()))
    if ai == 1 or bi == 1:
        g.update({max(ai, bi): (1, 1)})
    else:
        update_g(ai, bi)
        update_g(bi, ai)

ok = False
for k, v in g.items():
    if v[0] == 1:
        ok = True
        break

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

Submission status: Wrong Answer

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

import networkx as nx

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


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

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

    paths = nx.predecessor(G, 1)

    print(YES)

    ans_list = []
    for key, val in paths.items():
        if key != 1:
            print(val[0])
            # ans_list.append((key,val[0]))

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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

ki = [[] for _ in range(n)]

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

# print(ki)

q = deque([0])
seen = [0] * n
ans = [-1] * n
ans[0] = 0
s = 0
while len(q):
    s = q.pop()
    if seen[s] == 0:
        seen[s] = 1

    for i in ki[s]:
        if seen[i]:
            continue
        if seen[i] == 0:
            seen[i] = 1
        ans[i] = s + 1
        q.append(i)

for i in ans:
    if i == -1:
        print('No')
        exit()
print("Yes")
for i in range(1, len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
line1 = input().split()
n = int(line1[0])
m = int(line1[1])

road_map = [[] for i in range(n)]

for i in range(m):
  line = input().split()
  a = int(line[0]) - 1
  b = int(line[1]) - 1
  road_map[a].append(b)
  road_map[b].append(a)
  
current_goal = [0]
route = [-1] * n
none = True
while none:
  goal = current_goal
  current_goal = []
  for i in range(n):
    none = False
    road = road_map[i]
    if route[i] >= 0:
      continue
    dist = -1
    for r in road:
      if r in goal:
        dist = r
    if dist >= 0:
      current_goal.append(i)
      route[i] = dist
      none = True
if min(route) == -1:
  print("No")
else:
  print("Yes")
  for ro in route[1:n]:
    print(ro + 1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

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

nodes = [None]*n

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

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

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

Submission status: Wrong Answer

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

# node:connected
graph = {node:set() for node in range(1,N+1)}

for _ in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].add(B)
    graph[B].add(A)

to_visit = set(range(2,N+1))
current_level = {1}
to_visit = to_visit - current_level
level = 0
levels = {0:{1}}
seen = {1}

while to_visit:
    level += 1
    next_level = set()
    for i in current_level:
        next_level = next_level.union(graph[i] & to_visit)
    
    levels[level] = next_level    
    current_level = next_level
    to_visit = to_visit - current_level

prevs = {}
for level in reversed(range(1,len(levels))):
    for node in levels[level]:
        prevs[node] = set()
        for nbr in graph[node]:
            if nbr in levels[level-1]:
                prevs[node].add(nbr)

# print(prevs)

posts = {1:1}

for level in range(1,len(levels)):
    for node in levels[level]:
        for prev in prevs[node]:
            if prev in posts:
                posts[node] = prev
                break

# print(posts)

for i in range(2, N+1):
    print(posts[i])

Submission status: Wrong Answer

Solution code:
import collections

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
t = [10**18] * N
last = [-1] * N 
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  graph[A].append(B)
  graph[B].append(A)

q = collections.deque([[0, 0]])
count = 0
while q:
  tmp = q.pop()
  pos, time = tmp[0], tmp[1]
  for next_pos in graph[pos]:
    if time+1 < t[next_pos]:
      last[next_pos] = pos
      t[next_pos] = time+1
      q.append([next_pos, time])
print('Yes')
for n in last[1:]:
  print(n+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N, M = [int(i) for i in input().strip().split()]
    pathes = [sorted([int(i) for i in input().strip().split()])
              for _ in range(M)]
    pathes.sort(key=lambda x: x[0])
    ans_table = [[None, float("inf")] for _ in range(N)]
    ans_table[0] = [0, 0]  # next_idx, size to path

    while float("inf") in [dis[1] for dis in ans_table]:
        flag = False
        next_path = []
        for path in pathes:
            next_flag = True
            node_1 = path[0] - 1
            node_2 = path[1] - 1
            if ans_table[node_1][1] != float("inf"):
                cur_dis = ans_table[node_2][1]
                if ans_table[node_1][1] < cur_dis:
                    next_flag = False
                    flag = True
                    ans_table[node_2] = [node_1+1, ans_table[node_1][1] + 1]
            if ans_table[node_2][1] != float("inf"):
                cur_dis = ans_table[node_1][1]
                if ans_table[node_2][1] < cur_dis:
                    next_flag = False
                    flag = True
                    ans_table[node_1] = [node_2 + 1, ans_table[node_2][1] + 1]
            if next_flag:
                next_path.append(path)

        if flag == False:
            break
        pathes = next_path

    if float("inf") in [dis[1] for dis in ans_table]:
        print("No")
        return

    print("Yes")
    for ans in ans_table[1:]:
        print(ans[0])
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

a=[]
for i in range(n-1):
  a.append([])

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

k=[]
k.append(1)
while len(k)>0:
  for i in range(n-1):
    if k[0] in a[i]:
      a[i]=[k[0]]
      k.append(i+2)
  k.pop(0)

print("Yes")
for i in range(n-1):
  print(*a[i])

Submission status: Wrong Answer

Solution code:
print("give up")

Submission status: Wrong Answer

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

import networkx as nx

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


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

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

    paths = nx.predecessor(G, 1)

    print(YES)

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

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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix, coo_matrix
import pprint

N, M = map(int,input().split())
xy = [map(int, input().split()) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

x = list(map(lambda x: x - 1, x))
y = list(map(lambda x: x - 1, y))

X = x + y
Y = y + x

value = np.ones(len(X))
row = np.array(X)
col = np.array(Y)

A = coo_matrix((value,(row,col)))
A = csr_matrix(A)


d, p = shortest_path(A, return_predecessors=True, indices=0)


if -9999 in p[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(p[i] + 1)

Submission status: Wrong Answer

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

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]

n, m = map(int,input().split())
p = [list(map(int,input().split())) for i in range(m)]

#n-1本の道で、全ての場所から辿り着けるか
for v in itertools.combinations(p, n-1):
    l = [[0]*n for i in range(n)]
    for pi in v:
        l[pi[0]-1][pi[1]-1] = 1
        l[pi[1]-1][pi[0]-1] = 1
    l = np.array(l)
    d, p = shortest_path(l, return_predecessors=True)

    x = []
    for i in range(1,n):
        x.append(get_path(0, i, p))
    print(x)
    if x.count([]) == 0:
        print("Yes")
        ans = d[0][1:]
        for i in ans:
            print(int(i))
        exit()

print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
#print(AB)
if N>M:
    print("No")
    exit()
#for i in range(M):
#    if AB[i][0]>AB[i][1]:
#        tmp=AB[i][1]
#        AB[i][1]=AB[i][0]
#        AB[i][0]=tmp
l=[0]*(N-1)
#print(AB)
#AB.sort()
#print(AB)
bo=[1]
box=deque(bo)
count=0
while count<N-1:
    for i in range(M):
        if AB[i][0]==box[0] and l[AB[i][1]-2]==0:
        #if AB[i][0]==box[0]:
            box.append(AB[i][1])
            l[AB[i][1]-2]=AB[i][0]
            count+=1
        elif AB[i][1]==box[0] and l[AB[i][0]-2]==0:
        #elif AB[i][1]==box[0] and l[AB[i][0]-2]==0:
            box.append(AB[i][0])
            l[AB[i][0]-2]=AB[i][1]
            count+=1
    box.popleft()
    #print(box,count)
#print(l,count)
print("Yes")
[print(i) for i in l]

Submission status: Wrong Answer

Solution code:
import queue

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

parent = [-1] * (n-1)
visit = ["yet"]*(n)
visit[0] = "done"
q = queue.Queue()
q.put(1)
while -1 in parent:
    temp = q.get()
    for i in routs[temp]:
        if visit[i-1] == "yet":
            q.put(i)
            if parent[i-2] == -1:
                parent[i-2] = temp
            visit[i-1] = "done"
    print("a")

print("Yes")
for i in parent:
    print(i)

Submission status: Wrong Answer

Solution code:
ans = {}
def main():
    ans = {}
    n, m = input_list()
    rooms = {}
    ll = [False] * (n - 1)
    for _ in range(m):
        a, b = list(sorted(input_list()))
        if a == 1:
            ans[b] = a
            ll[b-2] = True
        if a in rooms:
            rooms[a].append(b)
        else:
            rooms[a] = [b]
        if b in rooms:
            rooms[b].append(a)
        else:
            rooms[b] = [a]
    if 1 not in rooms:
        print('No')
        exit()

    ans.update(dfs(rooms, rooms[1]))
    ans = dict(sorted(ans.items(), key=lambda x: x[0]))
    if len(ans) != n-1:
        print('No')
        exit()
    print('Yes')
    for r, a in ans.items():
        print(a)

def dfs(rooms, goals):
    for r, path in rooms.items():
        if r == 1:
            continue
        if 1 in path:
            ans[r] = 1
            continue
        g = set(path) & set(goals)
        if len(g) > 0:
            ans[r] = list(g)[0]
    return ans

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def dijkstra(g,node_count,start_index):
    INF = 10**9+7
    node = [INF] * node_count
    conf = [0] * node_count
    root = [-1] * node_count

    node[start_index] = 0
    while sum(conf) < node_count:
        change = False
        min_node_dex = -1
        min_node_val = INF
        for i in range(node_count):
            if conf[i] == 0:
                if node[i] < min_node_val:
                    min_node_val = node[i]
                    min_node_dex = i
        conf[min_node_dex] = 1
        for i in range(node_count):
            if conf[i] == 0:
                if g[min_node_dex][i] > 0:
                    new_dist = node[min_node_dex] + g[min_node_dex][i]
                    if new_dist < node[i]:
                        node[i] = new_dist
                        root[i] = min_node_dex
                        change = True

        if not change:
            break

    return root


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

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

#c = dijkstra_heapq(g,n,0)
#print(c)
c = dijkstra(g,n,0)

#c = np.array(c) + 1
#print(c)
ans = []
for i in range(1,n):
    if c[i] >= 0:
        ans.append(c[i]+1)
    else:
        print('No')
        exit()

print('Yes')
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
#import sys
from collections import deque
N, M = map(int, input().split())
p = [0]
ans = [-1]
D = deque()
for i in range(N):
    p.append(list())
    if i == 0:
        ans.append(0)
    else:
        ans.append(-1)
for i in range(M):
    A, B = map(int, input().split())
    p[A].append(B)
    p[B].append(A)
#for i in range(1, N+1):
#    if len(p[i]) == 0:
#        print('No')
#        sys.exit()
D.append(1)
while len(D) != 0:
    ind = D.pop()
    for i in p[ind]:
        if ans[i] == -1:
            D.append(i)
            ans[i] = ind
    if -1 not in ans[2:]:
        break
if -1 in ans[2:]:
    print('No')
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Submission status: Wrong Answer

Solution code:
import numpy

inp=input().split(" ")

n=int(inp[0])
m=int(inp[1])
array=numpy.zeros(m*2,dtype=">i4")

for i in range(m):
  a=(input().split(" "))
  array[2*i]=(int(a[0]))
  array[2*i+1]=(int(a[1]))

ans=numpy.ones(n-1,dtype=">i4")
ans*=-1
nums=[]
next=[-1]
where=numpy.where(array==1)[0]
while len(next)!=0:
    remcount=0
    for i in where:
        i=i-remcount
        if (i%2)==1:
          if array[i-1] not in nums:
            next.append(array[i-1])
            nums.append(array[i-1])
            ans[array[i-1]-2]=array[i]
            array=numpy.delete(array,i-1)
            array=numpy.delete(array,i-1)
        else:
          if array[i+1] not in nums:
            next.append(array[i+1])
            nums.append(array[i+1])
            ans[array[i+1]-2]=array[i]
            array=numpy.delete(array,i)
            array=numpy.delete(array,i)
        if len(next)==0:
          break
        remcount+=2
    where=numpy.where(array==next[0])[0]
    next.pop(0)

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