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:
import time
from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)] #各node(index)から繋がるnode(value)
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [0 for i in range(N+1)]
    q = deque([1])
    visited = []
    while q:
        node = q.popleft()
        visited.append(node)
        for e in edge[node]:
            if signpost[e] == 0:
                signpost[e] = node
                q.append(e)
    print('Yes')
    for i in signpost[2:]:
        print('{:.1g}'.format(i))        

if __name__ == "__main__":
    s = time.time()
    main()
    e = time.time()
    print(e-s)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))


INF = float('inf')


class Graph:
    def __init__(self, n, is_directed=False):
        self.graph = [[] for _ in range(n)]
        self.is_directed = is_directed

    def add_edge(self, u, v):
        """頂点uから頂点vに辺を作る
        無向グラフの場合、uからvの方向の辺のみを記録する
        """
        self.graph[u].append(v)
        if not self.is_directed:
            self.graph[v].append(u)

    def bfs(self, start):
        """幅優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [INF] * len(self.graph)
        queue = deque([start])
        distances[start] = 0

        while queue:
            now = queue.popleft()
            for to in self.graph[now]:
                if distances[to] != INF:
                    continue
                queue.append(to)
                distances[to] = distances[now] + 1
        return distances

    def dfs(self, start):
        """幅優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [INF] * len(self.graph)
        queue = deque([start])
        distances[start] = 0
        ans = [0] * len(self.graph)

        while queue:
            now = queue.pop()
            for to in self.graph[now]:
                if distances[to] != INF:
                    continue
                queue.append(to)
                # 前の頂点からこの頂点に対する道標を建てる
                ans[to] = now
                distances[to] = distances[now] + 1
        return distances, ans


def main():
    n, m = LI()
    g = Graph(n)
    for _ in range(m):
        a, b = LI()
        a, b = a - 1, b - 1
        g.add_edge(a, b)
    dfs_res, ans = g.dfs(0)
    for d in dfs_res:
        if d == INF:
            print('No')
            return
    print('Yes')
    print(*map(lambda x: x + 1, ans[1:]), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))


INF = float('inf')


class Graph:
    def __init__(self, n, is_directed=False):
        self.graph = [[] for _ in range(n)]
        self.is_directed = is_directed

    def add_edge(self, u, v):
        """頂点uから頂点vに辺を作る
        無向グラフの場合、uからvの方向の辺のみを記録する
        """
        self.graph[u].append(v)
        if not self.is_directed:
            self.graph[v].append(u)

    def bfs(self, start):
        """幅優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [INF] * len(self.graph)
        queue = deque([start])
        distances[start] = 0

        while queue:
            now = queue.popleft()
            for to in self.graph[now]:
                if distances[to] != INF:
                    continue
                queue.append(to)
                distances[to] = distances[now] + 1
        return distances


def main():
    n, m = LI()
    g = Graph(n)
    for _ in range(m):
        a, b = LI()
        a, b = a - 1, b - 1
        g.add_edge(a, b)
    bfs_res = g.bfs(0)
    for d in bfs_res:
        if d == INF:
            print('No')
            return
    print('Yes')
    print(*bfs_res[1:], sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))


class Graph:
    def __init__(self, n, is_directed=False):
        self.graph = [deque([]) for _ in range(n)]
        self.is_directed = is_directed

    def add_edge(self, u, v):
        """頂点uから頂点vに辺を作る
        有向グラフ出ない場合、uからvの方向の辺のみを記録する
        """
        self.graph[u].append(v)
        if not self.is_directed:
            self.graph[v].append(u)

    def bfs(self, start):
        """幅優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [float('inf') for _ in range(len(self.graph))]
        visited = [False for _ in range(len(self.graph))]
        queue = deque([start])
        visited[start] = True
        distances[start] = 0
        distance_from_start = 1

        while queue:
            v = queue.popleft()
            # print(f'pop v: {v}')
            for i in self.graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
                    distances[i] = min(
                        distances[i], distance_from_start)
            distance_from_start += 1
        return distances

    def dfs(self, start):
        """深さ優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [float('inf') for _ in range(len(self.graph))]
        visited = [False for _ in range(len(self.graph))]
        stack = deque([start])
        visited[start] = True
        distances[start] = 0
        distance_from_start = 1

        while stack:
            v = stack.pop()
            # print(f'pop:{v}')
            for i in self.graph[v]:
                if not visited[i]:
                    stack.append(i)
                    visited[i] = True
                    distances[i] = min(
                        distances[i], distance_from_start)
            distance_from_start += 1
        return distances


def main():
    n, m = LI()
    g = Graph(n)
    for _ in range(m):
        a, b = LI()
        g.add_edge(a - 1, b - 1)
    # print(f'{g.graph=}')
    # bfs_res = g.bfs(0)
    # print(f'{bfs_res=}')
    dfs_res = g.dfs(0)
    for d in dfs_res:
        if d == float('inf'):
            print('No')
            return
    print('Yes')
    print(*dfs_res[1:], sep='\n')
    # print(f'{dfs_res=}')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))


class Graph:
    def __init__(self, n, is_directed=False):
        self.graph = [deque([]) for _ in range(n)]
        self.is_directed = is_directed

    def add_edge(self, u, v):
        """頂点uから頂点vに辺を作る
        有向グラフ出ない場合、uからvの方向の辺のみを記録する
        """
        self.graph[u].append(v)
        if not self.is_directed:
            self.graph[v].append(u)

    def bfs(self, start):
        """幅優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [float('inf') for _ in range(len(self.graph))]
        visited = [False for _ in range(len(self.graph))]
        queue = deque([start])
        visited[start] = True
        distances[start] = 0
        distance_from_start = 1

        while queue:
            v = queue.popleft()
            # print(f'pop v: {v}')
            for i in self.graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
                    distances[i] = min(
                        distances[i], distance_from_start)
            distance_from_start += 1
        return distances

    def dfs(self, start):
        """深さ優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [float('inf') for _ in range(len(self.graph))]
        visited = [False for _ in range(len(self.graph))]
        stack = deque([start])
        visited[start] = True
        distances[start] = 0
        distance_from_start = 1

        while stack:
            v = stack.pop()
            # print(f'pop:{v}')
            for i in self.graph[v]:
                if not visited[i]:
                    stack.append(i)
                    visited[i] = True
                    distances[i] = min(
                        distances[i], distance_from_start)
            distance_from_start += 1
        return distances


def main():
    n, m = LI()
    g = Graph(n)
    for _ in range(m):
        a, b = LI()
        g.add_edge(a - 1, b - 1)
    # print(f'{g.graph=}')
    # bfs_res = g.bfs(0)
    # print(f'{bfs_res=}')
    dfs_res = g.dfs(0)
    print('Yes')
    print(*dfs_res, sep='\n')
    # print(f'{dfs_res=}')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
nm = list(map(int,input().split()))
n = nm[0]
m = nm[1]
a = []
b = []
for i in range(0, m):
    ab = list(map(int,input().split()))
    a.append(ab[0])
    b.append(ab[1])
signs = [0]*(n+1)
signs[1]=-1
now = [1]
nexx = []
while True:
    for i in now:
        for j in range(0,m):
            if a[j] == i:
                if signs[b[j]] == 0:
                    signs[b[j]] = i
                    nexx.append(b[j])
            elif b[j] == i:
                if signs[a[j]] == 0:
                    signs[a[j]] = i
                    print("signs=",signs)
                    nexx.append(a[j])
    now=nexx.copy()
    if len(nexx)==0:
        break
    nexx = []
flag = 0
for i in range(1, n):
    if signs[i]==0:
        print("No")
        flag = 1
        break
if flag == 0:
    print("Yes")
    for k in range(2,n+1):
        print(signs[k])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)#どこの点がどことつながっているか
pre = [-1] * (n+1)
dist = [-1] * (n+1)
dist[1] = 0
que = deque([1])

while que:
    now = que.popleft()#1取り出す。queはから
    for i in adjacent_list[now]:
        if pre[i] == -1:#訪問していない
            que.append(i)
            dist[i] = dist[now] + 1
            pre[i] = now
print("Yes")
for i in range(2,n+1):
    print(dist[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)#どこの点がどことつながっているか
print(adjacent_list)
pre = [-1] * (n+1)
dist = [-1] * (n+1)
dist[1] = 0
que = deque([1])

while que:
    now = que.popleft()#1取り出す。queはから
    for i in adjacent_list[now]:
        if pre[i] == -1:#訪問していない
            que.append(i)
            dist[i] = dist[now] + 1
            pre[i] = now
print("Yes")
for i in range(2,n+1):
    print(dist[i])

Submission status: Wrong Answer

Solution code:
import sys

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

work = []
a = []
d = [[0] * 2 for i in range(m)]
cnt = n - 1
cnt2 = 0
for i in range(cnt):
  a.append(0)


for i in range(m):
  b,c = map(int,input().split())
  if b == 1:
    work.append(c)
    a[c - 2] = 1
    cnt2 += 1
  if c == 1:
    work.append(b)
    a[b - 2] = 1
    cnt2 += 1
  d[i][0] = b
  d[i][1] = c
  
for i in work:
  for j in range(m):
    if d[j][0] == i:
      work.append(d[j][1])
      if a[(d[j][1] - 2)] == 0 or a[(d[j][1] - 2)] > i:
        a[(d[j][1] - 2)] = i
    if d[j][1] == i:
      work.append(d[j][0])
      if a[(d[j][0] - 2)] == 0 or a[(d[j][0] - 2)] > i:
        a[(d[j][0] - 2)] = i
  cnt2 += 1
  if cnt2 == n:
    break
        
for i in a:
  if i == 0:
    print("No")
    print(a)
    sys.exit()

print("Yes")
for i in a:
  print(i)

Submission status: Wrong Answer

Solution code:
import collections
import sys

def create_graph(n, l):
    '''
    先に作成した行列を参照して、部屋(ノード)をつなぐグラフを作成する
    '''
    g = {i:[] for i in range(1, n + 1)}

    for a, b in l:
        g[a].append(b)
        g[b].append(a)

    return g

def bfs(n, g):
    '''
    幅優先探索の実装
    '''
    navi = [0] * (n + 1) # 隣接リストの要素を探索したかどうかをカウントする道しるべリスト(グラフの大きさだけの配列, 0で初期化)
    navi[1] = -1 # 部屋1の道しるべを-1で更新

    q = collections.deque() # キューを初期化
    q.append(1) # キューの末尾に1を追加
    while len(q) > 0: # キューに要素がある限りループ
        cp = q.popleft() # キューから現在地を取り出す, popleftでキューの先頭を削除
        np = g[cp] # 現在地の隣接リストをグラフから取り出す

        for i in np: # 隣接リスト内の要素に対してループ
            if navi[i] == 0: # そこが未探索の場合
                navi[i] = cp # 対応するnaviに現在地を格納して
                q.append(i) # キューの末尾に添字を追加

    print(q)

    return navi

if __name__ == '__main__':
    sys.setrecursionlimit(10**6) # 再起回数の上限を設定

    N, M = map(int, input().split()) # N, Mを標準入力
    L = [list(map(int, input().split())) for _ in range(M)] # 標準入力で[A, B]をリストに格納、行列にする

    G = create_graph(N, L) # グラフを作成
    for i in range(1, len(G)):
        if len(G[i]) == 0: # グラフに空が存在すれば
            print('No') # Noを出力して終わり
            sys.exit(1)

    navi = bfs(N, G) # 幅優先探索を行い、各ノードをどれだけ訪れたかをカウントしたリストを返す

    if min(navi[2:]) == 0: # 部屋2以降で道しるべが更新されていないときは
        print('No') # Noを出力
    else:
        print('Yes') # そうでないときはYesを出力して
        for i in navi[2:]: # 部屋2以降の道しるべを出力
            print(i)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 1つ前の部屋(1-indexed)
        self.dist = [-1]*self.N
        self.que = deque()

        # 初期条件(0-indexed)
        self.dist[0] = 0
        self.que.append(0)

    def bfs(self):
        while self.que:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = v+1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    con = [[] for i in range(N)]
    for A,B in A_B_arr:
        A -= 1
        B -= 1
        con[A].append(B)
        con[B].append(A)

    bfs = BFS(con)
    bfs.bfs()

    print(bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if -1 in bfs.dist[1:]:
        print('No')
    else:
        print('Yes')
        for _ in bfs.dist[1:]:
            print(_)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edge = [[0 for y in range(N)] for x in range(N)]
for _ in range(M):
  x, y = map(int, input().split())
  edge[x-1][y-1] = 1
  edge[y-1][x-1] = 1

ct = [-1]*N

for i in range(N):
  for j in range(N):
    if edge[i][j] == 1:
      if ct[j] == -1:
        ct[j] = i

print('Yes')
for i in range(1,N):
  print(ct[i]+1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0]*(M+1)
B = [1]*(M+1)
Dist = [1000000]*(N+1)
Flug = [0]*(N+1)
Dist[0] = 0

for i in range(1,M+1):
    c1, c2 =map(int, input().split())
    A[i] = min(c1,c2)
    B[i] = max(c1,c2)

for j in range(N):
    for i in range(M+1):
        if Dist[A[i]] == j and Dist[B[i]] > j:
            Dist[B[i]] = j+1
            Flug[B[i]] = A[i]
        elif Dist[B[i]] == j and Dist[A[i]] > j:
            Dist[A[i]] = j+1
            Flug[A[i]] = B[i]


print('yes')
for i in range(2,N+1):
    print(Flug[i])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0]*(M+1)
B = [1]*(M+1)
Dist = [1000000]*(N+1)
Flug = [0]*(N+1)
Dist[0] = 0



for i in range(1,M+1):
    c1, c2 =map(int, input().split())
    A[i] = min(c1,c2)
    B[i] = max(c1,c2)

for j in range(N):
    for i in range(M+1):
        if Dist[A[i]] == j and Dist[B[i]] > j:
            Dist[B[i]] = j+1
            Flug[B[i]] = A[i]
        elif Dist[B[i]] == j and Dist[A[i]] > j:
            Dist[A[i]] = j+1
            Flug[A[i]] = B[i]


print('yes')
for i in range(1,N+1):
    print(Flug[i])

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np
def main():
    line = input().split(' ')
    N, M = int(line[0]), int(line[1])
    root = np.asarray([list(map(int, input().split(' '))) for i in range(M)])
    #signpost = [0 for i in range(N+1)]
    signpost = np.zeros(N+1)

    mem1 = [1]
    for i in range(M):
        mem2 = []
        for node in root:
            if node[0] in mem1:
                if signpost[node[1]] == 0 and node[1] != 1:
                    signpost[node[1]] = node[0]
                    mem2.append(node[1])
            elif node[1] in mem1:
                if signpost[node[0]] == 0 and node[0] != 1:
                    signpost[node[0]] = node[1]
                    mem2.append(node[0])
        if len(mem2) == 0:
            break
        mem1.clear()
        #list(set(mem2))
        mem1 = copy.copy(mem2)

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
def main():
    line = input().split(' ')
    N, M = int(line[0]), int(line[1])
    root = [list(map(int, input().split(' '))) for i in range(M)]
    signpost = [0 for i in range(N+1)]

    mem1 = [1]
    while True:
        mem2 = []
        for node in root:
            if node[0] in mem1:
                if signpost[node[1]] == 0 and node[1] != 1:
                    signpost[node[1]] = node[0]
                    mem2.append(node[1])
                    root.remove(node)
            if node[1] in mem1:
                if signpost[node[0]] == 0 and node[0] != 1:
                    signpost[node[0]] = node[1]
                    mem2.append(node[0])
                    root.remove(node)
        if len(mem2) == 0:
            break
        mem1.clear()
        list(set(mem2))
        mem1 = copy.copy(mem2)

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

if __name__ == "__main__":
    main()

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)

d = [0] * (n + 1)
q=deque()
q.append(1)

while q:
    v = q.popleft()
    for j in graph[v]:
        if not d[j]:
            q.append(j)
            d[j] = v
print(d)
print('Yes')
for x in range(2,n+1):
    print(d[x])

Submission status: Wrong Answer

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

import math

def nearby(room, pathes):
    r = []
    for path in pathes:
        if path[0] == room:
            r.append(path[1])
        elif path[1] == room:
            r.append(path[0])
    return r



numbers = input().split(" ")

n = int(numbers[0])
m = int(numbers[1])

pathes = []
rooms = [-1] * (n + 1)

for i in range(m):
    numbers = input().split(" ")
    pathes.append([int(numbers[0]), int(numbers[1])])


rooms[0] = 0
rooms[1] = 0

for i in list(range(n+1))[1:]:
    if rooms[i] != -1:
        for j in nearby(i, pathes):
            if rooms[j] == -1:
                rooms[j] = i

if -1 not in rooms:
    print("Yes")
    for i in list(range(n+1))[2:]:
        print(rooms[i])
else:
    print("No")

Submission status: Wrong Answer

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

import math

def nearby(room, pathes):
    r = []
    for path in pathes:
        if path[0] == room:
            r.append(path[1])
        elif path[1] == room:
            r.append(path[0])
    return r



numbers = input().split(" ")

n = int(numbers[0])
m = int(numbers[1])

pathes = []
rooms = [-1] * (n + 1)

for i in range(m):
    numbers = input().split(" ")
    pathes.append([int(numbers[0]), int(numbers[1])])


rooms[0] = 0
rooms[1] = 0

for i in list(range(n+1))[1:]:
    for j in nearby(i, pathes):
        if rooms[j] == -1:
            rooms[j] = i

if -1 not in rooms:
    print("Yes")
    for i in list(range(n+1))[2:]:
        print(rooms[i])
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input():
    return list(map(int, sys.stdin.readline().strip().split()))
 
n, m = input()
mem = [0 for _ in range(n + 1)] # n -> 1 거리
adj = [[] for _ in range(n + 1)]
q = []
 
for i in range(m):
    a, b = input()
    adj[b].append(a)
    adj[a].append(b)
    if b == 1: 
        q.append(a)
        mem[a] = 1
    if a == 1: 
        q.append(b)
        mem[b] = 1
 
visited = []
while q:
    v = q.pop(0)
    if v not in visited:
        visited.append(v)
        for node in adj[v]:
            if node not in visited:
                mem[node] = v
                q.append(n)
 
if 0 in mem[2:]: print('No')
else: print('Yes', *mem[2:], sep='\n')

Submission status: Wrong Answer

Solution code:
import numpy as np

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

G = np.zeros([N + 1])
C = np.zeros([N + 1])

for ab in AB:
    a, b = ab
    G[a] = b
    G[b] = a


def main(keys):
    temp_keys = []
    for key in keys:
        for i in range(2, N + 1):
            if G[key] == i:
                if C[i] == 0:
                    temp_keys.append(i)
                    C[i] = C[key] + 1
    if temp_keys != []:
        main(temp_keys)


main([1])

print('Yes')
temp = 1

for i in range(2, N + 1):
    for j in range(1, N + 1):
        if C[i] - 1 == C[j]:
            print(j)
            temp = C[j]
            break

Submission status: Wrong Answer

Solution code:
def BFS(K,edges,N):
  INF = 10**10
  roots=[ [] for i in range(N)]
  for a,b in edges:
    roots[a-1]+=[b-1]
    roots[b-1]+=[a-1]
  dist=[INF]*N
  pre = [-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i in roots[label]:
      if dist[i]==INF:
        dist[i]=dist[label]+1
        pre[i]=label
        stack+=[i]
  return pre
 
N,M=map(int,input().split())
edges=[]
for i in range(M):
  edges+=[list(map(int,input().split()))]


ans=BFS(0,edges,N)
print("Yes")
for i in range(1,N):
  print(ans[i]+1)

Submission status: Wrong Answer

Solution code:


roomNum, aisleNum = map(int, input().split())

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

distanceFromRoom1 = [-1] * (roomNum+1)
distanceFromRoom1[0] = 0
distanceFromRoom1[1] = 0

from collections import deque
aisleQue = deque(aisles)

while aisleQue:
    aisle = aisleQue.popleft()
    roomleft = aisle[0]
    roomright = aisle[1]

    if distanceFromRoom1[roomleft] == -1 and distanceFromRoom1[roomright] == -1:
        # どちらの部屋も未到達の場合は後回し
        aisleQue.append(aisle)
    elif distanceFromRoom1[roomleft] != -1 and distanceFromRoom1[roomright] != -1:
        # どちらの部屋も到達済みの場合は一方を更新
        if distanceFromRoom1[roomleft]  < distanceFromRoom1[roomright]:
            distanceFromRoom1[roomright] = distanceFromRoom1[roomleft] + 1
        else:
            distanceFromRoom1[roomleft] = distanceFromRoom1[roomright] + 1
    else:
        # 一方は到達済みの場合、未到達の方を更新
        if distanceFromRoom1[roomleft] == -1:
            distanceFromRoom1[roomleft] = distanceFromRoom1[roomright] + 1
        else:
            distanceFromRoom1[roomright] = distanceFromRoom1[roomleft] + 1

if min(distanceFromRoom1) == -1:
    # 到達できない場所がある
    print('No')
else:
    print('Yes')
    for dis in distanceFromRoom1[2:]:
        print(dis)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

n, m = input()
mem = [0 for _ in range(n + 1)] # n -> 1 거리
adj = [[] for _ in range(n + 1)]
q = []

for i in range(m):
    a, b = input()
    adj[b].append(a)
    adj[a].append(b)
    if b == 1: 
        q.append(a)
        mem[a] = 1
    if a == 1: 
        q.append(b)
        mem[b] = 1

visited = []
while q:
    v = q.pop(0)
    if v not in visited:
        visited.append(v)
        for node in adj[v]:
            if node not in visited:
                mem[node] = mem[v] + 1
                q.append(n)

if 0 in mem[2:]: print('No')
else: print('Yes', *mem[2:], sep='\n')

Submission status: Wrong Answer

Solution code:
import sys, queue
def input():
    return list(map(int, sys.stdin.readline().strip().split()))

n, m = input()
mem = [10 ** 6 for _ in range(n + 1)] # n -> 1 거리
adj = [[] for _ in range(n + 1)]
q = queue.Queue()
for i in range(m):
    a, b = input()
    adj[b].append(a)
    adj[a].append(b)
    if b == 1: 
        q.put(a)
        mem[a] = 1
    if a == 1: 
        q.put(b)
        mem[b] = 1

while not q.empty():
    v = q.get()
    for vv in adj[v]:
        if vv == 1 or mem[vv] != 10 ** 6: continue
        mem[vv] = mem[v] + 1
        q.put(vv)

if 10 ** 6 in mem[2:]:
    print('No')
else:
    print('Yes', *mem[2:], sep='\n')

Submission status: Wrong Answer

Solution code:
newarr = input()
newarr = newarr.split()
n = int(newarr[0])
m = int(newarr[1])
dicts = {}
ans = [0] * (n + 1)
for line in range(m):
    newarr = input()
    newarr = newarr.split()
    froom = int(newarr[0])
    sroom = int(newarr[1])
    if froom not in dicts:
        dicts[froom] = []
    if sroom not in dicts:
        dicts[sroom] = []
    dicts[froom].append(sroom)
    dicts[sroom].append(froom)
queue = []
if 1 not in dicts:
    print("No")
else:
    ans[1] = 1
    curarr = dicts[1]
    for i in curarr:
        queue.append(i)
        ans[i] = 1 
    while queue:
        curitem = queue.pop()
        if curitem not in dicts:
            continue 
        curarr = dicts[curitem]
        for i in curarr:
            if ans[i] == 0:
                ans[i] = curitem 
                queue.append(i)

    finalans = []
    flag = 0 
    for i in range(2, n + 1):
        if i == 0 :
            flag = 1 
            break 
        finalans.append(ans[i])
    if flag == 1:
        print("No")
    else:
        print("Yes")
        for i in finalans:
            print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int, input().split())
alist = []
blist = []
T = [ [] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    T[a-1].append(b)
    T[b-1].append(a)
# T[i]にはi+1が接続してる数のリスト
rdic = [0]*(N)
d = deque()
d.append(1)
c = 0
ans = [0]*N
while len(d)>0:
    getlist = T[d[0]-1]
    for i in getlist:
        if i not in rdic:
            rdic[i-1] = d[0]
            d.append(i)
            c+=1
    if c == N-1:
        break
    d.popleft()
print('Yes')
for n in range(2,N+1):
    print(rdic[n-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int, input().split())
alist = []
blist = []
T = [ [] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    T[a-1].append(b)
    T[b-1].append(a)
rdic = [0]*(N)
d = deque()
def find_index(n):
    returnlist = []
    for indexa,i in enumerate(alist):
        if i == n:
            returnlist.append(blist[indexa])
    for indexb,i in enumerate(blist):
        if i == n:
            returnlist.append(alist[indexb])
    return returnlist
d.append(1)
c = 0
ans = [0]*N
while True:
    getlist = T[d[0]-1]
    for i in getlist:
        if i not in rdic:
            rdic[i-1] = d[0]
            d.append(i)
            c+=1
    if c == N-1:
        break
    d.popleft()
print('Yes')
for n in range(2,N+1):
    print(rdic[n-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
 
#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1].append(b)
    l[b-1].append(a)

#深さのリストを作る
l1=sum(l, []) #一次元化
l_depth=list(dict.fromkeys(l1))#深さのリスト

#解の出力
print('Yes')
for i in range(1,n):
    #各部屋の通じてる部屋リストを浅い順にソート
    ll=sorted(l[i], key=lambda data:l_depth.index(data))
    print(ll[0])

Submission status: Wrong Answer

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

#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1].append(b)
    l[b-1].append(a)

#深さのリストを作る
l_depth=[1]
l_depth_sub=[0]*n
l_depth_sub[0]+=1
for i in range(n):
    for j in range(len(l[i])):
        if l_depth_sub[l[i][j]-1]==0:
            l_depth_sub[l[i][j]-1]+=1
            l_depth.append(l[i][j])               
    if l_depth_sub.count(0)==0:break

#解の出力
print('Yes')
for i in range(1,n):
    k=10**9
    for j in range(len(l[i])):
        if l_depth.index(l[i][j])<k:#より浅い部屋へ通じるのなら更新
            k=l_depth.index(l[i][j])
    print(l_depth[k])