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:
N, M =map(int, input().split())



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)
    
    

visited = [False for _ in range(N)]
stock = [1]
visited[0] = True
sign = [-1 for _ in range(N)]

while True:
    if not stock:
        break
    else:
        q = stock.pop()
        probable_room = path[q-1]
#         pritn(probable_room)
        for p in probable_room:
            if p == q:
                continue
            if visited[p-1]:
                continue
            else:
#                 print(1111)
                visited[p-1] = True
                sign[p-1] = q
                stock.append(p)
if all(visited):
    print("Yes")
    for i in range(1,N):
        print(sign[i])
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ans = [-1]*n
used = [0]*n
used[0] = 1
que = deque()
que.appendleft(0)
while que:
    v = que.pop()
    # print(v)
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv] = 1
        que.appendleft(nv)
        if ans[nv] == -1:
            ans[nv] = v
    # exit()
# print(ans)    
# print(g)
for i in range(1, n):
    print(ans[i]+1)

Submission status: Wrong Answer

Solution code:
# 参考https://qiita.com/kazukazukazukazu/items/e5db00a3aefb1f5ed72f
import collections
import heapq


class Dijkstra:
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

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

graph1 = Dijkstra()

for a, b in AB:
    graph1.add(a, b, 1)

ans = []
for i in range(2, N+1):
    result = graph1.search(i)
    ans.append(result[1])
if float('inf') in ans:
    print('No')
else:
    print('Yes')
    for a in ans:
        print(a)

Submission status: Wrong Answer

Solution code:
import sys
import collections
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

DQ=collections.deque([(1,0)])
VS=set([1])
MP={}
N,M=LI()
RES=[0]*(N+1)

for i in range(M):
    ff,tt=LI()
    if not ff in MP: MP[ff] = []
    if not tt in MP: MP[tt] = []
    MP[ff].append(tt)
    MP[tt].append(ff)

# print("----")
while DQ:
    i, dist = DQ.popleft()
    # print(i,dist)
    if i in MP:
        for j in MP[i]:
            if not j in VS:
                VS.add(j)
                DQ.append((j, dist+1))
                RES[j] = i

# print(VS, MP)
if len(VS) < N:
    print("No")
else:
    for i in range(2, N+1):
        print(RES[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N, M = MII_split()

def dijkstra(s, n, w, cost):
    # 始点sから各頂点への最短距離
    # n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    signs = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        # まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            if d[j] > d[v] + cost[v][j]:
                d[j] = d[v] + cost[v][j]
                signs[j] = v+1
        return signs

    cost = [[float('inf') for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        x, y = MII_split()
        if x > y:
            x, y = y, x
        cost[x - 1][y - 1] = 1

    d = dijkstra(0, N, M, cost)
    if float('inf') in d:
        print('No')
    else:
        print('Yes')
        print_list_in_2D(d[1:])

Submission status: Wrong Answer

Solution code:
import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}

while queue:
    cost, cur = queue.pop()
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.append((next_cost, next_cur))

del results[0]
# print(results)

is_no = False
for k, result in results.items():
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    for k, result in results.items():
        print(result[1]+1)

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]
path = []
for i in range(M):
  t1, t2 = [int(x) for x in input().split()]
  if t1 < t2:
    path.append((t1, t2))
  else:
    path.append((t2, t1))
path.sort()
print(path)
bread = [1] + [0] * (N-1)
while True:
  for i in reversed(range(len(path))):
    if bread[path[i][0]-1] == 0:
      if bread[path[i][1]-1] != 0:
        bread[path[i][0]-1] = path[i][1]
        path.pop(i)
    elif bread[path[i][1]-1] == 0:
      bread[path[i][1]-1] = path[i][0]
      path.pop(i)
    else:
      path.pop(i)
  print(bread)
  if path == []:
    break
print('Yes')
for i in range(1, N):
  print(bread[i])

Submission status: Wrong Answer

Solution code:
import heapq

inf = 10 ** 9


def dijkstra(a):
    color = ["white" for _ in range(n + 1)]
    D = [inf for _ in range(n + 1)]

    D[a] = 0
    color[a] = "gray"
    queue = [[0, a]]
    heapq.heapify(queue)

    while len(queue) > 0:
        u = heapq.heappop(queue)[1]
        if color[u] == "black": continue
        color[u] = "black"

        V = [[i, j] for i, j in M[u] if color[j] != "black"]
        if len(V) > 0:
            for i, j in V:
                if D[u] + i < D[j]:
                    D[j] = D[u] + i
                    color[j] = "gray"
                    heapq.heappush(queue, [D[j], j])

    return D


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
M=[[] for _ in range(n+1)]
for a,b in AB:
    M[a].append([1,b])
    M[b].append([1,a])
D=dijkstra(1)
if inf not in D[1:]:
    print("Yes")
    for i in D[2:]:
        print(i)
else:print("No")

Submission status: Wrong Answer

Solution code:
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)

# bfs
milestone = [0] * (n+1)
q = []
q.append(1)
while len(q) != 0:
    for i in graph[q[0]]:
        if milestone[i] == 0:
            milestone[i] = q[0]
            q.append(i)
    q.pop(0)

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
used = []
for i in range(n+1):
    # visited, pv, cost
    used.append([False, None])
path = []
for i in range(n+1):
    path.append([])
for i in range(m):
    a, b = map(int, input().split())
    path[a].append(b)
    path[b].append(a)

import collections
q = collections.deque([])
q.append([1, -1, 0])
print(path)
while len(q) > 0:
    print("qu", q)
    curroom, pv, cost = q.popleft()
    print("visit", curroom, used)
    print(" > path", path[curroom])
    if used[curroom][0] is True:
        continue
    used[curroom][0] = True
    used[curroom][1] = pv
    for i in range(len(path[curroom])):
        nextroom = path[curroom][i]
        #print(" >> path[{0}] = {1}".format(path[curroom][i], nextroom))
        #print(" >>>>", used[nextroom])
        if used[nextroom][0] is True:
            #print(" >>!!visited")
            continue
        q.append([nextroom, curroom,cost])

print(used)


can = True # 判定
for i in range(1, n+1):
    x,y = used[i]
    if x is False:
        can = False

if can is False:
    print("No")
else:
    print("Yes")
    for i in range(2, n+1):
        print(used[i][1])

Submission status: Wrong Answer

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

paths = []
for i in range(M):
  paths.append(sorted([int(v) - 1 for v in input().split(" ")]))
  
marks = [-1 for _ in range(N)]
hops = [999999999999999999999999999 for _ in range(N)]
marked = [0]
marks[0] = 0
hops[0] = 0

hops_prev = sum(hops)
for _ in range(100):
  for path_index in range(M):
    path = paths[path_index]
    
    for path in [(path[0], path[1]), (path[1], path[0])]:
      hop_ = hops[path[1]]
      hop = hops[path[0]] + 1
      if hop_ > hop:
        marks[path[1]] = path[0]
        hops[path[1]] = hop
        
  if hops_prev == sum(hops):
    break
  else:
    hops_prev = sum(hops)
     

if min(hops) >= 999999999999999999999999999:
  print("No")
else:
  print("Yes")
  [print(v+1) for v in marks[1:]]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

D = [0] * n
q = deque([0])
while q:
    u = q.popleft()
    for v in G[u]:
        if D[v]:
            continue
        D[v] = D[u] + 1
        q += [v]


print('Yes')
for i in range(1, n):
    ret = INF
    for j in G[i]:
        if D[j] < ret:
            ret = D[j]
            ans = j
    print(ans + 1)

Submission status: Wrong Answer

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

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

inf = float('inf')
distance = [[-1, inf] for i in range(n)] #目印、距離
queue = deque([])

distance[0] = [0, 0]
queue.appendleft(0)

while len(queue) > 0:
  v = queue.popleft() 
  judge = True
  for next_v in graph[v]:
    if distance[next_v][0] == -1 or distance[v][1]+1 < distance[next_v][1]:
      distance[next_v] = [v, distance[v][1]+1]
      judge = False
  if not judge:    
    queue.append(next_v)

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

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]
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)
print("Yes")
for i in range(N-1):
    print(V[i+1][0])

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

n,m=getNM()
a=[]
b=[]
c=[0]*(n+1)
for i in range(m):
    a1,b1=getNM()
    a.append(a1)
    b.append(b1)
    if a1==1:
        c[b1]=1
    elif b1==1:
        c[a1]=1


for i in range(1,n):
    for j in range(m):
        #print(c)
        if c[a[j]]==i and c[b[j]]==0:
            c[b[j]]=a[j]
        elif c[b[j]]==i and c[a[j]]==0:
            c[a[j]]=b[j]

for i in range(n-1):
    print(c[2:][i])

Submission status: Wrong Answer

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



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)
    
    

visited = [False for _ in range(N)]
stock = [1]
visited[0] = True
sign = [-1 for _ in range(N)]

while True:
    if not stock:
        break
    else:
        q = stock.pop()
        probable_room = path[q-1]
#         pritn(probable_room)
        for p in probable_room:
            if p == q:
                continue
            if visited[p-1]:
                continue
            else:
#                 print(1111)
                visited[p-1] = True
                sign[p-1] = q
                stock.append(p)
for i in range(1,N):
    print(sign[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
AB = [[] for _ in range(N+1)]
for i in range(M):
    A_tmp , B_tmp = map(int, input().split())
    AB[A_tmp].append(B_tmp)
    AB[B_tmp].append(A_tmp)

ans = [0]*(N+1)
visited = list()

q = deque()
q.append(1)
past = 1
while len(q) > 0:
    node = q.popleft()
    ans[node] = past
    visited.append(node)
    for t in AB[node]:
        if t in visited:
            continue
        if t in q:
            continue
        q.append(t)
        past = node
print("Yes")
for i in range(2, N+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify

from heapq import heappush, heappop, heapify


def trace(s, t, ancestors):
    route = [t]
    c = t
    while True:
        a = ancestors[c]
        assert a is not None, 'Failed to trace'
        route.append(a)
        if a == s:
            break
        c = ancestors[c]
    route.reverse()
    return route


def dijkstra(s, t, links):
    heap = [(*l, s) for l in links[s]]
    heapify(heap)
    visited = set()
    ancestors = [None] * N
    while heap:
        cost, node, ancestor = heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        ancestors[node] = ancestor
        if node == t:
            return cost, trace(s, t, ancestors)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2, node))
    return float('inf'), None

N, M = map(int, input().split())
links = [set() for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    links[x-1].add((1, y-1))
    links[y-1].add((1, x-1))
print(links)
ans = [0]*N
for i in range(1, N):
    tmp = dijkstra(0, i, links)
    if tmp == float("inf"):
        print("No")
        exit()
    ans[i] = tmp[1][-2]+1
print("Yes")
for i in range(1,N):
    print(ans[i])

Submission status: Wrong Answer

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

import sys
import pprint
from collections import deque

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(1)
	n, m = map(int, sys.stdin.readline().split())
	graph = [[] for i in range(n)]
	for i in range(m):
		ai, bi = map(int, sys.stdin.readline().split())
		graph[ai-1].append(bi-1)
		graph[bi-1].append(ai-1)
	stack = deque([0])
	dist = [-1]*len(graph)
	ans = [-1]*n
	while len(stack) != 0:
	    v = stack.pop()
	    d = dist[v]
	    nexts = graph[v]
	    for next in nexts:
	        if dist[next] != -1:
	            continue
	        dist[next] = d + 1
	        ans[next] = v
	        stack.append(next)
	if -1 in ans:
		print("No")
	else:
		print("Yes")
		for i in range(1, n):
			print(ans[i]+1)

	


main()

Submission status: Wrong Answer

Solution code:
import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, item):
        heapq.heappush(self.heap, item)

    def pop(self):
        return heapq.heappop(self.heap)

    def __len__(self):
        return len(self.heap)


n, m = [int(i) for i in input().split()]
V_ds = [None, 0] + [10**10] * (n-1)
V_prevs = [None] * (n+1)
class V:
    def __init__(self, idx):
        self.idx = idx
        # self.d = 10**10 if idx != 1 else 0
        # self.prev = None

    def __lt__(self, other):
        return V_ds[self.idx] < V_ds[other.idx]

raw_edges = [[int(i) for i in input().split()] for i in range(m)]
edges = {i: [] for i in range(1, n+1)}
for i, j in raw_edges:
    edges[i].append(j)
    edges[j].append(i)

Q = PriorityQueue()

for i in range(1, n+1):
    Q.push(V(i))
while len(Q):
    u = Q.pop()

    for d in edges[u.idx]:
        if V_ds[d] > V_ds[u.idx] + 1:
            V_ds[d] = V_ds[u.idx]+ 1
            V_prevs[d] = u.idx

ans = V_prevs[2:]
if None in ans:
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def dfs(u):
    st = [u]
    cv = [0] * n
    while st:
        u = st.pop()
        for nxt in adj[u]:
            if cv[nxt]:
                continue
            cv[u] = 1
            if parent[nxt] == -1:
                parent[nxt] = u
            st.append(nxt)


n, m = [int(item) for item in input().split()]
parent = [-1] * n
parent[0] = 0
adj = defaultdict(list)
for i in range(m):
    u, v = [int(item) - 1 for item in input().split()]
    adj[u].append(v)
    adj[v].append(u)
dfs(0)
# print(parent, adj)
if -1 in parent:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(parent[i] + 1)

Submission status: Wrong Answer

Solution code:
def dijkstra(s, n, w, cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j], d[v]+cost[v][j])
    return d[0]


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

cost = [[float("inf") for i in range(n)] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    cost[a - 1][b - 1] = 1
    cost[b - 1][a - 1] = 1
ans = []
for i in range(1, n):
    ans += [dijkstra(i, n, m, cost)]
if float('inf') not in ans:
    print('Yes')
    for i in ans:
        print(i)
else:
    print('No')

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)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
ans=[0]*(n+1)
while len(q)!=0:
  v=q.pop()
  for u in g[v]:
    if check[u]==0:
      check[u]=1
      ans[u]=v
      q.append(u)
print('Yes')
for i in range(2,n+1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
node = [[0 for _ in range(n)] for _ in range(n)]
ans=[0 for _ in range(n)]
L=[]
for _ in range(m):
    a,b = map(int,input().split())
    node[a-1][b-1] = 1
    node[b-1][a-1] = 1
for i in range(n):
    if node[i][0] == 1:
        ans[i] = 1
        node[i][0] = 0
        node[0][i] = 0
        L.append(i)
while L:
    for i in L:
        tmp=[]
        for j in range(n):
            if node[j][i] == 1 and ans[j]==0:
                ans[j] = i + 1
                node[j][i] = 0
                node[i][j] = 0
                tmp.append(j)
        L=tmp
if ans.count(0)!=1:
    print('No')
else:
    for i in range(n):
        if i==0:
            print('Yes')
        else:
            print(ans[i])

Submission status: Wrong Answer

Solution code:
import networkx as nx
x,y= list(map(int, input().split()))
G = nx.Graph()
lis=[0]*(x-1)
for i in range(y):
    j,k= list(map(int, input().split()))
    G.add_edge(j-1,k-1)
for j in range(x-1):
    z=nx.dijkstra_path_length(G,0,j+1)
    lis[j]=z

if 0 in lis:
    print("No")
else:
    print("Yes")
    for j in range(len(lis)):
        print(lis[j])

Submission status: Wrong Answer

Solution code:
#from collections import deque
n,m=map(int,input().split())
root=[[] for _ in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	root[a-1].append(b-1)
	root[b-1].append(a-1)
times=[0]*n
sign=[-1]*n
sign[0]=0
#q=deque(root[0])
flag=0
a=root[0]
b=[]
f=False
while True:
	for i in a:
		if sign[i]==-1:
			sign[i]=flag
			b.extend(root[i])
			f=True
	flag=i
	a=b
	b=[]
	if f==False:
		break
	f=False
for i in range(n-1):
	print(sign[i+1]+1)

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 = defaultdict(int)
visited = defaultdict(int)
level = 0
while queue:
    temp = []
    while queue:
        x = queue.pop()
        visited[x] = 1
        for neighbour in graph[x]:
            if not visited[neighbour]:
                mini_passage[neighbour] = x
                temp.append(neighbour)
    queue = temp.copy()
    level += 1

if len(mini_passage)!=n-1:
    print("No")
else:
    print("Yes")
    for key in range(2,n+1):
        print(mini_passage[key])

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


n,m=mp()
step=[-1]*(n+1)
ans=[-1]*(n+1)
edge=[[i] for i in range(n+1)]
for i in range(m):
    a,b=mp()
    edge[a].append(b)
    edge[b].append(a)


que=deque()
que.append(edge[1])
step[1]=0
while len(que):
    q=que.popleft()
    for i in range(1,len(q)):
        if step[q[i]]==-1:
            step[q[i]]=0
            ans[q[i]]=q[0]
            que.append(edge[q[i]])
print("Yes")
print(ans)
for i in range(2,n+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
P=[[] for i in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  P[a].append(b)
  P[b].append(a)
#AB=[list(map(int,input().split())) for i in range(M)]
ans=[0]*N
con=set()
now=[1]
while now!=[]:
  _now=[]
  for n in now:
    for p in P[n]:
      if p in con:
        continue
      ans[p-1]=n
      _now.append(p)
      con.add(p)
    #con.add(n)
  now=_now
print('yes')
for a in ans[1:]:
  print(a)

Submission status: Wrong Answer

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

d=[n+1 for i in range(n+1)]
d[1]=0
for i in range(1,n+1):
  for j in range(m):
    if l[j][0]==i:
      d[i]=min(d[i],d[l[j][1]]+1)
    if l[j][1]==i:
      d[i]=min(d[i],d[l[j][0]]+1)
      
      
j="Yes"
for i in range(2,n+1):
    if d[i]==n+1:
        j="No"
print("j")
for i in range(2,n+1):
  print(d[i])

Submission status: Wrong Answer

Solution code:


import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N, M = map(int, input().split())
G = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)


q = deque()

# 0 を頂点とする
ans = [-1 for _ in range(N)]
ans[0] = 0
q.append(0)

while q:
    v = q.popleft()
    for u in G[v]:
        if ans[u] != -1:
            continue
        ans[u] = v + 1
        q.append(u)

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

Submission status: Wrong Answer

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

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

ans = [0 for _ in range(n-1)]
looked = [1 for _ in range(n)]
queue = [0]
looked[0] = 0
can = [[] for _ in range(n)]

for i in range(m):
    can[a[i]].append(b[i])
    can[b[i]].append(a[i])

while(len(queue)):
    now = queue.pop(0)
    for i in can[now]:
        if looked[i]:
            queue.append(i)
            looked[i] = 0
            ans[i-1] = now+1
print("\n".join(list(map(str,ans))))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
B = []
for m in range(M):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
from collections import defaultdict as ddict
route = ddict(list)
for i in range(M):
    route[A[i]].append(B[i])
    route[B[i]].append(A[i])
for i in range(1,N+1):
    if route[i] == []:
        print("No")
        exit()
ans = [0 for i in range(N+1)]
from collections import deque
Q = deque([1])
while Q:
    q = Q.popleft()
    for r in route[q]:
        if ans[r] == 0:
            ans[r] = q
            Q.append(r)
print(*ans[2:],sep="\n")

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split())
    graph = {}
    for i in range(n):
        graph[i+1]=[]
    for i in range(m):
        a,b = map(int,input().split())
        graph[a]+=[b]
        graph[b]+=[a]
    dist = [-1 for i in range(n)]
    dist[0]=0
    que = [1]
    while len(que)>0:
        q = que.pop(0)
        for v in graph[q]:
            if dist[v-1]!=-1:
                continue
            dist[v-1] = dist[q-1]+1
            que.append(v)
    Dist = {}
    for i in range(n):
        if dist[i] not in Dist.keys():
            Dist[dist[i]] = [i+1]
        else:
            Dist[dist[i]] += [i+1]
    ans = []
    for i in range(1,n):
        c = list(set(Dist[dist[i]-1]) & set(graph[i+1]))
        print(Dist[dist[i]-1],graph[i+1])
        if len(c)>0:
            ans.append(c[0])
        else:
            print('No')
            return
    print('Yes')
    for i in range(n-1):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
tr=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)
print(tr)
ans=[-1]*N
q=deque([0])
v=[True]*N
x=[True]*N
while q:
    t=q.popleft()
    if v[t]:
        v[t]=False
        for j in tr[t]:
            if x[j]:
                x[j]=False
                ans[j]=t
                q.append(j)
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())

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

list_step = [-1] * N
list_step[0] = 0
queue = deque([0])
while len(queue) > 0:
    parent = queue.popleft()
    cost = list_step[parent]
    for i in range(len(list_road[parent])):
        tmp = list_road[parent][i]
        if list_step[tmp] == -1:
            list_step[tmp] = cost+1
            queue.append(tmp)

if -1 in list_step:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(list_step[i])