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:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N, M = Scanner.map_int()
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    print(G)
    q = []
    q.append(0)
    ans = [-1 for _ in range(N)]
    visited = [False for _ in range(N)]
    visited[0] = True
    while q != []:
        p = q.pop(0)
        for g in G[p]:
            if visited[g]:
                continue
            visited[g] = True
            ans[g] = p
            q.append(g)
    ans = [a + 1 for a in ans]
    print('Yes')
    print(*ans[1:], sep='\n')


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
P = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    P[A-1].append(B)
    P[B-1].append(A)
V = [[N,N] for i in range(N)]
V[0] = [0,0]
W = [1]
T = 0
while(W):
    a = W.pop()
    p,q = V[a-1]
    while(P[a-1]):
        s = P[a-1].pop()
        if q + 1 <= V[s-1][1]:
            V[s-1] = [a,q+1]
        W.append(s)
    T += 1
print("Yes")
for i in range(N-1):
    print(V[i+1][0])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import functools
import heapq
import math
from collections import deque
from collections import defaultdict
MOD = 10**9+7

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

stack = [(1,1)]
not_visit = [True]*(N+1)
ans = [0]*(N+1)
while stack:
    now = stack.pop()
    ans[now[0]] = now[1]
    if not_visit[now[0]]:
        not_visit[now[0]] = False
        for room in lines[now[0]]:
            if not_visit[room]:
                stack.append((room,now[0]))

flag = 0
for i in not_visit[1:]:
    if i:
        flag = 1
        break

if flag == 1:
    print("No")
else:
    print("Yes")
    for i in ans[2:]:
        print(i)

Submission status: Wrong Answer

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

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

d_, i_, j_ = [1] * (2*M), [], []
E = {}
for i in range(N):
  E[i] = []
  
for i in range(M):
  a,b = list(map(int, input().split()))
  a,b = a-1, b-1
  i_.append(a)
  j_.append(b)
  i_.append(b)
  j_.append(a)
  E[a].append(b)
  E[b].append(a)
  
coo = coo_matrix((d_, (i_, j_)), (N, N))

dst = shortest_path(coo, indices=0, method='D')

ans = []
for i in range(1,N):
  now = dst[i]
  for j in E[i]:
    if now - 1 == dst[j]:
      ans.append(j+1)
      break
if len(ans) < N-1:
  print('No')
  exit(0)
else:
  print('Yes')
  
for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().strip().split())
to = [[] for _ in range(n)]

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

stack=[0]
ans=[None]*n
while stack:
    cur=stack.pop()
    for nxt in to[cur]:
        if ans[nxt] is not None: # visited
            continue
        ans[nxt]=cur+1
        stack.append(nxt)

if None in ans:
    print("No")
else:
    print("Yes")
    print(*ans[1:])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, input().split())
PATH = [[] for _ in range(N + 1)]

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


USED = [False] * (N + 1)
MARK = [None] * (N + 1)

Q = [1]

while Q:
    node = Q.pop()

    for v in PATH[node]:
        if USED[v]:
            continue

        MARK[v] = node
        USED[v] = True
        Q.append(v)

print("Yes")
print("\n".join(map(str, MARK[2:])))

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n,w = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(1,n+1)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    a,b = map(int,input().split())
    edge[b-1].append([1,a-1])
    edge[a-1].append([1,b-1]) 
res_list = dijkstra_heap(0)
if float('inf') in res_list:
  print("No")
else:
  print("Yes")
  for res in res_list[1:]:
    print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
n,m = map(int,input().strip().split())
graph = defaultdict(list)
for _ in range(m):
    u,v = map(int,input().strip().split())
    graph[u].append(v)
    graph[v].append(u)

queue = deque()
queue.append(1)

mini_passage = [1,1]+[float('inf')]*(n-1)
visited = defaultdict(int)
level = 0
while queue:
    #print(queue,mini_passage,level)
    temp = []
    while queue:
        x = queue.pop()
        mini_passage[x] = min(mini_passage[x],level)
        visited[x] = 1
        for neighbour in graph[x]:
            if not visited[neighbour]:
                temp.append(neighbour)
    queue = temp.copy()
    level += 1

#print(mini_passage)
ans = []
f = 0
if float('inf') in mini_passage:
    print("No")
else:
    print("Yes")
    for val in mini_passage[2:]:
        print(val)

# for val in mini_passage[2:]:
#     if val==float('inf'):
#         f = 1
#         break
#     ans.append(val)
# else:
#     print("No")

Submission status: Wrong Answer

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

q = deque([1])
while(q):
    v = q.popleft()
    for s in E[v]:
        if(ans[s] == -1):
            ans[s] = v
            q.append(s)
    
for s in ans:
    if(s == -1):
        print("No")
        exit()
print("Yes")
for s in ans[2:]:
    print(s)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = [int(x) for x in input().strip().split()]
graph = {}

for i in range(m):
    u, v = [int(x) for x in input().strip().split()]
    if u not in graph:
        graph[u] = []
    if v not in graph:
        graph[v] = []
    graph[u].append(v)
    graph[v].append(u)

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

def bfs(node):
    q = deque([])
    q.append(node)
    dp[node] = node
    while len(q)!=0:
        curr = q.popleft()
        for node in graph[curr]:
            if dp[node] is None:
                dp[node] = curr
                q.append(node)


bfs(1)
print(dp)
flag = True
for i in range(1,n+1):
    if dp[i] is None:
        flag = False
        break

if flag:
    print("Yes")
    for i in range(2,n+1):
        print(dp[i])
else:
    print("No")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# input
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())
path = [[] for _ in range(n)]
ans = [-1] * (n - 1)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # 0idx に直す
    path[a].append(b)
    path[b].append(a)
# room 0 から見ていく
# i-1が""でなければvisited
stack = deque()
stack.append(0)
while len(stack) > 0:
    pos = stack.popleft()
    for next_pos in path[pos]:
        if ans[next_pos - 1] == -1:  # unvisited
            ans[next_pos - 1] = pos + 1
            stack.append(next_pos)
print("Yes")
for i in ans:
    print(i)

Submission status: Wrong Answer

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

next_vec = deque()
for v in path[0]:
    next_vec.append([0, v])
visited = [1] + [0] * (N-1)
parent = [-1] + [0] * (N-1)

while next_vec:
    u, v = next_vec.popleft()
    visited[v] = 1
    parent[v] = u
    for w in path[v]:
        if visited[w] == 0:
            next_vec.append([v,w])

ans_flag = 1
for i in visited:
    if i == 0:
        ans_flag = 0
if ans_flag:
    print('Yes')
    for i in range(1,N):
        print(parent[i]+1)
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))


from collections import deque
n,m = mp()
path = []
for i in range(n+1):
    path.append([])
for i in range(m):
    a,b = mp()
    path[a].append(b)
    path[b].append(a)

ans = [0]*(n+1)
q = deque([1])
used = set()
used.add(1)
while q:
    here = q.popleft()
    for i in path[here]:
        if i not in used:
            ans[i] = ans[here] + 1
            q.append(i)
            used.add(i)
print("Yes")
for i in range(2, n+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,*ab = map(int, read().split())

    E = [[] for _ in range(N+1)]
    for a, b in zip(*[iter(ab)]*2):
        E[a].append(b)
        E[b].append(a)

    par = [0] * (N+1)
    seen = [-1] * (N+1)
    seen[1] = 0
    queue = deque([1])

    while queue:
        v = queue.popleft()
        for e in E[v]:
            if seen[e] == -1:
                seen[e] = seen[v] + 1
                par[e] = v
                queue.append(e)
    
    for i in range(1, N+1):
        if seen[i] == -1:
            print("No")
            exit()
    
    print("\n".join(map(str, par[2:])))

    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

INF = float('inf')
dist = [INF]*n # dfsの条件式の書き換えに注意

ans = [-1]*(n)

from functools import lru_cache
@lru_cache(None)
def dfs(now):
    for next_v in es[now]:
        if dist[next_v] > dist[now]+1:
            dist[next_v] = dist[now]+1
            ans[next_v] = now+1
            dfs(next_v)

start = 0
dist[start]=0 #初期化
dfs(start)

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

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:
                        heapq.heappush(queue,(w,j,k))

        return gb

    def bfs(self,vartex = 0):
        todo = [True]*self.v
        queue = deque([vartex])
        while(len(queue)>0):
            v = queue.popleft
            todo[v] = False
            yield v
            for v_i in self.neighbor[v]:
                if todo[v_i]:
                    queue.append(v_i)

    def dfs(self,vartex = 0):
        seen = [False]*self.v
        def recdfs(v):
            seen[vartex] = True
            for next_v in self.neighbor[vartex]:
                if (seen[next_v]):continue
                recdfs(next_v)
    
        
            
class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False,edge = None, weights = None):
        self.v = v
        self.directed = directed
        self.edge = []
        self.weights = []
        if edge is not None:
            self.addEdges(edge)
        if weights is not None:
            self.addVartex(weights)

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
    
    def addVartex(self,weights):
        if len(weights) != self.v:
            return
        self.weights.extend(weights)

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

def main():
    n,m = tuple([int(t)for t in input().split()])
    edge = []

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

    gb = GraphBuilder(n,edge=edge)
    g = gb.buildGraph()

    queue = deque([0])
    root = [-1]*n
    checked = [False]*n
    while(len(queue)>0):
        p = queue.popleft()
        if checked[p]:
            continue
        checked[p] = True
        for q in g.neighbor[p]:
            root[q] = p+1
            queue.append(q)

    if all(checked):
        print("Yes")
        for i in root[1:]:
            print(i)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

next_vec = deque()
for v in path[0]:
    next_vec.append([0, v])
visited = [1] + [0] * (N-1)
parent = [-1] + [0] * (N-1)

while next_vec:
    u, v = next_vec.pop()
    visited[v] = 1
    parent[v] = u
    for w in path[v]:
        if visited[w] == 0:
            next_vec.append([v,w])

ans_flag = 1
for i in visited:
    if i == 0:
        ans_flag = 0
if ans_flag:
    print('Yes')
    for i in range(1,N):
        print(parent[i]+1)
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
visited = set()
my_dict = dict()

for i in range(m):
    a, b = map(int, input().split())
    if a in my_dict:
        my_dict[a].append(b)
    else:
        my_dict[a] = [b]
    if b in my_dict:
        my_dict[b].append(a)
    else:
        my_dict[b] = [a]

ret_dict = dict()

queue = [1]
visited.add(1)

while queue:
    item = queue.pop()
    if item in my_dict:
        for val in my_dict[item]:
            if val not in visited:
                visited.add(val)
                queue.append(val)
                ret_dict[val] = item

print('Yes')
for i in range(2, n+1):
    print(ret_dict[i])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
graph={i:[] for i in range(1,N+1)}
for _ in range(M):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    
visited=[False for i in range(N+1)]
par=[-1 for i in range(N+1)]
from collections import deque
d=deque()
visited[1]=True
d.append(1)
e=deque()
while d:
    x=d.popleft()
    for node in graph[x]:
        if visited[node]==False:
            par[node]=x
            visited[node]=True
            e.append(node)
        elif visited[node]==True:
            pass
    if e:
        d=e
        e=deque()
    else:
        d=deque()
flag=True
for i in range(2,N+1):
    if par[i]<0:
        flag=False
        break
if flag:
    print("Yes")
    for i in range(2,N+1):
        print(par[i])
else:
    print("No")

Submission status: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




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


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,M=acinput()


L=[[]for i in range(N+1)]
for i in range(M):
    tmp=acinput()
    L[tmp[0]].append(tmp[1])
    L[tmp[1]].append(tmp[0])
    
    
visited=[0]*(N+1)
queue=[1]

parent=[-1]*(N+1)
count=0
while True:
    
    try:
        q=queue.pop()
    except:
        break
    
    for sq in L[q]:
        if not visited[sq]:
            visited[sq]=1
            parent[sq]=q
        
            queue.append(sq)
            count+=1
    

if count<N:
    print("No")
    sys.exit()

print("Yes")
for i in range(2,N+1):
    print(parent[i])

Submission status: Wrong Answer

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

from collections import deque
def bfs():
    heap = deque()
    road = [0]*n

    heap.append((0, -1))
    used = set()
    while heap:
        cur, prev = heap.popleft()
        if cur in used:
            continue
        used.add(cur)
        road[cur] = prev+1
        for to in G[cur]:
            if to not in used and to != prev:
                heap.append((to, cur))
    return road

ans = bfs()
print("yes")
for i in range(1, n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[[0,10**18] for _ in range(n+1)]
q=collections.deque()
q.append((1,0))
check=[0]*(n+1)
check[1]=1
while len(q)!=0:
  v,d=q.pop()
  for u in g[v]:
    if ans[u][1]>d:
      ans[u][0]=v
      ans[u][1]=d
    if check[u]==0:
      check[u]=1
      q.append((u,d+1))
print('Yes')
for i in range(2,n+1):
  print(ans[i][0])

Submission status: Wrong Answer

Solution code:
#D
from collections import deque

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

D = deque(AB)
visited = [-1]*N
visited[0] = 0
mae = [-1]*N
mae[0] = 0
while D:
    d = D.popleft()
    a,b = d
    if visited[a-1] == -1 and visited[b-1] == -1:
        D.append(d)
    elif visited[b-1] == -1:
        visited[b-1] = visited[a-1]+1
        mae[b-1] = a
    elif visited[a-1] == -1:
        visited[a-1] = visited[b-1]+1
        mae[a-1] = b
    else:
        if abs(visited[a-1]-visited[b-1]) <= 1:
            continue
        else:
            if visited[a-1] > visited[b-1]:
                visited[a-1] = visited[b-1]+1
                mae[a-1] = b
            else:
                visited[b-1] = visited[a-1]+1
                mae[b-1] = a
        
if -1 in mae:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(mae[i])

Submission status: Wrong Answer

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

for a,b in lis:
    path[a-1].append(b-1)
    path[b-1].append(a-1)
gone = [0] * n
gone[0] = 1
ans = [-1] * n
now = {0}
for i in range(10 ** 5):
    while now:
        next = set()
        a = now.pop()
        for go in path[a]:
            if gone[go] == 0:
                gone[go] = 1
                ans[go] = a
                next.add(go)
    now = next
print("Yes")
for num in ans:
    if num != -1:
        print(num+1)

Submission status: Wrong Answer

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

next_vec = deque()
for v in path[0]:
    next_vec.append([0, v])
visited = [1] + [0] * (N-1)
parent = [-1] + [0] * (N-1)

while next_vec:
    u, v = next_vec.pop()
    print(u,v)
    visited[v] = 1
    parent[v] = u
    for w in path[v]:
        if visited[w] == 0:
            next_vec.append([v,w])

ans_flag = 1
for i in visited:
    if i == 0:
        ans_flag = 0
if ans_flag:
    print('Yes')
    for i in range(1,N):
        print(parent[i]+1)
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N,M = MI()
adj = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = MI()
    adj[a].append(b)
    adj[b].append(a)
print(adj)

q = deque()
q.append(1)
d = [0]*(N+1)
d[1]=1
while q:
    u = q.popleft()
    for v in adj[u]:
        if d[v]!=0:
            continue
        q.append(v)
        d[v]=u
isOK = True
for i in range(2,N+1):
    if d[i]==0:
        isOK = False
if isOK:
    print('Yes')
    for j in range(2,N+1):
        print(d[j])
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
def main():
    N, M = map(int, input().split())
    dp = [[] for i in range(N)]
    color = [-1 for i in range(N)]
    color[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        dp[a].append(b)
        dp[b].append(a)
    queue = deque()
    queue.append(0)
    while len(queue) != 0:
        now = queue.popleft()
        for i in range(len(dp[now])):
            if color[dp[now][i]] == -1 or color[dp[now][i]] > color[now] + 1:
                color[dp[now][i]] = now + 1
                queue.append(dp[now][i])
    for i in range(N):
        if color[i] == -1:
            print("No")
            sys.exit()
    print("Yes")
    for i in range(1, N):
        print(color[i])



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    roads = [[] for _ in range(n)]
    ans = [0]*n
    for i in range(m):
        a, b = map(int, input().split())
        roads[a-1].append(b-1)
        roads[b-1].append(a-1)
    
    already = [False]*n
    dist = [0]*n
    not_yet = deque(roads[0])
    for v in roads[0]:
        dist[v] = 1
        already[v] = True
    already[0] = True
    
    while not_yet:
        key = not_yet.popleft()
        for v in roads[key]:
            if already[v]:
                continue
            already[v] = True
            dist[v] = dist[key] + 1
            not_yet.append(v)
    
    if all(already):
        print("Yes")
        for i in range(1, n):
            print(dist[i])
    else:
        print("No")
  


if __name__ == "__main__":
    main()