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

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

b = [[] for i in range(n)]
for i in range(m):
    b[a[i][1]-1].append(a[i][0])
    b[a[i][0]-1].append(a[i][1])
    
c = [-1 for i in range(n)]
c[0] = 0
c[b[0][0]-1] = 1
q = deque([b[0][0]])
now = 0
count = 0
while q:
    #print(c,q, now)
    count = count + 1
    if count > 10 ** 5:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        if c[b[now][i] - 1] == -1 and b[now][i] not in q:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            #print(c)
            
#print(c)
print("Yes")
for i in range(1,len(c)):
    print(c[i])

Submission status: Wrong Answer

Solution code:
import numpy as np
a = list(map(int,input().split()))
k = []
count = []
ans = []
room = []
for i in range(0,a[0]) :
    k.append([])
    count.append([])
    ans.append([])
    if i == 0 :
        room.append(0)
    else :
        room.append(-1)
for i in range(0,a[1]) :
    b = list(map(int,input().split()))
    k[b[0]-1].append(b[1])
    k[b[1]-1].append(b[0])
#print(k)
M = []
poi = []
for i in range(0,a[0]) :
    poi = []
    for j in range(0,len(room)) :
        if j in poi :
            continue
        if 1 in count[j] :
            continue
        if room[j] != -1 :
            count[j].append(1)
            for t in k[j] :
                if room[t-1] == -1 :
                    room[t-1] = j + 1
                    poi.append(t-1)
        else :
            continue
    print(room)
    if M == room :
        break
    else :
        M = list(room)

room = room[1:]
if -1 in room :
    print("No")
else :
    print("Yes")
    for i in room:
        print(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
a = list(map(int,input().split()))
k = []
count = []
ans = []
room = []
for i in range(0,a[0]) :
    k.append([])
    count.append([])
    ans.append([])
    if i == 0 :
        room.append(0)
    else :
        room.append(-1)
for i in range(0,a[1]) :
    b = list(map(int,input().split()))
    k[b[0]-1].append(b[1])
    k[b[1]-1].append(b[0])

M = []
for i in range(0,a[0]) :
    for j in range(0,len(room)) :
        if 1 in count[j] :
            continue
        if room[j] != -1 :
            count[j].append(1)
            for t in k[j] :
                if room[t-1] == -1 :
                    room[t-1] = j + 1
        else :
            continue
    if M == room :
        break
    else :
        M = list(room)

room = room[1:]
if -1 in room :
    print("No")
else :
    print("Yes")
    for i in room:
        print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(M):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

siru=[-1]*(N-1)#2~~N
que=deque([0])

while que:
    #print(que)
    now=que.pop()
    nexlist=G[now]
    for nex in nexlist:
        if nex==0:
            continue
        if siru[nex-1]==-1:
            siru[nex-1]=now
            que.append(nex)
X=siru.count(-1)
if X>=1:
    print("No")
else:
    print("Yes")
    for num in siru:
        print(num+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(M):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

siru=[-1]*(N-1)#2~~N
que=deque([0])

while len(que)>0:
    #print(que)
    now=que.pop()
    nexlist=G[now]
    for nex in nexlist:
        if nex==0:
            continue
        if siru[nex-1]==-1:
            siru[nex-1]=now
            que.append(nex)
X=siru.count(-1)
if X>=1:
    print("No")
else:
    print("Yes")
    for num in siru:
        print(num+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
a = list(map(int,input().split()))
k = []
count = []
for i in range(0,a[0]) :
    k.append([])
    count.append([])
for i in range(0,a[1]) :
    b = list(map(int,input().split()))
    k[b[0]-1].append(b[1])
    k[b[1]-1].append(b[0])

an = []
room = []
for i in range(0,a[0]) :
    if i == 0 :
        an.append(0)
    else :
        an.append(-1)
for i in range(0,a[0]+1) :
    room.append(an)
    '''
room.append(an)
an = []
for i in range(0,a[0]) :
    an.append(-1)
for i in range(0,a[0]) :
    room.append(an)
    '''
room = np.array(room).tolist()

for i in range(1,a[0]+1) :
    for j in range(0,a[0]) :
        if 1 in count[j] :
            continue
        if room[i-1][j] != -1 :
            room[i][j] = room[i-1][j]
        if room[i-1][j] == -1 : 
            continue
        else :
            count[j].append(1)
            for m in k[j] :
                if room[i-1][m-1] == -1 :
                    if room[i][m-1] == -1 :
                        room[i][m-1] = j + 1
                    else :
                        continue
                else :
                    room[i][m-1] = room[i-1][m-1]
    print(room)
    if room[i] == room[i-1] :
        room = room[:i]
        break

ans = room[len(room)-1][1:]
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(" "))
ar = [[] for i in range(n)]
br = [0 for i in range(n-1)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
cr = [0]
dr = []
c = 0
del ar[0]
while True:
    c += 1
    for r in cr:
        for i in range(n-1):
            if r in ar[i] and br[i] == 0:
                br[i] = c
                dr.append(i+1)
    if br.count(0) == 0:
        break
    cr = dr
print("Yes")
for r in br:
    print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
a = list(map(int,input().split()))
k = []
for i in range(0,a[0]) :
    k.append([])
for i in range(0,a[1]) :
    b = list(map(int,input().split()))
    k[b[0]-1].append(b[1])
    k[b[1]-1].append(b[0])

room = []
dkt = []
for i in range(0,a[0]) :
    if i == 0 :
        room.append(0)
    else :
        room.append(-1)
dkt.append(room)
room = []
for i in range(0,a[0]) :
    room.append(-1)
for i in range(0,a[0]) :
    dkt.append(room)
dkt = np.array(dkt).tolist()

for i in range(1,a[0]+1) :
    for j in range(0,a[0]) :
        if dkt[i-1][j] < 0 :
            continue
        dkt[i][j] = dkt[i-1][j]
        for m in k[j] :
            if dkt[i][m-1] < 0 :
                dkt[i][m-1] = dkt[i-1][j] + 1
            else :
                dkt[i][m-1] = min(dkt[i-1][j] + 1,dkt[i-1][m-1])

ans = dkt[len(dkt)-1][1:]
if min(ans) < 0 :
    print("No")
else :
    print("Yes")
    for i in ans :
        print(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
a = list(map(int,input().split()))
k = []
for i in range(0,a[0]) :
    k.append([])
for i in range(0,a[1]) :
    b = list(map(int,input().split()))
    k[b[0]-1].append(b[1])
    k[b[1]-1].append(b[0])

room = []
dkt = []
for i in range(0,a[0]) :
    if i == 0 :
        room.append(0)
    else :
        room.append(-1)
dkt.append(room)
room = []
for i in range(0,a[0]) :
    room.append(-1)
for i in range(0,a[0]) :
    dkt.append(room)
dkt = np.array(dkt).tolist()

for i in range(1,a[0]+1) :
    for j in range(0,a[0]) :
        if dkt[i-1][j] < 0 :
            continue
        dkt[i][j] = dkt[i-1][j]
        for m in k[j] :
            if dkt[i][m-1] < 0 :
                dkt[i][m-1] = dkt[i-1][j] + 1
            else :
                dkt[i][m-1] = min(dkt[i-1][j] + 1,dkt[i-1][m-1])

ans = dkt[len(dkt)-1][1:]
if min(ans) < 0 :
    print("Fail")
else :
    for i in ans :
        print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

INF=100050

q=deque()

class Room:
    def __init__(self,num):
        self.number=num
        self.frontier=True
        self.neighbor=[]
        self.arrow=0
        self.deepness=INF

    def set(self,room):
        self.neighbor.append(room)
    
    def search(self,num,deps):
        self.arrow=num
        self.deepness=deps
        self.frontier=False

    def dfs(self):
        for i in self.neighbor:
            if rooms[i].frontier:
                rooms[i].search(self.number,self.deepness+1)
                q.append(i)

rooms=[]
for i in range(n+1):
    rooms.append(Room(i))

for _ in range(m):
    a,b=map(int,input().split())
    rooms[a].set(b)
    rooms[b].set(a)

q.append(1)
while q:
    rooms[q.popleft()].dfs()

for i in range(2,len(rooms)):
    if rooms[i].frontier==False:
        print(rooms[i].arrow)

Submission status: Wrong Answer

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

graph = [[] for _ in range(n)]
for i in range(m):
    graph[a[i] - 1].append(b[i] - 1)
    graph[b[i] - 1].append(a[i] - 1)
print(graph)

pathway = [None for _ in range(n)]
queue = [0]
depth = [-1]*n
depth[0] = 0
pre = [-1]*n

while queue:
    now = queue.pop(0)
    for i in graph[now]:
        if depth[i] == -1:
            if pre[i] == -1:
                pre[i] = now
            depth[i] = depth[now] + 1
            queue.append(i)

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

Submission status: Wrong Answer

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

def decode_input(input_string):
    input_list = input_string.split("\n")
    N, M = map(int, input_list[0].split())
    A = []
    B = []
    for i in range(M):
        A_i, B_i = map(int, input_list[i+1].split())
        A.append(A_i)
        B.append(B_i)
    return N, M, A, B


class Rooms(object):
    def __init__(self, N, M, A, B):
        self.N = N
        self.M = M
        A = [x - 1 for x in A]
        B = [x - 1 for x in B]
        self.A = A
        self.B = B
        self.rooms = [Room(i) for i in range(N)]
        self.set_aisles()

    def set_aisles(self):
        for i, j in zip(self.A, self.B):
            print(i, j)
            self.rooms[i].add_aisle(j)
            self.rooms[j].add_aisle(i)

    def update_rooms(self, room_index=0):
        for i in self.rooms[room_index].aisles:
            if (self.rooms[i].found_step is None) or self.rooms[i].found_step > self.rooms[room_index].found_step:
                self.rooms[i].found_step = self.rooms[room_index].found_step + 1
                self.rooms[i].next_hop = room_index
                self.update_rooms(room_index=i)

    def check_result(self):
        print("___")
        for i in range(1, self.N):
            if self.rooms[i].next_hop is None:
                return "No"
        return "Yes"
        

    def solve(self):
        self.set_aisles()
        self.update_rooms()
        # [print(room.next_hop) for room in self.rooms]
        result = self.check_result()
        print(result)
        [print(room.next_hop + 1) for room in self.rooms[1:]]
        

class Room(object):
    def __init__(self, i):
        self.index = i
        self.aisles = []
        self.next_hop = None
        if i == 0:
            self.found_step = 0
        else:
            self.found_step = None

    def add_aisle(self, j):
        self.aisles.append(j)

Submission status: Wrong Answer

Solution code:
from queue import Queue
s=input().split(' ')
N=int(s[0])
M=int(s[1])
room_from=[]
room_to=[]

for i in range(M):
  s=input().split(' ')

#道は両方向に使える
  room_from.append(int(s[0]))
  room_to.append(int(s[1]))
  room_from.append(int(s[1]))
  room_to.append(int(s[0]))

#for i in range(2*M):
#  print("from=",room_from[i],"to=",room_to[i])


#最小経路の回答を入れる. ansewr[room_from]=room_to


answer={}
todo={}
temp={}
todoq=Queue(N)

for (i,room) in enumerate(room_to): 
  if room_to[i] == 1:
    todo[room_from[i]]=1

answer.update(todo)

while True:
  for a in todo:
    for (i,room) in enumerate(room_to): 
      if room == a and room_from[i] not in temp and room_from[i] not in answer and room_from[i] != 1:
        temp[room_from[i]]=a
  if len(temp)==0:
    break
  else:
    todo.clear()
    todo.update(temp)
    answer.update(temp)
    temp.clear()
print(answer)
if len(answer)== N-1 :
  print ("Yes")
  for n in answer:
    print (answer[n])
else:
  print ("No")

Submission status: Wrong Answer

Solution code:
s=input().split(' ')
N=int(s[0])
M=int(s[1])
room_from=[]
room_to=[]

for i in range(M):
  s=input().split(' ')

#道は両方向に使える
  room_from.append(int(s[0]))
  room_to.append(int(s[1]))
  room_from.append(int(s[1]))
  room_to.append(int(s[0]))

#for i in range(2*M):
#  print("from=",room_from[i],"to=",room_to[i])


#最小経路の回答を入れる. ansewr[room_from]=room_to


answer={}
temp={}
for (i,room) in enumerate(room_to): 
  if room_to[i] == 1:
    answer[room_from[i]]=1

temp={}
for n in range(N):
  for a in answer:
    for (i,room) in enumerate(room_to): 
      if room == a and room_from[i] not in temp and room_from[i] not in answer and room_from[i] != 1:
        temp[room_from[i]]=a
  #        print("temp=",temp)
  answer.update(temp)
#  print ("answer=",answer)

if len(answer)== N-1 :
  print ("Yes")
  for n in answer:
    print (answer[n])
else:
  print ("No")

Submission status: Wrong Answer

Solution code:
s=input().split(' ')
N=int(s[0])
M=int(s[1])
room_from=[]
room_to=[]

for i in range(M):
  s=input().split(' ')

#道は両方向に使える
  room_from.append(int(s[0]))
  room_to.append(int(s[1]))
  room_from.append(int(s[1]))
  room_to.append(int(s[0]))

#for i in range(2*M):
#  print("from=",room_from[i],"to=",room_to[i])


#最小経路の回答を入れる. ansewr[room_from]=room_to


answer={}
temp={}
for (i,room) in enumerate(room_to): 
  if room_to[i] == 1:
    answer[room_from[i]]=1

temp=answer.copy()
for n in range(N):
  for a in answer:
    for (i,room) in enumerate(room_to): 
      if room == a and room_from[i] not in temp and room_from[i] != 1:
        temp[room_from[i]]=a
#        print("temp=",temp)
  answer.update(temp)
#  print ("answer=",answer)

if len(answer)== N-1 :
  print ("Yes")
  for n in answer:
    print (answer[n])
else:
  print ("No")

Submission status: Wrong Answer

Solution code:
s=input().split(' ')
N=int(s[0])
M=int(s[1])
room_from=[]
room_to=[]

for i in range(M):
  s=input().split(' ')

#道は両方向に使える
  room_from.append(int(s[0]))
  room_to.append(int(s[1]))
  room_from.append(int(s[1]))
  room_to.append(int(s[0]))

#for i in range(2*M):
#  print("from=",room_from[i],"to=",room_to[i])


#最小経路の回答を入れる. ansewr[room_from]=room_to


answer={}
temp={}
for (i,room) in enumerate(room_to): 
  if room_to[i] == 1:
    answer[room_from[i]]=1

temp=answer.copy()
for n in range(N):
  for a in answer:
    for (i,room) in enumerate(room_to): 
      if room == a and room_from[i] not in temp and room_from[i] != 1:
        temp[room_from[i]]=a
#        print("temp=",temp)
  answer.update(temp)
#  print ("answer=",answer)

if len(answer)== N-1 :
  print ("Yes")
  for n in answer:
    print (answer[n])

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfn():
    q=deque([0])
    visit[0]=True
    while q:
        room_proper=q.popleft()
        for i in graph[room_proper]:
            if visit[i]==False:
                visit[i]=True
                shirube[i]=room_proper
                q.append(i)



if __name__ == "__main__":

    n,m=map(int,input().split())
    shirube=[0]*n
    b=[]
    visit=[False]*n
    graph=[[]*n for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        graph[a].append(b)
        graph[b].append(a)
    bfn()
    print(visit)
    if all(visit)==True:
        print("Yes")
        for i in range(1,n):
            print(shirube[i]+1)
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
N,M=map(int, input().split())
l=[[0]*N for i in range(N)]
for i in range(M):
  a ,b = map(int, input().split())
  l[a-1][b-1]=1
  l[b-1][a-1]=1

Submission status: Wrong Answer

Solution code:
from collections import deque

# 初期化周り
N, M = map(int, input().rstrip().split())
G = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().rstrip().split())
    G[A].append(B)
    G[B].append(A)

# 目印
sign = [-1]*(N+1)
sign[0] = None
sign[1] = 0

queue = deque([1])

while queue:
    node = queue.popleft()
    for next in G[node]:
        if sign[next] > -1:
            continue
        sign[next] = node
        queue.append(next)

if -1 in sign:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque

# 初期化周り
N, M = map(int, input().rstrip().split())
G = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().rstrip().split())
    G[A].append(B)
    G[B].append(A)

# 目印
sign = [-1]*(N+1)
sign[1] = 0

queue = deque([1])

while queue:
    node = queue.popleft()
    for next in G[node]:
        if sign[next] > -1:
            continue
        sign[next] = node
        queue.append(next)

ans = "Yes"

print(sign)

for i in range(2, N+1):
    S = sign[i]
    while S > 0:
        S = sign[S]

    if not S == 0:
        ans = "No"

print(ans)
if ans == "Yes":
    for i in range(2, N+1):
        print(sign[i])

Submission status: Wrong Answer

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
print(to)
dist=[0]*n    
flag=[False]*n
flag[0]=True
que=[]
que.append(0)
while(False in flag):
    v=que.pop(0)
    for i in to[v]:
        if(flag[i]==False):
            dist[i]=v+1
            flag[i]=True
            que.append(i)
        


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

Submission status: Wrong Answer

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

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

dist=[0]*n    
flag=[False]*n
flag[0]=True
que=[]
que.append(0)
while(False in flag):
    v=que.pop(0)
    for i in range(n):
        if(cost[v][i]==1 and flag[i]==False):
            dist[i]=v+1
            flag[i]=True
            que.append(i)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int,input().split())
r=np.array([list(map(int,input().split())) for _ in range(m)])
start=np.array([1], dtype='int8')
done=np.array([1], dtype='int8')
ans=np.array([-1]*n, dtype='int8')

for _ in range(n-1):
    start_tmp=np.array([], dtype='int8')
    for st in start:
        #print(st)
        r_st = r[np.any(r==st, axis=1)].flatten()
        r_gl = np.setdiff1d(np.delete(r_st, np.where(r_st == st)), done)
        
        start_tmp=np.unique(np.append(start_tmp, r_gl))
        done=np.unique(np.append(done, r_gl))
        #print(r_gl)
        ans[r_gl-1] = st
        
    start = start_tmp
    #print(ans)
    #print(start, done)
    
    if len(done)==n:
        break
    
print('Yes')
print('\n'.join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
AB = [list(input().split()) for i in range(M)]

routes = dict(zip([str(n+1) for n in range(N)], [0 for n in range(N)]))
routes['1'] = 1
que = ['1'] # 探索対象

while (len(que) != 0) & (len(AB) != 0):
    room = que.pop() # 探索対象
    
    for ab in AB:
        if room in ab: # 部屋番号が含まれている通路
            room_next = ab[1-ab.index(room)] # 探している方じゃない物
            if routes[room_next] == 0: # まだ看板のない部屋なら
                que.append(room_next) # 探索対象にして
                routes[room_next] = int(room) # 看板を立てる

if all([v != 0 for v in routes.values()]): # 全ての部屋に看板がたったら
    print('Yes')
    for n in range(2, N+1):
        print(routes[str(n)])
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def dfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.pop()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited

def main():
    #n = int(stdin.readline().rstrip())
    n,m = map(int, stdin.readline().rstrip().split())
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b = map(int, stdin.readline().rstrip().split())
        a-=1;b-=1 #indexに直す
        graph[a].append(b)
        graph[b].append(a)
    visited = dfs(graph, n, 0)
    print("Yes")
    for i in range(1,n):
        print(visited[i])

main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n,m = map(int,input().split())

listA=[] #appendのために宣言が必要
while True:
    try:
        listA.append(list(map(int,input().split())))

    except:
        break;
        #または、quit(),os.exit()をして止める。

#print(listA)

aisle = [[] for i in range(n)]
#print(aisle)
for i in range(m):
    aisle[listA[i][1]-1].append(listA[i][0]-1)
    aisle[listA[i][0]-1].append(listA[i][1]-1)
#print(aisle)
#for i in range(n):
#    aisle[i].pop(0)
#print(aisle)

t = [10**9]*n
t[0] = 0
for i in range(n):
    for j in aisle[i]:
        if t[j] >= t[i]+1:
            t[j] = t[i]+1
#print(t)
print("Yes")
for i in range(1, n):
    print(t[i])

Submission status: Wrong Answer

Solution code:
def main():
    N,M=map(int,input().split())
    to=[[] for _ in range(N)]
    for _ in range(M):
        A,B=map(int,input().split())
        A-=1
        B-=1
        to[A].append(B)
        to[B].append(A)
    queue=[]
    dist=[-1]*N
    prev=[-1]*N
    dist[0]=0
    queue.append(0)
    while len(queue)!=0:
        v=queue.pop()
        for u in to[v]:
            if dist[u]!=-1: continue
            dist[u]=dist[v]+1
            prev[u]=v
            queue.append(u)
    print('Yes')
    for i in range(N):
        if i==0: continue
        ans=prev[i]+1
        print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri May 22 04:38:30 2020

@author: hiros
"""
import numpy as np
"""
N = 4
M = 4
A = np.array([0,1,2,3])
B = np.array([1,2,3,1])
"""
N,M = map(int,input().split())
A,B = np.zeros(M,dtype=int),np.zeros(M,dtype=int)
for i in range(M):
    A[i],B[i] = map(int,input().split())

A = A-1
B = B-1

ans = np.zeros(N,dtype=int)
ans = ans-1
ans[0]=-2

for i in range(M):
    if (A[i] == 0): #部屋１とつながっている部屋には道しるべ１を置く
        ans[B[i]] = 0
    elif (B[i] == 0):
        ans[A[i]] = 0

flag = 1
deep = 1
room = []
for i in range(N):
    if ans[i]==0:
        room.append(i)  #階層1にある部屋のリスト
room_next = []

while (flag==1):
    for i in room:
        for m in range(M):
            if (A[m]==i and ans[B[m]]==-1):
                ans[B[m]] = i
                room_next.append(B[m])
            elif (B[m]==i and ans[A[m]]==-1):
                ans[A[m]] = i
                room_next.append(A[m])
            else:
                continue
    room = room_next
    print(room_next)
    flag = 0
    for i in range(N):
        if ans[i] == -1:
            flag = 1
            break   

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

Submission status: Wrong Answer

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

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

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

lt=[0 for i in range(n)]
lll=[1]
for i in range(n):
    for j in ll[lll[i]-1]:
        lll.append(j)
    lll=list(dict.fromkeys(lll))
    print(lll)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

print(graph)

dist = [0] * (n + 1)

d=deque()
d.append(1)

while d:
    v = d.popleft()
    
    for i in graph[v]:
        if not dist[i]:
            dist[i] = v
            d.append(i)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

dist = [-1] * (n + 1)
dist[0] = 0
dist[1] = 0

d=deque()
d.append(1)

while d:
    v = d.popleft()
    
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M=map(int,input().split())
A=np.zeros(N)
B=np.zeros([M,2])
for i in range(M):
  k,l=map(int,input().split())
  B[i,0]=k
  B[i,1]=l

C={1}
E=[]
while len(C)<N:
  for i in range(B.shape[0]):
    if B[i,0] in C:
      if A[int(B[i,1])-1]==0:
        A[int(B[i,1])-1]=B[i,0]
        C.add(B[i,1])
      E.append(i)
    elif B[i,1] in C:
      if A[int(B[i,0])-1]==0:
        A[int(B[i,0])-1]=B[i,1]
        C.add(B[i,0])
      E.append(i)
  B=np.delete(B,E,0)
  E=[]

print("Yes")
for i in range(1,N):
  print(int(A[i]))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

roomSign=[0]*n

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

D=deque([0])

while D:
    v=D.popleft()
    for i in graph[v]:
        if roomSign[i] == 0:
          roomSign[i]=v
          D.append(i)

print("Yes")

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

roomSign=[0]*n

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

D=deque([0])

while D:
    v=D.popleft()
    for i in graph[v]:
        if not roomSign[i] == 0:
          roomSign[i]=v
          D.append(i)

print("Yes")

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

Submission status: Wrong Answer

Solution code:

from collections import deque

def parse():
  N, M = map(int, input().split(" "))

  rooms = [[] for n in range(N)]
  for m in range(M):
    a, b = map(int, input().split(" "))
    rooms[a - 1].append(b - 1)
    rooms[b - 1].append(a - 1)
  
  return N, M, rooms

def main():
  N, M, rooms = parse()

  # 探索する部屋番号をqに入れる
  q = deque([])
  q.append(0)

  # 各部屋の道しるべを入れる変数
  guides = [None for n in range(N)]
  guides[0] = 0
  while len(q) > 0:
    room_num = q.popleft()
    # print("room_num:", room_num)

    # 次に探索する部屋は，今の部屋を道しるべに指す
    for next_room_num in rooms[room_num]:
      # print("guides[next_room_num]:", guides[next_room_num])
      if guides[next_room_num] == None:
        q.append(next_room_num)
        # print(next_room_num)
      
        guides[next_room_num] = guides[room_num] + 1
        # if next_room_num != room_num:

      
    # print("q:", q)
    # print("guides:", guides)
    # input()
  
  for guide in guides[1:]:
    if guide == None:
      print("No")
      exit(0)
  print("Yes")
  for guide in guides[1:]:
    print(guide)

if __name__ == "__main__":
  main()

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)]
ans=[0]*n
def bfs():
    deq.append(0)#1
    finish=set()
    finish.add(0)
    while deq:
        #print(deq)
        now=deq.pop()
        for ad_i in adlist[now]:
            if ad_i-1 != now and ad_i-1 not in finish:
                if ans[ad_i-1]==0:
                    ans[ad_i-1]=now+1
                deq.append(ad_i-1)
                finish.add(ad_i-1)

adlist=[[] for _ in range(n)]
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
#print(adlist)
deq=deque()
bfs()
print("Yes")
for i in range(1,n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M = map(int, input().split())
m = map(int, input().split())
 
G = [[] for _ in range(N + 1)]
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)
 
par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)
 
print('Yes')
print(*par[2:], sep='\n')