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:
import heapq
# 単一始点最短経路。2地点間ではなく、始点が一つで各点へのコストを計算する
# eは隣接リストでe[v] = [(u1,cost1), (u2,cost2)]みたいな形を想定
# 辺の重みは正である必要がある
# O(ElogV)
def dijkstra(e,n,s):
    inf = 10**18
    d = [inf]*n
    prev = [s]*n
    d[s] = 0

    q = [(d[s],s)] # priority queueのソートキーが第一要素
    heapq.heapify([q])
    while len(q)>0:
        _,v = heapq.heappop(q)
        for u,c in e[v]:
            if d[v]+c>=d[u]:
                continue
            d[u] = d[v] + c
            prev[u] = v
            heapq.heappush(q, (d[u],u))
    return d, prev

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

d,prev = dijkstra(e,n,0)
if max(d)==10**18:
    print("No")
    exit()
print("Yes")
for i in range(1,n):
    print(prev[i]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

G = [[] for _ 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)
# print(G)

todo = deque()
seen = set()

todo.append(0)
seen.add(0)

ans = [-1 for _ in range(N)]
while len(todo) > 0:
    here = todo.popleft()
    for neighbor in G[here]:
        if neighbor not in seen:
            todo.append(neighbor)
            seen.add(neighbor)
            if ans[neighbor] == -1:
                ans[neighbor] = here

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N,M = map(int,input().split())
    shirube = [None]*(N+1)
    shirube[1] = (1,0)
    mmap = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int,input().split())
        mmap[a].append(b)
        mmap[b].append(a)
    queue = deque()
    queue.appendleft((1,0))
    while queue:
        current_node, distance = queue.pop()
        for next_node in mmap[current_node]:
            new_distance = distance+1
            if shirube[next_node] is None:
                shirube[next_node] = (current_node, new_distance)
                queue.appendleft((next_node, new_distance))
            elif shirube[next_node][1] > new_distance:
                shirube[next_node] = (current_node, new_distance)
                queue.appendleft((next_node, new_distance))
    shirube = shirube[1::]
    if None in shirube:
        print("No")
        return
    print("Yes")
    for s in shirube[1::]:
        print(s[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    from collections import deque
    n,m = map(int,input().split()) 
    edge = [[] for i in range(n+1)]
    visit=[-1]*(n+1)
    for i in range(m):
        a,b = map(int,input().split())
        edge[a].append(b)
        edge[b].append(a)
    chk=deque()
    chk.append([1,0])
    while chk:
        x,bx=chk.popleft()
        if visit[x]>-1:
            continue
        visit[x]=bx
        bx=x
        for i in edge[x]:
            if visit[i]>-1:
                continue
            chk.append([i,bx])
    print('Yes')
    for i in visit[2:]:print(i)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [ [] for j in range(N+1) ]
for i in range(M):
    a, b = map(int, input().split())
    X[a].append(b)
    X[b].append(a)

result = [0] * (N+1)
c = []
flag = [0]*N
for x in X[1]:
    result[x] = 1
    c.append(x)
    flag[x-1]=True

c_new = []
while not all(flag):
    for x in c:
        for y in X[x]:
            if flag[y-1] == False:
                result[y] = x
                c_new.append(y)
                flag[y-1] = True
    c = c_new
    c_new = []

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

Submission status: Accepted

Solution code:
#!python3

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

# input
N, M = LI()
A, B = [None] * M, [None] * M
for i in range(M):
    A[i], B[i] = LI()
    A[i] -= 1
    B[i] -= 1

# link
link = [[] for _ in range(N)]
for a, b in zip(A, B):
    link[a].append(b)
    link[b].append(a)


def solve(w):
    l = link[0]
    visit = [False] * N
    visit[0] = True
    for x in l:
        visit[x] = True
        w[x] = 1
    while len(l) > 0:
        next_list = []
        for x in l:
            for v in link[x]:
                if not visit[v]:
                    visit[v] = True
                    w[v] = x + 1
                    next_list.append(v)
        l = next_list
    
    return True


def main():
    w = [None] * N
    solve(w)
    print("Yes")
    for ans in w[1:]:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def dfs(v, p):
        for u in tree[v]:
            if u == p:
                continue
            elif visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u, v)

    visited = [False for _ in range(n)]
    visited[0] = True
    dfs(0, -1)
    for i in visited:
        if not i:
            print("No")
            exit()

    def bfs(v):
        pre = [-1 for _ in range(n)]
        pre[0] = 0
        q = deque()
        q.append(v)
        while q:
            u = q.popleft()
            for nv in tree[u]:
                if pre[nv] == -1:
                    pre[nv] = u
                    q.append(nv)
        return pre

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

n,m = (int(x) for x in input().split())

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

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

#print(E)   

flag = [False]*(n+1)
#vs = [1]
vs = deque([1])

flag[1] = True
res = [0]*(n+1)

while(vs):
    this_v = vs[0]
    for i in E[this_v]:
        if flag[i]:
            continue
        else:
            res[i] = this_v
            flag[i] = True
            vs.append(i)
    vs.popleft()
            
print("Yes")
for i in res[2:]:
    print(i)

Submission status: Accepted

Solution code:
# bfsで探索終了条件をすでにそのノードに値があった場合として，ノードに距離を追加＋このノードを終了条件を見ながら追加とする
# こういうときのindexの扱い方とかこんがらがりやすい

N,M=map(int,input().split())
C=[[] for _ in range(N)]
for _ in range(M):
    ai,bi=map(int,input().split())
    C[ai-1].append(bi)
    C[bi-1].append(ai)

D=[-1 for _ in range(N)]

from collections import deque
que = deque([1])
while que:
    new = que.popleft()-1
    for c in C[new]:
        if D[c-1]==-1:
            que.append(c)
            D[c-1] = new+1

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
dict_road = {}
dict_room = {}
for i in  range(0, m):
    a, b = map(int, input().split())
    if a in dict_road:
        dict_road[a].append(b)
    else:
        dict_road[a] = [b]
    if b in dict_road:
        dict_road[b].append(a)
    else:
        dict_road[b] = [a]
start_list = dict_road[1]
temp_list = []
for no in start_list:
    dict_room[no] = 1
    temp_list.append(no)

while True:
    next_temp_list = []
    for no in temp_list:
        for next_no in dict_road[no]:
            if next_no not in dict_room:
                dict_room[next_no] = no
                next_temp_list.append(next_no)
    if len(next_temp_list) == 0:
        break
    temp_list = next_temp_list
print("Yes")
for i in range(2, n + 1):
    print(dict_room[i])

Submission status: Accepted

Solution code:
n, m = [int(_) for _ in input().split()]
w = {}
seen = {}
d = {}
for i in range(n):
    w[i+1] = []
    seen[i+1] = 0
    d[i+1] = -1
for i in range(m):
    a, b = [int(_) for _ in input().split()]
    w[a].append(b)
    w[b].append(a)

# print(w)
# print(seen)
# print(d)

que = [1]
n_que = []

seen[1] = 1

while len(que) != 0:
    for i in range(len(que)):
        p = que.pop()
        for u in w[p]:
            if seen[u] == 0:
                d[u] = p
                seen[u] = 1
                n_que.append(u)
            else:
                continue
    que = n_que
    n_que = []

# print(seen)
# print(d)

flag = 1
for i in range(n):
    if seen[i+1] == 0:
        flag = 0

if flag == 0:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        # print('n', n)
        # print('i', i)
        print(d[i+1])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
path_list = []
for i in range(N):
    z = []
    path_list.append(z)
for i in range(M):
    A,B = map(int,input().split())
    path_list[A-1].append(B)
    path_list[B-1].append(A)
chk = [0] * N

def bfs(a,chk,path):
    queue = [a]
    while queue:
        b = queue.pop(0)
        for i in range(len(path[b-1])):
            if chk[path[b-1][i]-1] == 0:
                queue.append(path[b-1][i])
                chk[path[b-1][i]-1] =b
    return chk
bfs(1,chk,path_list)
print("Yes")
for i in range(N):
    if i == 0:
        continue
    else:
        print(chk[i])

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int,input().split())
signs = [set() for _ in range(N)]
for i in range(M):
    A, B = map(int,input().split())
    signs[A-1].add(B-1)
    signs[B-1].add(A-1)
Q = deque()
check = [0]*N
ans = [10**6]*N
x = 0
for gen in signs[x]:
    check[gen] = 1
    ans[gen] = x
    Q.append(gen)
while len(Q) != 0:
    v = Q.popleft()
    for gen in signs[v]:
        if check[gen] == 0:
            check[gen] = 1
            ans[gen] = v
            Q.append(gen)
if 10**6 in ans:
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i+1)

Submission status: Accepted

Solution code:
from collections import deque

N,M=list(map(int,input().split()))
g=[set() for _ in range(N+1)]
visit=[0]*(N+1)
anslst=[0]*(N+1)

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

q=deque([1])
visit[1]=1

while len(q)>0:
    u=q.popleft()

    for v in g[u]:
        if visit[v]==1:
            continue

        anslst[v]=u
        visit[v]=1
        q.append(v)

if sum(visit)==N:
    print('Yes')
    for i in range(2,N+1):
        print(anslst[i])
else:
    print('No')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
root_list = [ [] for i in range(N) ]
check_list = [0 for i in range(N)]
ans_list = [0 for i in range(N)]

check_list[0] = 1

for m in range(M):
  A, B = map(int, input().split())
  A,B = A-1,B-1

  root_list[A].append(B)
  root_list[B].append(A)





this_order_check = [0]
this_order_check_next = []

now_ok = 0

def check(now_ok):
  for able in root_list[now_ok]:
    if check_list[able] == 0:
      check_list[able] = 1
      ans_list[able] = now_ok + 1
      this_order_check_next.append(able)

cnt = 0
while 0 in check_list:
  cnt += 1
  for now_ok in this_order_check:
    check(now_ok)
    this_order_check = this_order_check_next
  if cnt >= M:
    break

if 0 not in check_list:
  print('Yes')
  [print(i) for i in ans_list[1:]]
else:
  print('No')

Submission status: Accepted

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

ans = [-1]*n
used = [0]*n
used[0] = 1
que = deque()
que.appendleft(0)
while que:
    v = que.pop()
    # print(v)
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv] = 1
        que.appendleft(nv)
        if ans[nv] == -1:
            ans[nv] = v
    # exit()
# print(ans)    
# print(g)
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())

ab = [set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    ab[a].add(b)
    ab[b].add(a)

def bfs(p):
    ans = [0 for _ in range(n + 1)]
    v = {1}
    q = deque([p])
    while q:
        p = q.popleft()
        c = ab[p] - v
        if len(c) == 0:
            continue
        for pp in c:
            ans[pp] = p
            v.add(pp)
            q.append(pp)
    return ans


ans = bfs(1)
ans = ans[2:]

for an in ans:
    if an == 0:
        print('No')
        exit(0)
print('Yes')
for an in ans:
    print(an)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
edge = {i:[] for i in range(1,N+1)}
for _ in range(M):
    A, B = list(map(int, input().split()))
    edge[A].append(B)
    edge[B].append(A)

remain = [1 for _ in range(N)]
remain[0] = 0
ans = [0 for _ in range(N-1)]
before = 1
cand = [(before,edge[before])]
while len(cand)!=0:
    tmp = []
    for one in cand:
        before, can = one
        for on in can:
            tm = []
            if ans[on-2]==0:
                ans[on-2] = before
            remain[on-1] = 0
            for o in edge[on]:
                if remain[o-1]==1:
                    tm.append(o)
                    remain[o-1] = 0
            tmp.append((on, tm))
    cand = tmp
flag = True
for one in ans:
    if one==0:
        flag=False
        break
if not flag:
    print('No')
else:
    print('Yes')
    for one in ans:
        print(one)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

S = [-1 for _ in range(n)]
q = queue.Queue()
for v in A[0]:
    q.put((0,v))
while not q.empty():
    u,v = q.get()
    if S[v] == -1:
        S[v]=u #visit
        for nex in A[v]:
            if S[nex] == -1: #unvisited
                q.put((v,nex))
S[0]= -2
if not -1 in S:
    print('Yes')
    for i in range(1,n):
        print(S[i]+1)
else:
    print('No')

Submission status: Accepted

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

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

#print(used)


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

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

Submission status: Accepted

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

from collections import deque

load = [deque([]) for _ in range(N)]
ans_list = [-1]*N
q = deque([])
flag = [False]*N

for a,b in AB:
  a -= 1
  b -= 1
  load[a].append(b)
  load[b].append(a)
  
q.append(0)
flag[0] = True
while len(q)!=0:
  x = q.popleft()
  y = load[x]
  for i in y:
    if flag[i]:
      continue
    else:
      flag[i] = True
      q.append(i)
      ans_list[i] = x
      
if -1 in ans_list[1:]:
  print('No')
else:
  print('Yes')
  for ans in ans_list[1:]:
    print(ans+1)

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
# coding: utf-8


def dijkstra(costs, s, t, INF=10**10):
    """
    2020/04/11
    https://atcoder.jp/contests/abc079/tasks/abc079_d

    Parameters
    ----------
    costs: list of list of int
    e.g. [[-1,  4,  1, -1],
          [ 4, -1,  5, -1],
          [ 1,  5, -1,  6],
          [-1, -1,  6, -1]]
    """

    costs = [[c if c >= 0 else INF for c in row] for row in costs]
    n_node = len(costs)

    # adjacents = {}
    # for i in range(n_node):
    #     adjacents[i] = set([j for j in range(n_node) if 0 < costs[i][j] < INF])

    dist_from_s = [INF] * n_node
    dist_from_s[s] = 0
    checked = []  # nodes having fixed shortest distance

    while True:
        print(dist_from_s)
        # not checked nodes (not fixed nodes)
        nodes = [node for node in range(n_node) if node not in checked]

        # find the node having minimum cost from s
        # initialize
        shortest_node, shortest_dist = nodes[0], dist_from_s[nodes[0]]

        for node in nodes:
            if dist_from_s[node] < shortest_dist:
                shortest_node, shortest_dist = node, dist_from_s[node]

        if shortest_node == t:
            return dist_from_s[t]

        checked.append(shortest_node)  # fix

        # not checked nodes (not fixed nodes)
        nodes = [node for node in range(n_node) if node not in checked]

        # update
        for node in nodes:
            dist_from_s[node] = min(
                dist_from_s[shortest_node] + costs[shortest_node][node],
                dist_from_s[node]
            )


def main():
    N, M = map(int, input().split())
    A = [None] * M
    B = [None] * M
    for i in range(M):
        A[i], B[i] = map(int, input().split())
        A[i] -= 1
        B[i] -= 1

    edge_info = {i: [] for i in range(N)}
    for i in range(M):
        edge_info[A[i]].append(B[i])
        edge_info[B[i]].append(A[i])

    # dists = [None] * N
    # dists[0] = 0
    prenodes = [None] * N
    prenodes[0] = 0
    queue = [0]
    queue_size = 1
    queue_idx = 0
    while True:
        # 貪欲に
        if queue_idx == queue_size:
            break

        x = queue[queue_idx]
        queue_idx += 1
        nexts = [y for y in edge_info[x] if prenodes[y] is None]
        for node in nexts:
            prenodes[node] = x
            queue.append(node)
            queue_size += 1

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


main()
# print(main())

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
Map = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    Map[a-1].append(b-1)
    Map[b-1].append(a-1)
sign = [0]*N
depth = [-1]*N
depth[0] = 0
q = deque([0])
while len(q) != 0:
    cur = q.popleft()
    for chi in Map[cur]:
        if depth[chi] != -1:
            continue
        depth[chi] = depth[cur]+1
        sign[chi] = cur
        q.append(chi)
print("Yes")
for i in range(1,N):
    print(sign[i]+1)

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import heapq
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
d=[float("inf") for _ in range(N)]
d[0]=0
q=[]
prev=[-1]*N
q.append([0,0])
q1=q
flag=1
#print(q)
heapq.heapify(q)
#print(q1)
while len(q)>0:
    dist,u=heapq.heappop(q)
    if d[u]<dist: continue
    for i in tree[u]:
        alt=d[u]+1
        if d[i]>alt:
            d[i]=alt
            prev[i]=u
            heapq.heappush(q,[alt,i])
    #print(prev,d,q1)
for i in range(1,N):
    if prev[i]==-1:
        flag=0
        break
if flag==0:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(prev[i]+1)

Submission status: Accepted

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

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

for i in range(M):
  x,y=map(int,input().split(' '))
  m[x-1].append(y-1)
  m[y-1].append(x-1)

sign=[0]
signed_map=[-1]*N
signed_map[0]=1
while True:
  signed=sign
  sign=[]
  for s in signed:
    for room in m[s]:#サインされた場所から繋がってるとこを回る
      if signed_map[room]==-1:
        signed_map[room]=s+1
        sign.append(room)
  if sign==[]:break

print('Yes')
for ch in signed_map[1:]:
  print(ch)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
road = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  road[a].append(b)
  road[b].append(a)
co = set([0])
cn = set([0])
nn = set()
ans = [-1]*n
ans[0] = 0
for _ in range(n):
  if len(cn) == 0:
    break
  for i in cn:
    for j in road[i]:
      if j not in co:
        if j not in cn:
          nn.add(j)
          ans[j] = i
    co.add(i)
  cn = set(nn)
  nn.clear()
if -1 in ans:
  print("No")
else:
  print("Yes")
  for i in ans[1:]:
    print(i+1)

Submission status: Accepted

Solution code:
import numpy as np
import math
from collections import deque

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

E = [[] for _ in range(N)]

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

que = deque()
que.append(0)
ans = [None for i in range(N)]

while(len(que) > 0):
    p = que.popleft()
    #print(p, E[p])
    for to in E[p]:
        if ans[to] is None:
            #print(to, ans[to])
            que.append(to)
            ans[to] = p

if None not in ans:
    print("Yes")
    for a in ans[1:]:
        print(a + 1)
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

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


is_visited = [False for _ in range(N)]
ans = [0 for _ in range(N)]
def bfs():
    queue = deque()
    queue.append(0)
    is_visited[0] = True
    while queue:
        pos = queue.popleft()
        for next_pos in A[pos]:
            if is_visited[next_pos] == False:
                is_visited[next_pos] = True
                queue.append(next_pos)
                ans[next_pos] = pos

bfs()

if False in is_visited:
    print("No")
else:
    print("Yes")
    for i in range(N-1):
        print(ans[i+1]+1)

Submission status: Accepted

Solution code:
# Problem D - Double Dots

from collections import deque

# input
N, M = map(int, input().split())
graph_list = {}
for i in range(M):
    a, b = map(int, input().split())
    if a in graph_list:
        graph_list[a].append(b)
    else:
        graph_list[a] = [b]

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

# initialization
visit_list = [0]*N
distance_list = [float("INF")]*N
distance_list[0] = 0
visit_queue = deque([1])
queue_count = 1

# bfs search
while queue_count>0:
    v = visit_queue.popleft()
    queue_count -= 1

    graph = graph_list[v]
    for n in graph:
        if distance_list[v-1]+1<distance_list[n-1]:
            distance_list[n-1] = distance_list[v-1] + 1
            visit_list[n-1] = v
            visit_queue.append(n)
            queue_count += 1

# output
print("Yes")
for i in range(1, N):
    print(visit_list[i])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
adjacent = [[] for i in range(N)]
for i in range(M):
  A,B = map(int,input().split())
  adjacent[A-1].append(B-1)
  adjacent[B-1].append(A-1)
Michi = [0 for i in range(N)]
visited = set()
frontier = set()
visited.add(0)
frontier.add(0)
while len(frontier) > 0:
  newfrontier = set()
  for v in frontier:
    for next in adjacent[v]:
      if next not in visited:
        Michi[next] = v
        visited.add(next)
        newfrontier.add(next)
  frontier = newfrontier
print('Yes')
for i in range(1,N):
  print(Michi[i]+1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
ki=[[] for f in range(N)]
for i in range(M):
 A,B= map(int,input().split())
 ki[A-1].append(B-1)
 ki[B-1].append(A-1)
stack = deque([0])
check = [0]*N #チェック済みリスト
check[0] = 1
ans=[0]*(N-1)
while stack != deque([]) :
 a=stack.popleft()
 for i in range(len(ki[a])):
  if check[ki[a][i]]==0:
   stack.append(ki[a][i])
   check[ki[a][i]]=1
   ans[ki[a][i]-1]=a+1
print("Yes")
for i in range(N-1):
 print(ans[i])

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque


def wfs(start):
    reached = [None] + [0] * N
    exit = [None] + [-1] * N
    q = deque()

    q.append(start)
    reached[start] = 1
    while q:
        p = q.popleft()
        for r in V[p]:
            if reached[r]:
                continue
            reached[r] = 1
            exit[r] = p
            q.append(r)

    return exit


N, M = map(int, input().split())
V = [None] + [[] for _ in range(N)]
for _ in range(M):
    A, B = list(map(int, input().split()))
    V[A].append(B)
    V[B].append(A)

exit = wfs(1)[2:]
if min(exit) == -1:
    print('No')
else:
    print('Yes')
    for e in exit:
        print(e)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, check):
    queue = deque([v])
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if check[u] != -1:
                continue
            check[u] = v + 1
            queue.append(u)


def main():
    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)

    check = [-1] * N
    check[0] = 0
    bfs(G, 0, check)

    print("Yes")
    print(*check[1:], sep="\n")


if __name__ == "__main__":
    main()