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
# N = int(input())
# S = input()
N, M = map(int, input().split())
# A = list(map(int, input().split()))

edge = [[] for _ in range(N + 1)]

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

q = deque([1])
done = [True for _ in range(N + 1)]
done[1] = False

ans = [0 for _ in range(N + 1)]

while q:
    num = q.popleft()
    for e in edge[num]:
        if done[e]:
            ans[e] = num
            done[e] = False
            q.append(e)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def f(data):
    tmp=links[data[0]]
    for x in tmp:
        if ans[x]==-1:
            ans[x]=data[0]
            q.append([x, data[0]])

from collections import deque

N, M=map(int, input().split())
links=[[] for _ in range(N+1)]
for _ in range(M):
    A, B=map(int, input().split())
    links[A].append(B)
    links[B].append(A)
    
q=deque()
q.append([1, -1])#imadoko, dokokara, 
ans=[-1]*(N+1)
ans[0]=0
ans[1]=0
while len(q)>0:
    data=q.popleft()
    f(data)
    
print('Yes')
print(*ans[2:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

n, m = list(map(int, input().split()))
d = defaultdict(list)
for i in range(m):
    data = list(map(int, input().split()))
    d[data[0]].append(data[1])
    d[data[1]].append(data[0])

mindist = defaultdict(lambda: 1000000)
mindist[1] = 0
sign = defaultdict(int)

dq = deque()
dq.append([1, 0])
while len(dq) > 0:
    room, dist = dq.popleft()
    for nroom in d[room]:
        if dist + 1 < mindist[nroom]:
            mindist[nroom] = dist + 1
            sign[nroom] = room
            dq.append([nroom, dist + 1])

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

Submission status: Accepted

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

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

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

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


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

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

Submission status: Accepted

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

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

dp = [-1] * n
from collections import deque
q = deque([])
q.append(0)
dp[0] = 0
while len(q) > 0:
    u = q.popleft()
    for v in edges[u]:
        if dp[v] != -1:continue
        q.append(v)
        dp[v] = u
# print(dp)
for d in dp[1:]:
    if d == -1:
        print("No")
        exit()
print("Yes")
for d in dp[1:]:
    print(d+1)

Submission status: Accepted

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

from collections import deque
Q = deque()
Q.append([0,0])

visited=[-1]*n
visited[0]=1

while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=now+1
        Q.append([nxt,cnt+1])

print("Yes")
for a in visited[1:]:
    print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


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

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

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

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

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

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


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

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

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

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

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


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


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


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

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

Submission status: Accepted

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dijkstra_al(s, n, ALcost, start_index = 0):
    '''
    ダイクストラ法 O(|E|log|V|)
    グラフを隣接リストで表す場合
    始点sから各頂点への最短距離
    n: 頂点の数、s: 始点
    ALcost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    start_index: 0のときvertexは0, 1, ..., n-1
                 1のときvertexは1, 2, ..., n
    '''
    import heapq
    INF = float('inf')

    fixed = [False] * (n + 1) # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * (n + 1)  # 始点sから各頂点への重み
    prev_vertex = [None] * (n + 1) #  各頂点までの最短経路上での１つ前の頂点

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    prev_vertex[s] = None
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, edge_cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + edge_cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))
                prev_vertex[v] = u

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    if start_index == 0:
        return vertex_cost[:n], prev_vertex[:n]
    else:
        return vertex_cost, prev_vertex # index 0はダミー

# 入力
N, M = [int(x) for x in input().split()]
ALcost = [[] for _ in range(N + 1)]
for i in range(M):
    u, v = [int(x) for x in input().split()]
    ALcost[u].append((v, 1))
    ALcost[v].append((u, 1))

print("Yes")
vertex_cost, prev_vertex = dijkstra_al(1, N, ALcost, 1)
for i in range(2, N + 1):
    print(prev_vertex[i])

Submission status: Accepted

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

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

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

from collections import deque

queue = deque([0])
d = [None] * N
d[0] = 0
while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] is None:
            d[i] = v+1
            queue.append(i)

if None in d:
    print('No')
else:
    print('Yes')
    for i in d[1:]:
        print(i)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = [None]*N
ans[0] = 0

stack = deque()
stack.append(0)
while stack:
    x = stack.popleft()
    connected = v[x]
    for u in connected:
        if ans[u] == None:
            ans[u] = x + 1
            stack.append(u)
print('Yes')
print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
way = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    way[a-1].append(b-1)
    way[b-1].append(a-1)
#print(way)
stack = deque([0])
ans = [-1]*n
ans[0] = 0
flag = [True]*n
flag[0] = False
while stack:
    a = stack.pop()
    for i in way[a]:
        if (flag[i]):
            stack.appendleft(i)
            ans[i] = a
            flag[i] = False

if (-1 in ans):
    print("No")
else:
    print("Yes")
    for i in range(n):
        ans[i] += 1
    print(*ans[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
d, check = [0]*n, [0]*n
check[0] = 1
for _ in range(m):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
que = deque([0])
count = 1
while que:
    count += 1
    for i in range(len(que)):
        to = que.popleft()
        for j in range(len(edge[to])):
            if check[edge[to][j]]: continue
            check[edge[to][j]] = 1
            d[edge[to][j]] = to+1
            que.append(edge[to][j])

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))
    g = {i: [] for i in range(1, n + 1)}

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

    from collections import deque

    que = deque()
    que.append(1)
    ans = [-1] * (n + 1)
    ans[1] = 0

    while que:
        cur = que.popleft()
        for nx in g[cur]:
            if ans[nx] == -1:
                ans[nx] = cur
                que.append(nx)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

YES = "Yes"  # type: str

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

    def prev_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        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
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))
        return d, prev

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = Dijkstra()
    for a, b in zip(A, B):
        G.add(a, b, 1)
    ans = G.prev_search(1)[1]
    if None in ans:
        print('No')
    else:
        print('Yes')
        for i in range(2, N+1):
            print(ans[i])
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

from collections import deque
q = deque([0])
INF = float('inf')
dist = [INF] * N
dist[0] = 0
back = [-1] * N
while q:
    v = q.popleft()
    for to in es[v]:
        if dist[v] + 1 >= dist[to]: continue
        dist[to] = dist[v]
        back[to] = v+1
        q.append(to)
print('Yes')
print(*back[1:], sep='\n')

Submission status: Accepted

Solution code:
import sys
import heapq


def input():
    return sys.stdin.readline().strip()


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    prev = [-1] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = heapq.heappop(q)
        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue
        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                prev[j] = i
                heapq.heappush(q, (dist[j], j))
    return dist, prev


def main():
    N, M = map(int, input().split())
    node = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        node[a - 1].append((1, b - 1))
        node[b - 1].append((1, a - 1))
    d, p = dijkstra(0, N, node)
    for i in range(N):
        if d[i] == float("inf"):
            print("No")
            return
    print("Yes")
    for i in range(1, N):
        print(p[i] + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[-1]*n
d=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
from collections import deque
q=deque()
q.append(0)
while q:
    now=q.popleft()
    for x in d[now]:
        if l[x]==-1:
            l[x]=now
            q.append(x)
if -1 in l:
    print("No")
else:
    print("Yes")
    for i in l[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
li = [list(map(int,input().split())) for i in range(m)]

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

for i in li:
    i[0]-=1
    i[1]-=1
    road[i[0]].append(i[1])
    road[i[1]].append(i[0])

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.popleft()
    for i,r in enumerate(road[v]):
        if dist[r]!=-1:
            continue
        dist[r] = v+1
        que.append(r)

dist.pop(0)
print('Yes')
print(*dist,sep='\n')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
road = [[] for _ in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    road[i-1].append(j-1)
    road[j-1].append(i-1)

# BFS
from collections import deque
ans = [-1] * n
todo = deque()
todo.append(0)
while len(todo) > 0:
    i = todo.popleft()
    for j in road[i]:
        if ans[j] > -1:
            continue
        ans[j] = i
        todo.append(j)

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

Submission status: Accepted

Solution code:
from queue import Queue as Q
INF = float('inf')
def bfs(s):
	dist = [INF]*(n+1)
	q = Q()
	q.put(s)
	dist[s] = 0
	while not q.empty():
		u = q.get()
		for v in adj[u]:
			if dist[v]==INF:
				dist[v] = 1+dist[u]
				pred[v] = u
				q.put(v)
				
n,m = map(int,input().split())
pred = [-1]*(n+1)
adj = [[] for i in range(n+1)]
for _ in range(m):
	u,v = map(int,input().split())
	adj[u]+=[v]
	adj[v]+=[u]
bfs(1)
	
if -1 in pred[2:]:
	print("No")
else:
	print("Yes")
	print(*(pred[2:]),sep = "\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    graph = {}
    for i in range(N):
        graph[i] = set()
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A-1].add(B-1)
        graph[B-1].add(A-1)
    que = deque([])
    que.append(0)
    seen = [0 for _ in range(N)]
    ans = [0 for _ in range(N)]
    while len(que) != 0:
        v = que.popleft()
        for node in graph[v]:
            if seen[node] == 1:continue
            ans[node] = v
            seen[node] = 1
            que.append(node)
    ok = "Yes"
    for i in range(N):
        if seen[i] == 0:
            ok = "No"
            break
    print(ok)
    if ok == "Yes":
        for i, a in enumerate(ans):
            if i == 0:continue
            print(a+1)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

q = deque()
q.append(1)

while q:
	cur = q.popleft()
	for dest in roads[cur]:
		if ans[dest] == -1:
			ans[dest] = cur
			q.append(dest)


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

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    edge = [[] for _ in range(N)]
    
    for _ in range(M):
        a,b = map(int,input().split())
        a -= 1;b -= 1
        edge[a].append(b)
        edge[b].append(a)
        
    go = [False]*N
    go[0] = True
    bef = [-1]*N
    
    q = deque([0])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if not go[fol]:
                bef[fol] = now
                go[fol] = True
                q.append(fol)

    if False in go:
        print("No")
    else:
        print("Yes")
        for i in range(1,N):
            print(bef[i]+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

prev = [-1] * N

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        prev[w] = v
        que.append(w)

print("Yes")
print(*[prev[i]+1 for i in range(1, N)], sep='\n')

Submission status: Accepted

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

for i in range(m):
    a, b = map(int, input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
seen = set([0])
q = deque([0])
ans = [0] * n
while q:
    parent = q.popleft()
    for child in d[parent]:
        if child not in seen:
            ans[child] = parent + 1
            q.append(child)
            seen.add(child)
    if len(seen) == n:
        break
print('Yes')
for i in ans[1:]:
    print(i)

Submission status: Accepted

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

ans = [0 for i in range(n+1)]
import queue
q = queue.Queue()
q.put(1)
while not q.empty():
  node = q.get()
  for e in edges[node]:
    if ans[e] == 0:
      ans[e] += node
      q.put(e)

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

Submission status: Accepted

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

ans = [None]*(n+1)
q = deque([1])
ans[1] = 0

while q:
    now = q.popleft()
    for next in g[now]:
        if ans[next] == None:
            ans[next] = now
            q.append(next)

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

Submission status: Accepted

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

D = [None]*(N+1)
D[1] = 0

Q = set([1])

while len(Q) > 0:
    Q2 = set()
    for q in Q:
        for r in G[q]:
            if D[r] == None:
                D[r] = q
                Q2.add(r)

    Q = Q2


print('Yes')
for d in D[2:]:
    print(d)

Submission status: Accepted

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

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

ret_dict = dict()

queue = [1]
visited.add(1)

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
edge = [[] for i in range(N)]
for i in range(M):
	A,B = map(int,input().split())
	A -= 1
	B -= 1
	edge[A].append(B)
	edge[B].append(A)

q = deque([(0, None)])
searched = [False for i in range(N)]
ans = [-1 for i in range(N)]
while len(q) > 0:
	after, before = q.popleft()
	if searched[after]:
		continue
	searched[after] = True
	ans[after] = before
	for n in edge[after]:
		if searched[n]:
			continue
		q.append((n, after))

flag = True
for i in range(1, N):
	if ans[i] == -1:
		flag = False
		break

if flag:
	print("Yes")
	for i in range(1, N):
		print(ans[i] + 1)
else:
	print("No")

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
adj = [[] for i in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

q = [0]
vis = [False]*n
sign = [0]*n
vis[0] = True
while(q):
    s = q.pop(0)
    for i in adj[s]:
        if (not vis[i]):
            vis[i] = True
            sign[i] = s+1
            q.append(i)
if (not all(vis)):
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(sign[i])