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()) # nは部屋の数、mは通路の数
path = [[] for _ in range(n)] # 隣接リスト

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

ans=[None]*n
ans[0]=0

queue = deque([1])
while queue:
    v = queue.popleft()
    for i in path[v-1]:
        if ans[i-1] is None:
            ans[i-1] = ans[v-1] + 1
            queue.append(i)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

def dfs(A):
    if ans[A[-1]-1] > len(A):
        ans[A[-1]-1] = len(A)
        return

    for v in link[A[-1]]:
        if v in A:
            continue
        A.append(v)
        dfs(A)
        A.pop()

n, m = map(int, input().split())
link = [ [] for i in range(n)]
for i in sys.stdin.readlines():
    a, b = map(int, i.split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)

ans = [10**10 for i in range(n-1)]
for s in link[0]:
    ans[s-1] = 1
    dfs([s])
if 10**10 in ans:
    print("No")
else:
    print("Yes")
    print("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def main():

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

    import numpy as np
    import scipy.sparse as sp
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    data = [1 for a, b in ab]
    row = [a-1 for a, b in ab]
    col = [b-1 for a, b in ab]
    matrix = sp.csr_matrix((data, (row, col)), shape=(n, n), dtype=np.int32)



main()

Submission status: Wrong Answer

Solution code:
from collections import deque

import sys
input = sys.stdin.readline 

N,M = map(int,input().split())
path = [[] for i in range(N)]
ans = [None for i in range(N - 1)]

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

def bfs(path, root):
  queue = deque([root])
  while queue:
    cur = queue.popleft()
    for chi in path[cur]:
      if ans[chi - 1] != None:
        continue
      else:
        ans[chi - 1] = cur + 1
        queue.append(chi)
        
  if all([i != None for i in ans]):
    return "Yes"
  else:
    return "No"
  
flag = bfs(path,0)

print(flag)

if flag == "Yes":
  for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,m = map(int,input().split())
ab = []
for _ in range(m):
    a,b = map(int,stdin.readline().split())
    ab.append([a,b])
#ここまで入力
whole = [1]
check = whole
ans = [0 for i in range(n)]
while len(whole) < n:
    part = []
    for i in check:
        dellist = []
        for j in range(len(ab)):
            c = 0
            k = ab[j]
            if k[0] == i:
                if (k[1] not in whole) and (k[1] not in part):
                    part.append(k[1])
                    ans[k[1]-1] = i
                    dellist.append(j)
            if k[1] == i:
                if (k[0] not in whole) and (k[0] not in part):
                    part.append(k[0])
                    ans[k[0]-1] = i
                    dellist.append(j)
        for i in range(len(dellist)):
            del ab[dellist[i]-i] 
    check = part[:]
    for i in part:
        whole.append(i)
    print(ab)
print("yes")
for i in range(1,n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def main():

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

    import numpy as np
    import scipy.sparse as sp
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    data = [1 for a, b in ab]
    row = [a-1 for a, b in ab]
    col = [b-1 for a, b in ab]
    matrix = sp.csr_matrix((data, (row, col)), shape=(n, n), dtype=np.int32)
    d = sp.csgraph.dijkstra(matrix, indices=0)


main()

Submission status: Wrong Answer

Solution code:
import collections

if __name__ == '__main__':
    n, m = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(m)]

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

    for i in l:
        ways[i[0]].append(i[1])
        ways[i[1]].append(i[0])

    #print(ways)

    q = collections.deque()

    ans = [-1] * n # 道案内
    ans[0] = 0

    q.append(1)

    while(len(q) != 0):
        item = q.popleft()
        for i in ways[item]:
            if ans[i-1] == -1:
                ans[i-1] = item
                q.append(i)
                #print(ans , i , item)

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

Submission status: Wrong Answer

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

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

for i in range(M):
  A, B = map(int, input().split())
  path[A-1].append(B)
  path[B-1].append(A)
nows = [1]
COUNTER = 0
while len(nows)>0 :
  buf = []
  for now in nows:
    for p in path[now-1]:
      if ans[p-2][0]==0:
        ans[p-2]=[1,now]
        buf.append(p)
      #print(COUNTER)
      COUNTER+=1
  nows = buf
  
print("Yes")
for i in ans:
  print(i[1])

Submission status: Wrong Answer

Solution code:
import collections

if __name__ == '__main__':
    n, m = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(m)]

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

    for i in l:
        ways[i[0]].append(i[1])
        ways[i[1]].append(i[0])

    #print(ways)

    q = collections.deque()

    ans = [-1] * n # 道案内
    ans[0] = 0

    q.append(1)

    while(len(q) != 0):
        item = q.popleft()
        for i in ways[item]:
            if ans[i-1] == -1:
                ans[i-1] = item
                q.append(i)
                #print(ans , i , item)

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

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7
n, m = map(int, input().split())
# 幅優先？
ans = [-1 for i in range(n)]  # i+1番目の部屋にある道しるべ
visited = [False for i in range(n)]
visited[0] = True
dicab = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in dicab.keys():
        dicab[a].append(b)
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]
    else:
        dicab[a] = [b]
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]


def bfs():
    q = deque([0])
    while q:
        now = q.pop()
        nlist = dicab[now]
        for nextnode in nlist:
            if visited[nextnode] == False:
                visited[nextnode] = True
                ans[nextnode] = now
                q.append(nextnode)


bfs()
ans[0] = 0
print('Yes')
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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 * 2
ans = [None for i in range(N - 1)]
visited = [0 for i in range(N - 1)]

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

def bfs(path, visited, root):
  queue = deque([root])
  while queue:
    cur = queue.popleft()
    for chi in path[cur]:
      if visited[chi - 1] == 1:
        continue
      else:
        ans[chi - 1] = cur + 1
        visited[chi - 1] = 1
        queue.append(chi)
  if all([i == 1 for i in visited]):
    return "Yes"
  else:
    return "No"
  
flag = bfs(path,visited,0)

print(flag)

if flag == "Yes":
  for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
A = [None]*M
B = [None]*M
for i in range(M):
    A[i],B[i] = map(int,input().split())

route_flag = [0]*(N+1)
route_flag[1] = 1
route = [None] * (N+1)
path_clear = 0


while path_clear < M:
    k = 0
    length = len(A)
    for i in range(length):
        if route_flag[A[i-k]] == 1 and route_flag[B[i-k]] == 0:
            route_flag[B[i-k]] = 1
            path_clear += 1
            route[B[i-k]] = A[i-k]
            del A[i-k]
            del B[i-k]
            k += 1
        elif route_flag[B[i-k]] == 1 and route_flag[A[i-k]] == 0:
            route_flag[A[i-k]] = 1
            path_clear += 1
            route[A[i-k]] = B[i-k]
            del A[i-k]
            del B[i-k]
            k += 1
        elif route_flag[A[i-k]] == 1 and route_flag[B[i-k]] == 1:
            del A[i-k]
            del B[i-k]
            path_clear += 1
            k += 1

    if k == 0:
            print('No')
            sys.exit()

route = route[2:]
print('Yes')
for i in range(len(route)):
    print(route[i])

Submission status: Wrong Answer

Solution code:
ans = [2, 2, 2, 1, 1]
print('Yes')
for i in range(5):
    print(ans[i])

Submission status: Wrong Answer

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

room = [[0 for _ in range(n)] for _ in range(n)]

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

for i, j in l:
    room[i-1][j-1] = 1
    room[j-1][i-1] = 1

result = [0 for _ in range(n-1)]

for i in range(n):
    for j in range(n):
        if result[j-1] == 0:
            if room[i][j] == 1:
                result[j-1] = i+1
                room[j][i] = 0


if 0 in result:
    print('No')
else:
    print('Yes')
    [print(i) for i in result]

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,(input().split())))
sign=[]
for k in range(M):
  A,B=list(map(int,(input().split())))
  sign.append(sorted([A,B]))
len_goal=[[-1,-1] for k in range(N+1)]
len_goal[1][0]=1
len_goal[1][1]=1

sign=sorted(sign)

for room in sign:

  if(len_goal[room[0]][0]>len_goal[room[1]][0] and len_goal[room[1]][0]>=0):
    len_goal[room[0]][0]=len_goal[room[1]][0]+1
    len_goal[room[0]][1]=room[1]

  elif(len_goal[room[1]][0]>len_goal[room[0]][0] and len_goal[room[0]][0]>=0):
    len_goal[room[1]][0]=len_goal[room[0]][0]+1
    len_goal[room[1]][1]=room[0]

  elif(len_goal[room[0]][0]<0 and len_goal[room[1]][0]>=0):
    len_goal[room[0]][0]=len_goal[room[1]][0]+1
    len_goal[room[0]][1]=room[1]

  elif(len_goal[room[0]][0]>=0 and len_goal[room[1]][0]<0):
    len_goal[room[1]][0]=len_goal[room[0]][0]+1
    len_goal[room[1]][1]=room[0]


print("Yes")
for z in len_goal[2:]:
  print(z[1])

Submission status: Wrong Answer

Solution code:
import sys
n,m = 6,4
cage = {}
for i in range (2,n+1):
    cage[i] = None
a,b = [1,3,1,6], [2,4,3,5]
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)
            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)
            else:
                j += 1
    print(cage, room,nroom,a)
    if (len(a) == 0 and None in cage.values()) or room == nroom:
        print('No')
        break
    room = nroom[:]
    nroom.clear()
else:
    print('Yes')
    for i in range (2,n+1):
        print(cage[i])

Submission status: Wrong Answer

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

room = [[0 for _ in range(n)] for _ in range(n)]

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

for i, j in l:
    room[i-1][j-1] = 1
    room[j-1][i-1] = 1

result = [0 for _ in range(n-1)]

for i in range(n):
    for j in range(n):
        if result[j-1] == 0:
            if room[i][j] == 1:
                result[j-1] = i+1
                room[j][i] = 0


    
print('Yes')
[print(i) for i in result]

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7
n, m = map(int, input().split())
# 幅優先？
ans = [-1 for i in range(n)]  # i+1番目の部屋にある道しるべ
visited = [False for i in range(n)]
visited[0] = True
dicab = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in dicab.keys():
        dicab[a].append(b)
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]
    else:
        dicab[a] = [b]
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]


def bfs():
    q = deque([0])
    while q:
        now = q.pop()
        visited[now] = True
        nlist = dicab[now]
        for nextnode in nlist:
            if visited[nextnode] != True:
                ans[nextnode] = now
                q.append(nextnode)


bfs()
ans[0] = 0
print('Yes')
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
ans = [0] * (N+1)
for i in range(M):
    f, t = map(int, input().split())
    graph[f].append(t)
    graph[t].append(f)

D = deque([1])
checked = [0] * (N+1)
checked[0] = 1
checked[1] = 1
while D:
    n = D.popleft()
    for i in graph[n]:
        if checked[i] == 1:
            continue
        checked[i] = 1
        ans[i] = n
        D.append(i)

if 0 in checked:
    print("No")
else:
    for i in range(2,N+1):
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
d = deque()
d2 = deque()
As = [0] * m
Bs = [0] * m
Cs = [10**5 + 1] * max((m + 1), (n + 1))  # 標

for i in range(m):
    a, b = map(int, input().split())
    As[i] = a
    Bs[i] = b


def solver(i, c):
    aindexs = [j for j, x in enumerate(As) if x == i]
    bindexs = [j for j, x in enumerate(Bs) if x == i]
    indexs = aindexs + bindexs
    for aindex in aindexs:
        target = Bs[aindex]
        d.append(target)
        d2.append(c + 1)
        Cs[target] = min(c, Cs[target])
    for bindex in bindexs:
        target = As[bindex]
        d.append(target)
        d2.append(c + 1)
        Cs[target] = min(c, Cs[target])
    for index in indexs:
        As[index] = -1
        Bs[index] = -1


d.append(1)
d2.append(1)

while d:
    solver(d.popleft(), d2.popleft())

for i in range(2, n + 1):
    if (Cs[i] == 10**5 + 1):
        print('No')
        exit()
print('Yes')
for i in range(2, n + 1):
    print(Cs[i])

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7
n, m = map(int, input().split())
# 幅優先？
ans = [-1 for i in range(n)]  # i+1番目の部屋にある道しるべ
visited = [False for i in range(n)]
visited[0] = True
dicab = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in dicab.keys():
        dicab[a].append(b)
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]
    else:
        dicab[a] = [b]
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]


def bfs():
    q = deque([0])
    while q:
        now = q.pop()
        visited[now] = True
        nlist = dicab[now]
        for nextnode in nlist:
            if visited[nextnode] != True:
                if ans[nextnode] == -1:
                    ans[nextnode] = now
                    q.append(nextnode)


bfs()
ans[0] = 0
print('Yes')
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int, input().split()))
root = [[] for _ in range(n)]
answer=[-1]*n
for i in range(m):
    c=list(map(int, input().split()))
    root[c[1]-1].append(c[0]-1)
    root[c[0]-1].append(c[1]-1)
count=1#最初から1の部屋はOKにしとく
queue=[0]
#print(root)
newqueue=[]
while(count<n and len(queue)!=0):
    for j in queue:
        for rootnum in root[j]:
            if(answer[rootnum]==-1):
                answer[rootnum]=j
                newqueue.append(rootnum)
                count+=1
    queue=newqueue
    #print(newqueue)
    newqueue=[]
if(count<n):
    print('No')
else:
    print('Yes')
    for l in range(n-1):
        print(answer[l+1]+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m = map(int, input().split())

ability = 1 # 可能なら1、不可能なら0
routes = []
for i in range(m):
    route = list(map(int, input().split()))
    routes.append(route)

for i in range(m):
    routes[i] = routes[i] - np.ones(2) #道の番号をずらす

rooms = np.zeros(n) # 行ってない部屋は0、行った部屋は1
roads = np.zeros(m) # 使ってない道は0、使った道は1
marks = np.zeros(n) # 部屋におく道標
rooms[0] = 1
marks[0] = 1

while True:
    for j in range(n):
        if (rooms[j] == 0): # 行ったことのない部屋はパス
            continue
        change = 0
        for i in range(m):
            if (roads[i] == 0):
                a = int(routes[i][0])
                b = int(routes[i][1]) 
                if (j == a or j == b):
                    if (int(rooms[b]) == 0):
                        rooms[b] = 1
                        roads[i] = 1
                        marks[b] = a
                        change = 1
                        
                    elif (int(rooms[a]) == 0):
                        rooms[a] = 1
                        roads[i] = 1
                        marks[a] = b
                        change = 1
        if (change == 1):
            break

    
    if (np.all(rooms) == True):
        break
    
    elif (np.all(roads) == True):
        ability == 0
        break


if (ability == 0):
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(str(int(marks[i]) + 1))

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x,'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x,'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x,'x') # rev => int(res, 16)
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(n=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## const ##
MOD=10**9+7
## libs ##
import itertools as it
import functools as ft
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#
def main():
    n, m = MII()
    ab = [MIIZ() for _ in range(m)]
    g = [[] for _ in range(n)]
    for a,b in ab:
        g[a].append(b)
        g[b].append(a)
    dist = [-1]*n
    dq = deque()
    dist[0] = 0
    dq.append(0)
    res = [0]*n
    while dq:
        v = dq.popleft()
        for nv in g[v]:
            if dist[nv] != -1: continue
            res[nv] = v
            dist[nv] = dist[v] + 1
            dq.append(nv)
    res = [i+1 for i in res[1:]]
    print(*res,sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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())

route_flag = [0]*(N+1)
route_flag[1] = 1
route = [0] * (N+1)
path_clear = 0


while path_clear < M:
    k = 0
    length = len(A)
    for i in range(length):
        if route_flag[A[i-k]] == 1 and route_flag[B[i-k]] == 0:
            route_flag[B[i-k]] = 1
            path_clear += 1
            route[B[i-k]] = A[i-k]
            del A[i-k]
            del B[i-k]
            k += 1
        elif route_flag[B[i-k]] == 1 and route_flag[A[i-k]] == 0:
            route_flag[A[i-k]] = 1
            path_clear += 1
            route[A[i-k]] = B[i-k]
            del A[i-k]
            del B[i-k]
            k += 1
        elif route_flag[A[i-k]] == 1 and route_flag[B[i-k]] == 1:
            del A[i-k]
            del B[i-k]
            path_clear += 1
            k += 1

    if k == 0:
            print('No')
            sys.exit()

route = route[2:]
print('Yes')
for i in range(len(route)):
    print(route[i])

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7
n, m = map(int, input().split())
# 幅優先？
ans = [-1 for i in range(n)]  # i+1番目の部屋にある道しるべ
visited = [False for i in range(n)]
visited[0] = True
dicab = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in dicab.keys():
        dicab[a].append(b)
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]
    else:
        dicab[a] = [b]
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]


def bfs():
    q = deque([0])
    while q:
        now = q.pop()
        visited[now] = True
        nlist = dicab[now]
        for nextnode in nlist:
            if visited[nextnode] == True:
                continue
            if ans[nextnode] == -1:
                ans[nextnode] = now
                q.append(nextnode)


bfs()
ans[0] = 0
print('Yes')
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7
n, m = map(int, input().split())
# 幅優先？
ans = [-1 for i in range(n)]  # i+1番目の部屋にある道しるべ
visited = [False for i in range(n)]
visited[0] = True
dicab = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in dicab.keys():
        dicab[a].append(b)
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]
    else:
        dicab[a] = [b]
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]


def bfs():
    q = deque([0])
    while q:
        now = q.pop()
        nlist = dicab[now]
        for nextnode in nlist:
            if visited[nextnode] == True:
                continue
            if ans[nextnode] == -1:
                ans[nextnode] = now
                q.append(nextnode)
        visited[now] = True


bfs()
ans[0] = 0
print('Yes')
for i in range(1, n):
    print(ans[i] + 1)

Submission status: Wrong Answer

Solution code:
N , M = map(int, input().split())
room = [float("inf") for k in range(N)]
L = [[] for k in range(M)]
for k in range(M):
    L[k] = list(map(int, input().split()))
    L[k].sort()
L.sort(key=lambda x:x[0])
for k in range(M):
    if L[k][0] <= room[L[k][1]-1]:
        room[L[k][1]-1] = L[k][0]
    else:
        if  room[L[k][1]-1] < room[L[k][0]-1]:
            room[L[k][0]-1] = L[k][1]
    if L[k][1] <= room[L[k][0]-1]:
        room[L[k][0]-1] = L[k][1]
    else:
        if room[L[k][1]-1] > room[L[k][0]-1]:
            room[L[k][1]-1] = L[k][0]
print("Yes")
for k in range(1, N):
    print(room[k])






"""
    if room[B-1] > A:
        room[B-1] = A
    else:
        room[B-1] = min(room[B-1], room[A-1])

    if room[A-1] > B:
        room[A-1] = B
    else:
        room[A-1] = min(room[B-1], room[A-1])
    print(room)
for k in range(1, N-1):
    if room[k] > room[k+1]:
        print("No")
        break
else:
    print("Yes")
    for k in range(1, N):
        print(room[k])
"""

Submission status: Wrong Answer

Solution code:
def resolve():
    def dijkstra(s, n, cost, inf=float("inf")):
        d = [inf] * n
        used = [False] * n
        d[s] = 0
        p = [-9999] * n
        while True:
            v = -1
            for i in range(n):
                if not used[i]:
                    if v == -1:
                        v = i
                    elif d[i] < d[v]:
                        v = i
            if v == -1:
                break
            used[v] = True
            for j in range(n):
                k = d[v] + cost[v][j]
                if k < d[j]:
                    d[j] = k
                    p[j] = v
        return d, p
    n, m = map(int, input().split())
    cost = [[float("inf") for i in range(n)] for i in range(n)]
    for _ in range(m):
        x, y = [int(x) - 1 for x in input().split()]
        cost[x][y] = 1
        cost[y][x] = 1
    l, p = dijkstra(0, n, cost)
    print(l)
    print(p)
    if min(l[1:]) < 1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque
# from math import factorial
import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)

n, m = list(map(int, input().split()))
# a = list(map(int, input().split()))
# ab = [list(map(int, input().split())) for i in range(n)]
# n = int(input())
# n, m = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
room = [[] for i in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    room[a-1].append(b-1)
    room[b-1].append(a-1)


def search(i):
    q = deque()
    q.append(i)
    while q:
        x = q.popleft()
        if 0 in room[x]:
            return x
        else:
            for i in range(len(room[x])):
                q.append(room[x][i])


print("Yes")
for i in range(1, n):
    if 0 in room[i]:
        print(1)
    else:
        a = search(i)
        print(a+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
b = []
#r = ['']*n
for i in range(m):
  t1, t2 = map(int, input().split())
  a.append(t1)
  b.append(t2)
#  r[t2-1]+=' '+str(t1-1)
#  r[t1-1]+=' '+str(t2-1)
#for i in range(len(r)):
#  r[i] = list(map(int, r[i].split()))
#print(r)
d = [-1]*n
d[0] = 0
ans = [-1]*(n-1)
#for i in range(len(a)):
i = 0  
while i < len(a):
  if d[a[i]-1] == -1 and d[b[i]-1] == -1:
    a.append(a[i])
    b.append(b[i])
  elif d[a[i]-1] == -1:
    d[a[i]-1] = d[b[i]-1]+1
    ans[a[i]-2] = b[i]
  elif d[b[i]-1] == -1:
    d[b[i]-1] = d[a[i]-1]+1
    ans[b[i]-2] = a[i]
  elif d[a[i]-1] > d[b[i]-1]:
    d[a[i]-1] = d[b[i]-1]+1
    ans[a[i]-2] = b[i]
  elif d[a[i]-1] < d[b[i]-1]:
    d[b[i]-1] = d[a[i]-1]+1
    ans[b[i]-2] = a[i]
  i += 1
if ans.count(-1) > 0:
  print('No')
else:
  print('Yes')
  for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
# from collections import deque

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

ans = [0]*(N+1)
now = [1]
# next = deque()
next = []
 
while len(now):
    print('now', now)
    for x in now:
        for y in L[x]:
            if (ans[y] == 0):
                ans[y] = x
                next.append(y)
    now = next.copy()
    # now.popleft()
    next = []
 
print("Yes")
for x in range(2, N+1):
    print(ans[x])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    lst = [[] for _ in range(n + 1)]
    ans = [0] * (n + 1)
    for _ in range(m):
        ab = list(map(int, input().split()))
        a, b = tuple(sorted(ab))
        lst[a].append(b)
        lst[b].append(a)

    limit = 10 ** 5
    d = {i: limit + 1 for i in range(1, n + 1)}
    d[1] = 0

    def dfs(n, length):
        # 道しるべ分次へ向かう
        # 洞窟＝n、length=最短距離、i=次の洞窟
        for i in lst[n]:
            if length >= d[i] or i == 1:
                continue
            else:
                d[i] = length
                ans[i] = n

        while lst[n]:
            p = lst[n].pop()
            if d[p] == length:
                dfs(i, length + 1)

    dfs(1, 1)

    if all([i != 0 for i in ans[2:]]):
        print('Yes')
        print(*ans[2:], sep='\n')
    else:
        print('No')


if __name__ == '__main__':
    main()