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: Accepted

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())
    rooms = list([] for _ in range(n))

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

        rooms[a-1].append(b-1)
        rooms[b-1].append(a-1)
    
    q = deque()
    q.append(0)

    dist = [False for _ in range(n)]
    dist[0] = 0

    while len(q):
        now = q.popleft()

        for nextRoom in rooms[now]:
            if dist[nextRoom] != False:
                continue
            else:
                dist[nextRoom] = now + 1
                q.append(nextRoom)
    
    if False not in dist:
        dist[0] = 'Yes'

        for i in range(len(dist)):
            if i == 0:
                print(dist[i])
            else:
                print(dist[i])
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math
import collections
import fractions
import itertools

def solve():
    n, m = map(int, input().split())
    cave = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n)]
    for i in cave:
        g[i[0]-1].append(i[1])
        g[i[1]-1].append(i[0])
    que = collections.deque()
    ans = [-1]*n
    que.append(1)
    ans[0] = 0
    while(len(que)!=0):
        state = que.popleft()
        for i in g[state-1]:
            if ans[i-1] == -1:
                ans[i-1] = state
                que.append(i)
    if -1 in ans:
        print("No")
    else:
        print("Yes")
        for i in range(1,n):
            print(ans[i])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited
 
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda n: int(n) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
visited = bfs(graph, N, 0)[1:]
if all(visited):
    print("Yes")
    print(*visited, sep="\n")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque
N,M,*AB=map(int,open(0).read().split())
to=[[] for _ in range(N)]
for a,b in zip(*[iter(AB)]*2):
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[None]*N
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
print("Yes",*r[1:],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[None]*N
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
print('Yes')
print('\n'.join(map(str,r[1:])))

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[None]*N
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
print("Yes",*r[1:],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[-1]*N
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i]==-1:
      q.append(i)
      r[i]=x+1
print("Yes",*r[1:],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[None]*N
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
print("Yes",*r[1:],sep="\n")

Submission status: Accepted

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

q=deque([0])
r=[None]*N
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
      
print('Yes')
for i in range(N):
  if r[i]!=0:
    print(r[i])

Submission status: Accepted

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

q=deque([0])
r=deque([None]*N)
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
      
print('Yes')
r.popleft()
for i in range(N-1):
  print(r.popleft())

Submission status: Accepted

Solution code:
from collections import deque
import sys


INF = float('inf')


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 = [[] 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
        ans = [0] * len(self.graph)

        while queue:
            now = queue.popleft()
            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)

    bfs_res, ans = g.bfs(0)
    for d in bfs_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: Accepted

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
        ans = [0] * len(self.graph)

        while queue:
            now = queue.popleft()
            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 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)

    bfs_res, ans = g.bfs(0)
    for d in bfs_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: Accepted

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

adjacent_list = [[] for _ 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)

signs = [-1 for _ in range(n + 1)]

que = deque()
que.append(1)

while que:
    node = que.popleft()
    for i in adjacent_list[node]:
        if signs[i] == -1:
            que.append(i)
            signs[i] = node


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

Submission status: Accepted

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(pre[i])

Submission status: Accepted

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()
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if -1 in bfs.dist[1:]:
        print('No')
    else:
        print('Yes')
        for _ in bfs.dist[1:]:
            print(_)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
to = [[] for i in range(N+1)]
#dist = [100001 for i in range(N+1)]
flug = [0 for i in range(N+1)]

to[0].append(1)
#dist[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

q = deque([0])
while (len(q) != 0):
    i = q.popleft()
    for j in to[i]:
        if flug[j] == 0:
#            dist[j] = dist[i] +1
            flug[j] = i
            q.append(j)

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

Submission status: Accepted

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

to = [[] for i in range(N+1)]

dist = [100001 for i in range(N+1)]
flug = [1 for i in range(N+1)]

to[0].append(1)
dist[0] = 0
flug[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

q = []
q.append(0)
while (len(q) != 0):
    i = q.pop(0)
    for j in to[i]:
        if dist[j] == 100001:
            dist[j] = dist[i] +1
            flug[j] = i
            q.append(j)

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

Submission status: Accepted

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

# G[i] = 部屋iとつながっている部屋のリスト
G = [[] for i in range(n)]

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

# 部屋1までの距離
dist = [-1] * n
dist[0] = 0
# 前の部屋番号
pre = [-1] * n

# 検査対象
q = deque()
q.append(0)

while len(q) != 0:
    V = q.popleft()
    for v in G[V]:
        if pre[v] == -1:
            dist[v] = dist[V] + 1
            pre[v] = V
            q.append(v)

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

Submission status: Accepted

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

n, m = map(int, input().split())
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

from collections import deque

def bfs(graph, queue, dist, prev):
    while queue:
        current = queue.popleft()

        for c in graph[current]:
            if dist[c] != -1:
                continue
            dist[c] = dist[current] + 1
            prev[c] = current
            queue.append(c)

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

bfs(graph, queue, dist, prev)
if -1 in prev:
    print('No')
else:
    print('Yes')
    for n in prev[2:]:
        print(n)

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
INF = 114514191981036436433-4

r = [[] for _ in range(n)]
aa,bb = [] , []

for i in range(m):
    a,b = map(int,input().split())
    aa.append(a-1)
    bb.append(b-1)
    r[a-1].append(b-1)
    r[b-1].append(a-1)
    
q = deque()
q.append(0)
d = [INF]*n
d[0] = 0

while q:
    p = q.popleft()
    for i in r[p]:
        if d[i] == INF:
            q.append(i)
            
        d[i] = min(d[p] + 1 , d[i])
    
ans = [0]*n
for i in range(m):
    if d[aa[i]] - d[bb[i]] == 1:
        ans[aa[i]] = bb[i] + 1
    elif d[bb[i]] - d[aa[i]] == 1:
        ans[bb[i]] = aa[i] + 1
        
print("Yes")
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
def solve(n, m, a, b):
    V = [i+1 for i in range(n)]
    E = {v: [] for v in V}
    for i in range(m):
        E[a[i]].append(b[i])
        E[b[i]].append(a[i])
    parent = {}
    que = [1]
    while que:
        s = que.pop(0)
        for t in E[s]:
            if not t in parent:
                parent[t] = s
                que.append(t)
    if len(parent) < n - 1:
        ans = ["No"]
    else:
        ans = ["Yes"] + [str(parent[v]) for v in range(2,n+1)]
    return "\n".join(ans)

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())
print(solve(n, m, a, b))

Submission status: Accepted

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

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

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

que = deque([])
que.append(0)

f_inf = float("inf")
dist = [f_inf for _ in range(n)]
dist[0] = 0

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

while que:
    v = que.popleft()
    for u in to[v]:
        if dist[u] != f_inf: continue
        dist[u] = dist[v] + 1
        pre[u] = v
        que.append(u)

print("Yes")
for i in range(n):
    if i == 0: continue
    ans = pre[i]
    ans += 1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b)
    g[b-1].append(a)
q=deque()
q.append(1)
check=[0]*n
check[0]=1
ans=[0]*n
while len(q)!=0:
    v=q.popleft()
    for u in g[v-1]:
        if check[u-1]==0:
            check[u-1]=1
            ans[u-1]=v
            q.append(u)
print("Yes")
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)] #Ex.ab = [[A1,B1],[A2,B2],…[]]
 
ans = [-1 for _ in range(n)] # 道標を記録。最後にこれを出力。
ans[0] = 0
tree = [[] for _ in range(n)] # 部屋間のつながりを記録
for a, b in ab:
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
#　Ex.　tree = [[2,4][3]…[]]

q = deque([0]) #キュー。次に探索する部屋を記録していく。最初は0が格納。
while q: #キューが空になれば終了。
    p = q.popleft() #キューなので左から取り出す。
    for i in tree[p]:
        if ans[i] < 0: # visit[i] >= 0なら既に探索しているので無視。
            ans[i] = p
            q.append(i) #新たにキューに加える。

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ans = [-1 for _ in range(n)]
ans[0] = 0
tree=[[]for _ in range(n)]
for a,b in ab:
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
visited={0}
q=[0]
for i in q:
    for j in tree[i]:
        if ans[j] < 0:
            q.append(j)
            ans[j]=i+1
print("Yes")
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
import queue

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

a = []
b = []

for i in range(m):
	s, t = map(int, input().split())
	a.append(s-1)
	b.append(t-1)

#各部屋から行ける部屋
c = [[] for i in range(n)]

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

q = queue.Queue()
q.put(0)

#部屋1からの距離
inf = 10**8
d = [inf]*n
d[0] = 0
ans = [0]*n

while not q.empty():
	x = q.get()
	for i in c[x]:
		if d[i]==inf:
			q.put(i)
			d[i] = d[x]+1
			ans[i] = x+1

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  g[a-1].append(b)
  g[b-1].append(a)
q=deque()
q.append(1)
check=[0]*n
check[0]=1
ans=[0]*n
while len(q)!=0:
  v=q.popleft()
  for u in g[v-1]:
    if check[u-1]==0:
      check[u-1]=1
      ans[u-1]=v
      q.append(u)
print("Yes")
for i in range(1,n):
  print(ans[i])

Submission status: Accepted

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)

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('Yes')
for x in range(2,n+1):
    print(d[x])

Submission status: Accepted

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

class Room:
    sign = -1
    distance = -1
    def __init__(self):
        self.connected = set()
    def print(self, no: str):
        print(f"{no}: sign={self.sign} dist={self.distance} / {self.connected}")

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

Rooms = []
for i in range(N+1):
    Rooms.append(Room())

for i in range(M):
    (A, B) = map(int, input().split(" "))
    Rooms[A].connected.add(B)
    Rooms[B].connected.add(A)

Rooms[0].distance = 0
Rooms[1].distance = 0
target = [1]

while(len(target)):
    new_target = []
    for t in target:
        for c in Rooms[t].connected:
            if Rooms[c].distance == -1 or Rooms[t].distance + 1 < Rooms[c].distance:
                Rooms[c].sign = t
                Rooms[c].distance = Rooms[t].distance + 1
                new_target.append(c)
    target = list(set(new_target))

if all([r.distance != -1 for r in Rooms]):
    print("Yes")
    for i in range(2, N+1):
        print(Rooms[i].sign)
else:
    print("No")

Submission status: Accepted

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
 
g=nx.Graph() #無向グラフ
g.add_edges_from(s) #リストsを参照して頂点（部屋）の追加
di=nx.predecessor(g,source=1)#1から全点までの最短路におけるその点の前の点を表示
 
print("Yes")
for x in range(2,n+1):
      print(di[x][0])

Submission status: Accepted

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
mem[1] = -1
while not q.empty():
    v = q.get()
    for vv in adj[v]:
        if mem[vv] != 10 ** 6: continue
        mem[vv] = v
        q.put(vv)
 
if 10 ** 6 in mem[2:]:
    print('No')
else:
    print('Yes', *mem[2:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
rooms = [[] for i in range(n + 1)]

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

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

while q:
    rnum = q.popleft()
    for i in rooms[rnum]:
        if signs[i] == -1:
            signs[i] = rnum
            q.append(i)

print("Yes")

for i in signs[2:]:
    print(i)

Submission status: Accepted

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.popleft()
 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: Accepted

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(0)
    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: Accepted

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

adj = [[] for _ in range(n)]

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

from collections import deque
q = deque()

dist = [False] * n
ans = [0] * n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] == True:continue
        dist[to] = True
        q.append(to)
        ans[to] = now

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
d=[set() for _ in range(n)]

for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d[a].add(b)
  d[b].add(a)
dist=[-1]*n
dist[0]=0
prev=[-1]*n
queue=deque()
queue.append(0)

while queue:
  q=queue.popleft()
  for next in d[q]:
    if dist[next]!=-1:
      continue
    dist[next]=dist[q]+1
    prev[next]=q
    queue.append(next)

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n+1)]
    for i in range(m):
        a,b=map(int,readline().split())
        G[a].append(b)
        G[b].append(a)

    ans=[0]*(n+1)
    flags=[False]*(n+1)
    flags[1]=True
    d=deque([1])
    while len(d)>0:
        now=d.popleft()
        v=now
        for u in G[v]:
            if flags[u]==False:
                flags[u]=True
                ans[u]=v
                d.append(u)

    print("Yes")
    for i in range(2,n+1):
        print(ans[i])
        
if __name__=="__main__":
    main()

Submission status: Accepted

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.popleft()
 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: Accepted

Solution code:
n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
br = [0 for i in range(n)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
cr = [0]
dr = []
for r in cr:
    for i in ar[r]:
        if br[i] == 0:
            br[i] = r + 1
            cr.append(i)
print("Yes")
for i in range(1,n):
    print(br[i])

Submission status: Accepted

Solution code:
import queue
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 = queue.Queue()
q.put(0)
while not q.empty():
  p = q.get()
  s = E[p]
  for i in s:
    if V[i] < 0:
      V[i] = p
      q.put(i)
#print(V)
print("Yes")
for i in range(1, N):
  print(V[i]+1)

Submission status: Accepted

Solution code:
# 1からスタートしてBFS、道しるべのない部屋に到達したら、親の番号を道しるべとして設定する

import sys
readline = sys.stdin.readline

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

from collections import deque
q = deque([])
q.append([0,-1])
ans = [-1 for i in range(N)]
while q:
  v,parent = q.popleft()
  if ans[v] != -1:
    continue
  ans[v] = parent + 1
  for child in G[v]:
    if child == parent:
      continue
    q.append([child,v])

for i in range(1,len(ans)):
  if ans[i] == -1:
    print("No")
    exit(0)
print("Yes")
for i in range(1,len(ans)):
  print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

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

g = [[] for i in range(N)]

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

visited = [-1] * N
q = deque([0])

while q:
  p = q.popleft()
  for node in g[p]:
    if visited[node] == -1:
      visited[node] = p + 1
      q.append(node)

print ('Yes')
print ('\n'.join(map(str, visited[1:])))

Submission status: Accepted

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

b = [[] for i in range(n)]
for i in range(m):
    a=list(map(int,input().split()))
    b[a[1]-1].append(a[0])
    b[a[0]-1].append(a[1])
    
c = [-1 for i in range(n)]
c[0] = 0
q = deque([1])
now = 0
count = 0
while q:
    #print(c,q, now)
    count = count + 1
    if count > n:
        print("No")
        exit()
    now = q.popleft() - 1
    for i in range(len(b[now])):
        #count = count + 1
        #print(now+1, "=>", b[now][i])
        if c[b[now][i] - 1] == -1:
            q.append(b[now][i])
            c[q[-1] - 1] = now + 1
            #print(c)
            
#print(count)
print("Yes")
for i in range(1,len(c)):
    print(c[i])

Submission status: Accepted

Solution code:
from collections import deque
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 = deque([])
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.popleft()
        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: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
candidate = [[] for i in range(n)]
parent = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    candidate[a].append(b)
    candidate[b].append(a)
q = deque([0])
visited = [False] * n
visited[0] = True
while len(q) > 0:
    v = q.popleft()
    for i in candidate[v]:
        if visited[i]:
            continue
        visited[i] = True
        parent[i] = v
        q.append(i)
print("Yes")
for i in range(1, n):
    print(parent[i]+1)