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:
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:
from collections import deque
def main():
    N,M= map(int, input().split())
    A = [0]*M
    B = [0]*M 
    ans = [-1]*(N+1)
    ans[1] = 0

    L=[]
    [L.append([])for _ in range(N+1)]

    for i in range(M):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    
    q = deque()
    qq = deque()


    for i in range(len(L[1])):
        q.append(L[1][i])
        qq.append(0)

    while len(q) !=0:
        temp = q.popleft()
        tempq = qq.popleft()
        if ans[temp]==-1:
            ans[temp] = tempq + 1
            for i in range(len(L[temp])):
                q.append(L[temp][i])
                qq.append(tempq + 1)

    for i in range(2,N+1):
        if ans[i]==-1:
            print('No')
            return

    print('Yes')

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





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):#要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):#要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):#要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):#要素x, yが同じグループに属するかどうかを返す

        return self.find(x) == self.find(y)

    def members(self, x):#要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):#すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):#グループの数を返す
        return len(self.roots())

    def all_group_members(self):#all_group_members O(N)かかるので注意
        return {r: self.members(r) for r in self.roots()}

uf=UnionFind(n+1)

for i in range(m):
    a=ab[i][0]
    b=ab[i][1]
    if uf.same(a,b)==False:
        uf.union(a,b)

#print(uf.all_group_members())
#print(uf.size(2))
if uf.group_count()!=2:
    print("NO")
    exit()
print("Yes")
ans=[0]*n
for i in range(m):
    if ans[ab[i][0]-1]==0:
        ans[ab[i][0]-1]=ab[i][1]
    if ans[ab[i][1]-1]==0:
        ans[ab[i][1]-1]=ab[i][0]

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

Submission status: Wrong Answer

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

for i in range(M):
    tempA,tempB = map(int, input().split())
    A.append(tempA)
    B.append(tempB)
    tree[tempA - 1] = tree[tempA - 1]+[tempB]
    tree[tempB - 1] = tree[tempB - 1]+[tempA]

answer = ["Yes"]

try:
    for i in range(N):
        for i2,v in enumerate(tree):
            if i + 1 in v:
                answer.append(i2 + 1)
                break
    for i in answer:
        print(i)
except:
    print("No")

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(ans[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

class Cave():
    def __init__(self):
        self.graph = {}
    def add_room(self, r):
        self.graph[r] = []
    def add_passage(self, r1, r2):
        self.graph[r1].append(r2)
        self.graph[r2].append(r1)
    def next_rooms(self, r):
        return self.graph[r]
    def __str__(self):
        return self.graph.__str__()

def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    cave = Cave()
    for i in range(1, N+1):
        cave.add_room(i)
    for r1, r2 in AB:
        cave.add_passage(r1, r2)

    q = deque()
    q.append(1)
    visited = [0]*(N+1)
    visited[1] = -1
    print(1)

    while q:
        r_now = q.popleft()
        for r_next in cave.next_rooms(r_now):
            if visited[r_next] == 0:
                # print(r_next)
                visited[r_next] = r_now
                q.append(r_next)

    print('Yes')
    for i in visited[2:]:
        print(i)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    u[a].append(b)
    u[b].append(a)
l = [0] * (n-1)

for i in range(1, n):
    count = 0
    q = deque([i])
    reach = False
    while reach == False:
        num = len(q)
        print(q)
        for j in range(num):
            p = q.popleft()
            if p == 0:
                reach = True
                l[i-1] = count
                break
            for y in u[p]:
                q.append(y)
        count += 1
    print(count)
    

if sum(l) == 0:
    print('No')
else:
    print('Yes')
    for i in range(n-1):
        print(l[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

ans = [None]*n
not_visited = set(range(n))
not_visited.remove(0)
vs = deque([0])
while vs:
    v = vs.pop()
    for other_v in e[v]:
        if other_v in not_visited:
            vs.append(other_v)
            not_visited.remove(other_v)
            if ans[other_v] is None:
                ans[other_v] = v

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

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    A=[]
    B=[]
    for i in range():
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)'''

    n,m = map(int, input().split())
    r=[[0 for i in range(n)]for i in range(n)]
    start = [0, 0]
    #print(bfs(h, w, m, start))
    for i in range(m):
        a,b=map(int, input().split())
        r[a-1][b-1]=b-1
        r[b-1][a-1]=a-1
    #print(r)
    
    from collections import deque
    d = [0 for i in range(n)]
    visited=[True]+[False for i in range(n-1)]
    flg = True
    queue=deque([0])
    dd=0
    print("Yes")
    while queue:
        now=queue.popleft()
        visited[now]=True
        #print(now)
        for i in r[now]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
                d[i]=now
                print(d[i]+1)

if __name__ == "__main__":
     main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline 
sys.setrecursionlimit(10 ** 6)
N,M = map(int,input().split())
path = [[] for i in range(N)]
inf = 10 ** 6
ans = [[None,inf] for i in range(N - 1)]

for _ in range(M):
  a,b = map(int,input().split())
  a = a - 1
  b = b - 1
  if a > b:
    a,b = b,a
  path[a].append(b)
  path[b].append(a)

print(path)

def dfs(cur,par,con):
  if con == N:
    return
  for chi in path[cur]:
    if chi == par:
      continue
    if con < ans[chi - 1][1]:
      ans[chi - 1][0] = cur
      ans[chi - 1][1] = con + 1
      dfs(chi,cur,con + 1)

dfs(0,-1,0)

if all([i[0] != None for i in ans]):
  print("Yes")
  for i in range(N - 1):
    print(ans[i][0] + 1)
else:
  print("No")

Submission status: Wrong Answer

Solution code:
N , M = map(int , input().split())
A = [ 0 for i in range(M)]
B = [ 0 for i in range(M)]
for i in range(M):
  A[i] , B[i] = map(int , input().split())
 
direction = [N for i in range(N)]
point = [N for i in range(N)]
for i in range(M):
  if A[i] == 1:
    direction[B[i] - 1] = 1
    point[B[i] - 1] = 1
  if B[i] == 1:
    direction[A[i] - 1] = 1
    point[A[i] - 1] = 1
step = 1
k=1
unko = list(range(M))
while k != 0:
  k = 0
 
  for i in unko:
    a = point[A[i] - 1]
    b = point[B[i] - 1]
    m = min([a, b])
    if m == step and a != b:
      if a == m:
        direction[B[i] - 1] = A[i]
        point[B[i] - 1] = m+1
      if b == m:
        direction[A[i] - 1] = B[i]
        point[A[i] - 1] = m+1
      k += 1  
      unko.remove(i)
  step += 1
print('Yes')
for i in range(N - 1):
  print(str(direction[i + 1]))

Submission status: Wrong Answer

Solution code:
n,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: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

N,M = map(int,input().split())
edge = [[10**9 for j in range(N+1)] for i in range(N+1)]

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

G = csgraph_from_dense(edge, null_value=10**9)
d = dijkstra(G,indices = 1)
ck = 0
for i in range(2,len(d)):
  if d[i] == float('inf'):
    ck = 1
if ck == 1:
  print("No")
else:
  print("Yes")
  for i in range(2,len(d)):
    print(int(d[i]))

Submission status: Wrong Answer

Solution code:
import math


n, m = list(map(int, input().split()))
a = []
b = []
g = {1: (1, 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 = True
for k, _ in g.items():
    if k is None:
        ok = False
        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:
n, m = map(int, input().split())
list = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    list[a-1][b-1] = 1
    list[b-1][a-1] = 1
for ll in list:
    if ll == [0]*n:
        print('No')
        break
else:
    print('Yes')
for ll in list:
    for j in range(len(ll)):
        if ll[j] == 1 and ll != list[0]:
            print(j+1)
            continue

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
import copy

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

mydic = {n:[] for n in range(1,N+1)}
#print(mydic)
for m in range(M):
    a, b = map(int, input().split())
    mydic[a] += [b]
    mydic[b] += [a]
#print(mydic)
mydic2 = copy.deepcopy(mydic)
mydp = [0 for n in range(N+1)]
myflag = [0 for n in range(N+1)]
myflag[1] = 1
#print(mydp)
#print(myflag)

d = deque()
d.append(mydic[1])
#print(d)
mycnt = 1
while d:
    mylist = d.pop()
    #mycandi = []
    while mylist:
        mynum = mylist.pop()
        if myflag[mynum] == 0:
            myflag[mynum] = 1
            mydp[mynum] = mycnt
            d.append(mydic[mynum])
            #mycandi += mydic[mynum]
            #print(mycandi)
    #d.append(mycandi)
    #print('d=',d)
    #print(mydp)
    mycnt += 1
#print(mydp)
#print(myflag)
#print(mydic2)

print('Yes')
for n in range(2,N+1):
    mymin = float('INF')
    mynum = 0
    for i in mydic2[n]:
        #print(n,i)
        if mydp[i] < mymin:
            mynum = i
            mymin = mydp[i]
    print(mynum)

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)
  
goal = [0]
route = [-1] * n
none = True
while none:
  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:
      goal.append(i)
      route[i] = dist
      none = True
if len(goal) < n:
  print("No")
else:
  print("Yes")
  for r in route:
    print(r + 1)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
G = [[0]*n for i in range(n)]
dist = [float('inf')]*n
dist[0] = 0
l = []
for i in range(m):
    a, b = map(int, input().split())
    p = min(a-1 ,b-1)
    q = max(a-1, b-1)
    l.append((p, q))
l.sort()
while len(l) != 0:
    a = l.pop(0)
    # print(a)
    # print(dist)
    if dist[a[0]] > dist[a[1]] + 1:
        dist[a[0]] = dist[a[1]] + 1
    if dist[a[1]] > dist[a[0]] + 1:
        dist[a[1]] = dist[a[0]] + 1
#     print(dist)
# print(dist)

if max(dist) == float('inf'):
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(dist[i])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
l = {}
for i in range(M):
    a,b = [int(j) for j in input().split()]
    a -= 1
    b -= 1
    if a in l:
        l[a].append(b)
    else:
        l[a] = [b]
    if b in l:
        l[b].append(a)
    else:
        l[b] = [a]
ans = [10**8] * N

v = {}
num = 0
cnt = 0
def search(idx, num):
    global cnt
    if ans[idx] > num:
        ans[idx] = num
    for i in l[idx]:
        if ans[i] <= num + 1:
            continue 
        if not i in v:
            v[i]=num
            cnt += 1

search(0,0)

for i in range(N-1):
    if cnt == M:
        break
    a = v
    v = {}
    num += 1
    for j in a:
        search(j, num)

ret = []
for i in range(1,N):
    for j in l[i]:
        if ans[j] == ans[i] - 1:
            ret.append(j+1)
            break

if len(ret) == N - 1:
    print("Yes")
    for i in ret:
        print(i)
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# = int(input())
N, M = map(int, input().split())
# = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
AB = [list(map(int, input().split())) for i in range(M)]
sign = [0]*(N-1)
ilist=[]

for i in range(M):
    if AB[i][0] == 1:
         sign[AB[i][1]-2] = 1
         ilist.append(i)
    elif AB[i][1] == 1:
         sign[AB[i][0]-2] = 1
         ilist.append(i)
for i in range(len(ilist)):
    del AB[ilist[i]-i]
ilist = []
length = len(AB)
#for i in range(M):
#    if sign[AB[i][0]-2] == 1 and sign[AB[i][1]-2] != 1:
#        sign[AB[i][1]-2] = AB[i][0]
#    elif sign[AB[i][1]-2] == 1 and sign[AB[i][0]-2] != 1:
#        sign[AB[i][0]-2] = AB[i][1]
for i in range(1000):
    for i in range(length):
        if sign[AB[i][0]-2] != 0 and sign[AB[i][1]-2] == 0:
            sign[AB[i][1]-2] = AB[i][0]
            ilist.append(i)
        elif sign[AB[i][1]-2] != 0 and sign[AB[i][0]-2] == 0:
            sign[AB[i][0]-2] = AB[i][1]
            ilist.append(i)
    for i in range(len(ilist)):
#        print(ilist)
        del AB[ilist[i]-i]
#        print(AB)
    ilist = []
    if len(AB) == length:
        break
    else:
        length = len(AB)
#        print(length)

if sign.count(0) > 0:
    print("No")
else:
    print("Yes")
    for number in sign:
        print(number)

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)
        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 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:
n,m = map(int, input().split(" "))
mlist = [[]]*(n+1)
dp = [0]*n
dp[0] =  1

for i in range(m):
  a,b = map(int, input().split(" "))
  newlist=[]
  for i in mlist[a]:
    newlist.append(i)
  newlist.append(b)
  mlist[a]=newlist
  newlist=[]
  for i in mlist[b]:
    newlist.append(i)
  newlist.append(a)
  mlist[b]=newlist

k = [1]
while 0 in dp:
  for i in k:
    for l in mlist[i]:
      if dp[l-1]==0:
        dp[l-1]=i
        k.append(l)
    k.remove(i)
print("yes")
for i in dp[1:n]:
  print(i)

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]

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]
    

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

Submission status: Wrong Answer

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

def bfs(start):
    queue = deque()
    visited = [False] * n
    visited[start-1] = True
    queue.append(start)
    while queue:
        target = queue.popleft()
        print(target)
        for i in g[target]:
            if not visited[i-1]:
                ans[i-2] = target
                visited[i-1] = True
                queue.append(i)

ans = [0] * (n-1)
g = dict()
for a, b in AB:
    if a in g:
        g[a].append(b)
    if b in g:
        g[b].append(a)
    if a not in g:
        g[a] = [b]
    if b not in g:
        g[b] = [a]
start = 1
bfs(start)
if len([i for i in ans if i == 0]) == 0:
    print("Yes")
    print(*ans, sep="\n")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G =[[]for i in range(N)]
for _ in range(M):
    A,B = map(int,input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
if len(G[0])==0:
    print('No')
else:
    print('Yes')
    for i in range(1,N):
        print(min(G[i])+1)

Submission status: Wrong Answer

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

a=[]
b=[]
for i in range(0,m):
    aa,bb=map(int,input().split())
    a.append(aa)
    b.append(bb)

s=[n+1 for i in range(0,n+1)]
ans=[n+1 for i in range(0,n+1)]
s[1]=0
s2=[[] for i in range(0,n+1)]


for i in range(0,m):
    x=s[a[i]]
    y=s[b[i]]

    if x<y:
        s2[a[i]].append(b[i])
        s[b[i]]=s[a[i]]+1
        ans[b[i]]=a[i]
        while (s2[b[i]]!=[]):
            s[s2[b[i]][0]]=s[a[i]]+2
            s2[b[i]].pop(0)





    elif y<x:
        s2[b[i]].append(a[i])
        s[a[i]]=s[b[i]]+1
        ans[a[i]]=b[i]
        while (s2[a[i]]!=[]):
            s[s2[a[i]][0]]=s[b[i]]+2
            s2[a[i]].pop(0)

    elif (x==n+1 and y==n+1):
        s2[a[i]].append(b[i])
        s2[b[i]].append(a[i])
        ans[b[i]]=a[i]
        ans[a[i]]=b[i]






















print("Yes")
for i in range(2,n+1):
    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())
    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:
from collections import deque

n, m = (int(each) for each in input().split())
paths = []
for each in range(m):
    paths.append(set([int(each) for each in input().split()]))

result = [-1]*(n+1)

queue = deque()
queue.append(1)
while queue:
    start_at = queue.popleft()

    for path in paths:
        if start_at in path:
            neibor = (list(path-{start_at}))[0]
            print(neibor)
            if result[neibor] != -1:
                continue
            result[neibor] = start_at
            queue.append(neibor)

if -1 in result[2:]:
    print('No')
else:
    print('Yes')
    print('\n'.join(str(each) for each in result[2:]))

Submission status: Wrong Answer

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

N = int(N)
M = int(M)

neighbor_dict = {}
wait = {}
done = {}
michisirube_dict = {}

for i in range(N):
	neighbor_dict[i+1] = []
	wait[i+1] = False
	done[i+1] = False
	michisirube_dict[i+1] = None

for i in range(M):

	A, B = input().split(" ")
	A = int(A)
	B = int(B)
	neighbor_dict[A].append(B)
	neighbor_dict[B].append(A)


def set_michisirube(room, neighbors):
	for neighbor in neighbors:
		if michisirube_dict[neighbor] is None:
			michisirube_dict[neighbor] = room
		else:
			pass
	return neighbors



neighbors = set_michisirube(1,neighbor_dict[1])
for neighbor in neighbors:
	set_michisirube(neighbor, neighbor_dict[neighbor])

print("yes")

for i in range(N-1):
	print(michisirube_dict[i+2])

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
import sys
import math
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations, combinations_with_replacement
from itertools import accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil,floor
from copy import deepcopy
from heapq import heappop,heappush,heapify
import heapq


# def combinations(n, r):
# 	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# def gcd(a, b):
# 	if b == 0:
# 		return a
# 	else:
# 		return gcd(b, a%b)
 
# def lcm(a, b):
# 	return a // gcd(a, b) * b

# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))


N,M = MI()
A = []
B = []
for _ in range(M):
	a,b = MI()
	A.append(a)
	B.append(b)

d = defaultdict(int)
ref_list = [''] * N

for aa, bb in zip(A,B):
	ref_list[bb-1] += str(aa)
	ref_list[aa-1] += str(bb)

memo = []

def rec(i, done, num):
	memo.append(int(i))
	if d[str(i)]==0:
		d[str(i)] = num
	else:
		d[str(i)] = min(num, d[str(i)])
	candidate = list(set(ref_list[int(i)-1]))
	candidate = [c for c in candidate if not c in done]
	new_done = done+candidate
	for c in candidate:
		if not c in done and not int(c) in memo:
			rec(c, new_done, num+1)
	return


rec(1, ['1'], 10)

ans = []
for i in range(1,N):
	d_i = d[str(i+1)]
	for target in list(set(ref_list[i])):
		if d[str(target)] == d_i -1:
			ans.append(target)
			break

if len(ans)==N-1:
	print('Yes')
	for f in ans:
		print(f)
else:
	print('No')

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
l = {}
for i in range(M):
    a,b = [int(j) for j in input().split()]
    a -= 1
    b -= 1
    if a in l:
        l[a].append(b)
    else:
        l[a] = [b]
    if b in l:
        l[b].append(a)
    else:
        l[b] = [a]
ans = [10**8] * N

v = {}
num = 0
cnt = 0
def search(idx, num):
    global cnt
    if ans[idx] > num:
        ans[idx] = num
    for i in l[idx]:
        if ans[i] < num + 1:
            continue 
        if not i in v:
            v[i]=num
            cnt += 1

search(0,0)

for i in range(N-1):
    if cnt == M:
        break
    a = v
    v = {}
    num += 1
    for j in a:
        search(j, num)

ret = []
for i in range(1,N):
    for j in l[i]:
        if ans[j] == ans[i] - 1:
            ret.append(j+1)
            break

if len(ret) == N - 1:
    print("Yes")
    for i in ret:
        print(i)
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
miti = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    miti[A-1].append(B-1)
    miti[B-1].append(A-1)

ans = [0] * (N-1)
kyori = [10 ** 6] * N
kyori[0] = 0
for i in range(N):
    tmp_kyori = kyori[i]
    tmp_lis = miti[i]
    for x in tmp_lis:
        if tmp_kyori + 1 < kyori[x] :
            kyori[x] = tmp_kyori + 1
            ans[x-1] = i + 1
print('Yes')
for i in range(N-1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
way = [list(map(lambda x: int(x) -1, input().split())) for _ in range(m)]
for i in range(m):
    if way[i][0] > way[i][1]:
        way[i][0],way[i][1] = way[i][1],way[i][0]
way = sorted(way, key = lambda x: x[0]*10**6+x[1])
dist = [n+1]*n
dist[0] = 0
ans = [n]*n
ans[0] = 0
for a,b in way:
    if dist[b] > dist[a]+1:
        dist[b] = dist[a]+1
        ans[b] = a+1
    elif dist[a] > dist[b]+1:
        dist[a] = dist[b]+1
        ans[a] = b+1
if n+1 in dist:
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i])