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:
n,edge = map(int,input().split())
l = [0]*n 
stack = [1]
dic  = {}
for i in range (edge) :
    x = [int(x) for x in input().split()]
    if x[0] not in dic :
        dic[x[0]] = []
    if x[1] not in dic :
        dic[x[1]] = []
    dic[x[0]].append(x[1])
    dic[x[1]].append(x[0])
x = 1 
while len(stack) != 0 :
    check = stack[0]
    stack.pop(0)
    for i in range (len(dic[check])) :
        if l[dic[check][i]-1] == 0 :
            x += 1 
            stack.append(dic[check][i])
            l[dic[check][i]-1] = check 
if l.count(0) != 0 :
    print("No")
else :
    print("Yes")
    for i in range (1,n) :
        print(l[i])

Submission status: Accepted

Solution code:
def main():
    N,M=map(int,input().split())
    graph=[[] for _ in range(N)]
    for _ in range(M):
        A,B=map(int,input().split())
        graph[A-1].append([A-1,B-1])
        graph[B-1].append([B-1,A-1])
    #print(graph)
    ans=[-1]*N
    Q=graph[0]
    while Q!=[]:
        tmp=[]
        for q in Q:
            ind,val=q
            if ans[val]!=-1:
                continue
            ans[val]=ind
            tmp+=graph[val]
        Q=tmp
    for w in ans:
        if w==-1:
            print("No")
            break
    print("Yes")
    for w in ans[1:]:
        print(w+1)
main()

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
room = {i: set() for i in range(n)}
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    room[a].add(b)
    room[b].add(a)

ans = dict()
visited = [1] + [0] * (n - 1)
que = deque([0])
while que:
    now = que.popleft()
    for i in room[now]:
        if visited[i]:
            continue
        ans[i] = now
        visited[i] = 1
        que.append(i)

if sum(visited) == n:
    print('Yes')
    for i in range(1, n):
        print(ans[i]+1)
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
d = {}
for _ in range(M):
    A, B = map(int, input().split())
    if A not in d:
        d[A] = [B]
    else:
        d[A].append(B)
    if B not in d:
        d[B] = [A]
    else:
        d[B].append(A)

ans = [(-1, float("inf"))] * N
cnt = 0
# stack = [(1, 0)]
queue = deque([(1, 0)])

while queue:
    val, step = queue.popleft()
    next_vals = d[val]
    for nxt in next_vals:
        #        if ans[nxt - 1][1] > step + 1:
        if ans[nxt - 1][0] == -1:
            cnt += 1
            ans[nxt - 1] = (val, step + 1)
            queue.append((nxt, step + 1))

if cnt < N - 1:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i][0])

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
G = [deque([]) for i in range(N+1)] 

road = [input().split() for i in range(M)]

for i in range(M):
    G[int(road[i][0])].append(int(road[i][1]))
    G[int(road[i][1])].append(int(road[i][0]))     

check = [-1] * (N+1)   

def dfs(v):
    stack = deque([v])
    
    while stack:    
        tmp = stack[0]
        if G[tmp]:
            w = G[tmp].popleft() 
            if check[w] < 0:
                check[w] = tmp
                stack.append(w)
        else:
            stack.popleft()
    return check


check = dfs(1)
check[0] = 100
check[1] = 100

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

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N, M = ri_()
d = [[] for i in range(N + 1)]
ans = [0] * (N + 1)
for i in range(M):
    A, B = ri_()
    d[A].append(B)
    d[B].append(A)
L = deque([1])
while L:
    n = L.popleft()
    for i in d[n]:
        if not ans[i]:
            ans[i] = n
            L.append(i)
if 0 in ans[2:]:
    print('No')
    exit()
print('Yes')
for i in range(2, N + 1):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split(' '))
edges = defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split(' '))
    edges[a].add(b)
    edges[b].add(a)

queue = deque()
queue.append(1)
results = {}

while len(queue) > 0:
    x = queue.popleft()
    next_nodes = edges[x]
    for node in next_nodes:
        if node not in results.keys():
            results[node] = x
            queue.append(node)

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    import sys
    from collections import deque

    N, M = list(map(int, sys.stdin.readline().split()))
    rooms = [None]*(N+1)
    for _ in range(M):
        A, B = list(map(int, sys.stdin.readline().split()))
        # A, B = A-1, B-1
        if rooms[A] is None:
            rooms[A] = []
        if rooms[B] is None:
            rooms[B] = []
        rooms[A].append(B)
        rooms[B].append(A)

    ans = [None] * (N+1)
    ans[0] = -1
    ans[1] = -1

    # 幅優先探索
    que = deque([1])
    while que:
        room = que.popleft()
        nrooms = rooms[room]
        # print(nrooms)
        # input()

        for nroom in nrooms:
            if ans[nroom] == None:
                ans[nroom] = room
                que.append(nroom)
            else:
                pass

    if None in ans:
        print("No")
        return
    print("Yes")
    for v in ans[2:]:
        print(v)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#import re
import sys
input = sys.stdin.readline
#import heapq
#import bisect
from collections import deque
#import math

def main():
    n, m = map(int, input().split())
    AL = [[] for i in range(n+1)]
    check = [0 for i in range(n+1)]
    for i in range(m):
        s, e = map(int, input().split())
        AL[s].append(e)
        AL[e].append(s)
    que = deque()
    pb = 1, 1
    que.append(pb)
    ANS = [0 for i in range(n+1)]
    while(que):
        pb = que.popleft()
        p = pb[0]
        b = pb[1]
        if check[p] == 1:
            continue
        elif check[p] == 0:
            ANS[p] = b
            check[p] = 1
            for num in AL[p]:
                que.append((num, p))
    print("Yes")
    for i in range(n+1):
        if i in [0, 1]:
            continue
        else:
            print(ANS[i])

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
tunagari={}
for i in range(m):
    a,b=map(int,input().split())
    if a not in tunagari:
        tunagari[a]=[b]
    else:
        tunagari[a].append(b)
    if b not in tunagari:
        tunagari[b]=[a]
    else:
        tunagari[b].append(a)
heya=["." for i in range(n)]
ans=[0 for i in range(n)]
heya[0]=0
tmp=deque([1])
count=1
while tmp:
    now=tmp.popleft()
    for i in tunagari[now]:
        if heya[i-1]==".":
            heya[i-1]=heya[now-1]+1
            tmp.append(i)
            ans[i-1]=now

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, m = input_to_int_map()
    ab = [input_to_int_tuple() for i in range(m)]

    from collections import defaultdict
    room = defaultdict(set)
    for a, b in ab:
        room[a].add(b)
        room[b].add(a)


    from collections import deque
    root = deque()
    root.append(1)
    moved = [-1] * n
    moved[0] = 0
    while root:
        room_no = root.popleft()
        for move_room_no in room[room_no]:
            if moved[move_room_no - 1] != -1:
                continue

            root.append(move_room_no)
            moved[move_room_no - 1] = room_no

    if min(moved) == -1:
        print("No")
    else:
        print("Yes")
        for i in moved[1:]:
            print(i)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
e = {i:[] for i in range(1, n+1)}
for _ in range(m):
    p, q = map(int, input().split())
    e[p].append(q)
    e[q].append(p)

def bfs():
    visited = [0] + [None] * n
    queue = deque([1])
    visited[1] = 0
    while queue:
        current = queue.pop()
        for x in e[current]:
            if visited[x] == None:
                visited[x] = current
                queue.appendleft(x)
    return visited

print('Yes')
print(*bfs()[2:], sep='\n')

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

def solve(N, M, paths):
    used = [False for _ in range(M)]
    stack = deque([1])
    ret = [[float("inf"), -1] for _ in range(N + 1)]
    ret[1] = [0, 1]

    while stack:
        cur = stack.popleft()
        nexts = paths[cur]
        for n in nexts:
            if used[n[0]]:
                continue
            used[n[0]] = True
            if ret[cur][0] + 1 < ret[n[1]][0]:
                ret[n[1]] = [ret[cur][0] + 1, cur]
                stack.append(n[1])

    print("Yes")
    for r in ret[2:]:
        print(r[1])

if __name__ == "__main__":
    N, M = map(int, input().split())
    paths = defaultdict(list)
    for idx in range(M):
        a, b = map(int, input().split())
        paths[a].append([idx, b])
        paths[b].append([idx, a])

    solve(N, M, paths)

Submission status: Accepted

Solution code:
# ダイクストラ法で部屋1から各部屋への最短経路を出す
import queue

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

# 隣接行列の作成
edges_dict = {}
for edge in edges:
    a, b = edge

    if a not in edges_dict:
        edges_dict[a] = [b]
    else:
        edges_dict[a].append(b)

    if b not in edges_dict:
        edges_dict[b] = [a]
    else:
        edges_dict[b].append(a)

# 定数 
COST = 1
INF = 1e10

# i=0は未使用, i>0は部屋iへの最短距離
dist_list = [INF] * (n + 1)
# i=0は未使用, i>0は部屋iの最短経路がたどる次の部屋 = 道しるべ
prev_list = [None] * (n + 1)
q = queue.PriorityQueue()

# 初期化
q.put((0, 1)) # (最短経路, 部屋番号)
dist_list[1] = 0
prev_list[1] = 1

while not q.empty():
    min_dist, v = q.get()
    #print("min_dist={}, v={}".format(min_dist, v))

    if dist_list[v] < min_dist:
        #print("waste")
        continue

    #print("check edges: ", edges_dict[v])
    for w in edges_dict[v]:
        cost = dist_list[v] + COST
        if dist_list[w] > cost:
            #print("push path {} -> {}; cost {}; path {}".format(v, w, cost, prev_list[v]))
            dist_list[w] = cost
            prev_list[w] = v#prev_list[v]
            q.put((cost, w))

print("Yes")
#print(edges_dict)
#print(dist_list)
#print(prev_list)
for v in prev_list[2:]:
    print(v)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
e = []
es = defaultdict(set)
for i in range(m):
    ee = tuple(sorted(map(int, input().split())))
    e.append(ee)
    es[ee[0]].add(ee[1])
    es[ee[1]].add(ee[0])

path = [None] * (n + 1)
path[1] = 1
num = 0
nodes = {1}
while nodes:
    new_nodes = set()
    for nd in nodes:
        for e in es[nd]:
            if path[e] is None:
                path[e] = nd
                num += 1
                new_nodes.add(e)
    nodes = new_nodes
if num == n - 1:
    print("Yes")
    for i in range(2, n + 1):
        print(path[i])
else:
    print("No")

Submission status: Accepted

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



r=list()
for i in range(n):
    a=list()
    r.append(a)
a=list()
for i in range(n):
    a.append(-1)
for i in range(m):
    x=0;y=0
    x,y=map(int,input().split())
    x-=1
    y-=1
    r[x].append(y)
    r[y].append(x)
    

a[0]=0
now=[0]
while len(now)!=0:
    nex=list()
    for i in now:
        for j in r[i]:
            if a[j]==-1:
                a[j]=i
                nex.append(j)
    now=nex


if -1 in a:
    print('No')
else:
    print('Yes')
    for item in a[1:]:
        print(item+1)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import heapq


def Bellman_Ford(s,n,w,es):
    #s→iの最短距離
    # s:始点, n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [Max] * n
    #d[i] : s→iの最短距離
    d[s] = 0
    po = 0
    while po < 2*N + 100:
        update = False
        for p,q,r in es:
        # e: 辺iについて [from,to,cost]
            if d[p] != Max and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if not update:
            break
        po += 1
    return d


def dijkstra():
    #n:ノード数e:辺数,w:スタート

    edge = [[] for i in range(n)]
    dg = 10**7
    # edge[i]:[コスト]
    for i in range(e):
        x,y = map(int,input().split())
        z = 1
        x -= 1
        y -= 1
        edge[x].append(z*dg + y)
        edge[y].append(z*dg + x)
    
    s = w-1
    d = [-1]*n
    d[s] = 0

    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)

        

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v,c = minedge%dg,minedge//dg
        if d[v] >= 0:
            continue
        d[v] = c
        for e in edge[v]:
            vNext = e%dg
            if d[vNext]:
                heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

    return d


def warshall_floyd(n,d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d






N,M = m()


n = N
w = 1
gr = [[] for i in range(n)]
edge = [[] for i in range(n)]
dg = 10**7
# edge[i]:[コスト]
for i in range(M):
    a,b = map(int,input().split())
    z = 1
    a -= 1
    b -= 1
    gr[a].append(b)
    gr[b].append(a)
    edge[a].append(z*dg + b)
    edge[b].append(z*dg + a)

s = w-1
d = [-1]*n
d[s] = 0

edgelist = []
for e in edge[s]:
    heapq.heappush(edgelist,e)

    

while len(edgelist):
    minedge = heapq.heappop(edgelist)
    v,c = minedge%dg,minedge//dg
    if d[v] >= 0:
        continue
    d[v] = c
    for e in edge[v]:
        vNext = e%dg
        if d[vNext]:
            heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)
print("Yes")
for i in range(1,N):
    for j in gr[i]:
        if d[i] == d[j]+1:
            print(j+1)
            break

Submission status: Accepted

Solution code:
import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M = map(int, readline().split())
graph = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int1, readline().split())
    graph[A].append(B)
    graph[B].append(A)
ans = [None] * (N)

visited = [False] * N
visited[0] = True

que = deque([0])

while len(que) > 0:
    acc = que.popleft()
    for connected in graph[acc]:
        if visited[connected]:
            continue

        ans[connected] = acc + 1
        visited[connected] = True
        que.append(connected)

if sum(visited) == len(visited):
    print("Yes")
    for sign in ans[1:]:
        print(sign)
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def print_ans(self):
        for i in range(1, n):
            print(self.prev[i]+1)

g = Graph()

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

d = Dijkstra(g, 0)
print('Yes')
d.print_ans()

Submission status: Accepted

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

from collections import deque


N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    i, j = map(int, input().split())
    G[i-1].append(j-1)
    G[j-1].append(i-1)


# dはparent
def bfs(start):
    distance = [-1 for _ in range(N)]
    Q = deque()
    Q.append(start)
    d = [-2 for _ in range(N)]
    d[start] = -1
    distance[start] = 0
    while len(Q) > 0:
        u = Q.popleft()
        for v in G[u]:
            if d[v] == -2:
                Q.append(v)
                d[v] = u  # 親のノード
                distance[v] = distance[u] + 1
    
    return d, distance

p, distance = bfs(0)


for path in p:
    if path == -2:
        print("No")
else:
    print("Yes")
    for path in p[1:]:
        print(path + 1)

Submission status: Accepted

Solution code:
from collections import deque
deck=deque()

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


not_visited=[1 for i in range(n)]
not_visited[0]=0

deck.append(0)
while len(deck)!=0:
    target=deck.popleft()
    tsuuro=tsuuro_list[target]
    for node in tsuuro:
        if not_visited[node]:
            not_visited[node]=0
            deck.append(node)
            saiteki[node]=target

if sum(not_visited)!=0:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(saiteki[i]+1)

Submission status: Accepted

Solution code:
#map(int, input().split())
from collections import deque
N, M = map(int, input().split())
graph = {i:deque() for i in range(1, N+1)}

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

seen = [0]*(N+1)
queue = deque()
dist = [-1]*(N+1)
dicgq = {i: 0 for i in range(2, N+1)}
dicqg = {i: 0 for i in range(2, N+1)}

def bfs(v):
    dist[v] = 0
    seen[v] = 1
    queue.append(v)
    while queue:
        q = queue[0]
        if not graph[q]:
            queue.popleft()
            continue
        g = graph[q].popleft()
        if seen[g]:
            continue
        seen[g] = 1
        dist[g] = dist[q] + 1
        dicgq[g] = q # mitisirube
        dicqg[q] = g # graph
        queue.append(g)

bfs(1)
pre_dis = dist.copy()

for i in range(2, N+1):
    graph[i] = dicqg[i]



seen = [0]*(N+1)
queue = deque()
def bfs2(v):
    dist[v] = 0
    seen[v] = 1
    queue.append(v)
    while queue:
        q = queue[0]
        if not graph[q]:
            queue.popleft()
            continue
        g = graph[q].popleft()
        if seen[g]:
            continue
        seen[g] = 1
        dist[g] = dist[q] + 1
        
        queue.append(g)


bfs2(1)
if pre_dis != dist:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(dicgq[i])

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    d = {}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    v = set()
    v.add(0)
    l = [0] * N
    c = set()
    c.add(0)
    r = 0
    while len(v) < N:
        n = set()
        for i in c:
            for j in d[i]:
                if j not in v:
                    l[j] = i
                    v.add(j)
                    n.add(j)
        c = n
    print('Yes')
    for i in range(1,N):
        print(l[i] + 1)
main()

Submission status: Accepted

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



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

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

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    status[s] = VISITING
    signs[s] = 0
    Q.append(s)
    while len(Q) > 0:
        u = Q.popleft()
        for v in rooms[u]:
            if status[v] == NOT_VISITED:
                status[v] = VISITING
                signs[v] = u
                Q.append(v)
        status[u] = VISITED


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

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

INFTY = float('inf')
signs = [INFTY] * n

NOT_VISITED = 0
VISITING = 1
VISITED = 2
status = [NOT_VISITED] * n
Q = deque()

bfs(0)
ok = True

for sign in signs:
    if sign == INFTY:
        ok = False

if ok:
    print('Yes')
    signs = signs[1:]
    for sign in signs:
        print(sign + 1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [[] for _ in range(n)]
for i in range(m):
	a, b = map(int, input().split())
	ab[a-1].append(b-1)
	ab[b-1].append(a-1)
# print(ab)
cnt = 0
check = [False for _ in range(n)]
check[0] = True
listA = [0]
listB = []
michishirube = [-1 for _ in range(n)]
while len(listA) > 0:
	# print(listA,listB)
	listB = []
	for la in listA:
		for laa in ab[la]:
			if not check[laa]:
				michishirube[laa] = la
				listB.append(laa)
				check[laa] = True
				cnt += 1
	listA = listB

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

Submission status: Accepted

Solution code:

from collections import deque


def bfs(u):
    queue = deque([u])
    d = [None] * N  # uからの距離の初期化
    d[u] = 0  # 自分との距離は0
    ans = [0] * N
    while queue:
        v = queue.popleft()
        for i in g[v]:

            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                ans[i] = v + 1
    return ans

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

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

ans = bfs(0)
if 0 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n, m = [int(x) for x in input().split()]
    corridors = [list() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        corridors[a].append(b)
        corridors[b].append(a)

    qu = deque()
    # dist = [-1] * n
    ans = [None] * n
    # initialize
    qu.append(0)
    ans[0] = 0
    # search
    while len(qu):
        v = qu.popleft()
        for new in corridors[v]:
            if ans[new] is not None:
                continue
            # dist[new] = dist[v] + 1
            ans[new] = v + 1
            qu.append(new)

    # for i, x in enumerate(ans):
    #     if i == 0:
    #         continue
    #     print('room', i+1, ':', x)

    print('Yes')
    for x in ans[1:]:
        print(x)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m = map(int, input().split())

INF = 1001001001

to = [[] for _ in range(n)]
dist = [INF]*n
dist[0] = 0
ans = [-1]*n
ans[0] = [0]

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

import queue

q = queue.Queue()
used = [0]*n
q.put(0)
used[0] = 1 # qに突っ込んだ時点でその頂点のusedを1にする

while not q.empty():
    v = q.get()
    for i in range(len(to[v])):
        u = to[v][i]
        if used[u]: continue
        if dist[v]+1 < dist[u]:
            dist[u] = dist[v]+1
            ans[u] = v
        q.put(u)
        used[u] = 1 # qに突っ込んだ時点でその頂点のusedを1にする

if -1 not in ans:
    print('Yes')
    for i in ans[1:]: print(i+1)
else:
    print('No')

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def dijkstra(graph, start):
    
    INF = float("inf")

    num = len(graph)
    dist = [INF] * num
    prev = [INF] * num

    dist[start] = 0
    q = []
    heappush(q, (0, start))
    
    while len(q) != 0:
        prov_cost, src = heappop(q)

        if dist[src] < prov_cost:
            continue
        
        for edge in graph[src]:
            cost = edge[1]
            dest = edge[0]

            if dist[dest] > dist[src] + cost:
                 dist[dest] = dist[src] + cost
                 heappush(q, (dist[dest], dest))
                 prev[dest] = src
        
    return prev

def main():
    n,m = map(int, input().split())
    G = {}
    for i in range(n):
        G.update({i: []})
    for i in range(m):
        a, b = map(int, input().split())
        G[a - 1].append([b - 1, 1])
        G[b - 1].append([a - 1, 1])

    path = dijkstra(G, 0)
    
    print("Yes")
    for i in range(1, n):
        print(path[i] + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue
N, M = map(int, input().split())
q=queue.Queue()
room=[['' for i in range(0)] for j in range(N+1)]
checkRoom=[0 for j in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    room[A].append(B)
    room[B].append(A)
q.put(1)
while not q.empty():
    checkI=q.get()
    for j in range(len(room[checkI])):
        if checkRoom[room[checkI][j]]==0:
            q.put(room[checkI][j])
            checkRoom[room[checkI][j]]=checkI
print("Yes")
for i in range(2,N+1):
    print(checkRoom[i])