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,m = map(int,input().split())
node_dict = {i:set() for i in range(1,n+1,1)}
for i in range(m):
    tmp1,tmp2 = map(int,input().split())
    node_dict[tmp1].add(tmp2)
    node_dict[tmp2].add(tmp1)
mitishirube_list = [1]
tansaku_set = set([i for i in range(2,n+1,1)])
tansakusumi_list = []
while(tansaku_set != set()):
    tmp_list = mitishirube_list
    mitishirube_list = []
    for i in tmp_list:
        for j in node_dict[i] & tansaku_set:
            tansakusumi_list.append([j,i])
            tansaku_set.remove(j)
            mitishirube_list.append(j)
tansakusumi_list.sort()
print("Yes")
for i in tansakusumi_list:
    print(i[1])

Submission status: Accepted

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

seen = [False for i in range(n)]
que = deque()
def bfn(i,j):
    for x in pas[i]:
        if seen[x-1]!=False:
            continue
        seen[x-1]=i
        que.append([x,i])
    if que:
        now,pre =que.popleft()
        bfn(now,pre)
    else:
        return

bfn(1,1)

if False in seen:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(seen[i+1])

Submission status: Accepted

Solution code:
import queue
#queue.Queue()
#que.put(i)
#que.get()

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)

sign = [-1] * N
que = queue.Queue()
que.put(0)

while not que.empty():
    v = que.get()
    for nv in G[v]:
        if sign[nv] != -1:
            continue
        sign[nv] = v
        que.put(nv)

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

Submission status: Accepted

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

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

    net[a].append(b)
    net[b].append(a)

a = [-1] * (n+1)
d = deque()
d.append(1)
while d:
    u = d.popleft()
    for child in net[u]:
        if a[child] != -1:continue
        a[child] = u
        d.append(child)
a = a[2:]
for z in a:
    if z == -1:
        print("No")
        exit()
print("Yes")
for z in a:
    print(z)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    # https://atcoder.jp/contests/abc070/tasks/abc070_d
    # https://atcoder.jp/contests/abc070/submissions/11681543
    from heapq import heapify, heappop, heappush

    N, M = map(int, input().split())
    inf = 10 ** 17

    def dijkstra_heap(start, edge):
        # 始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        # a:重み(//), b:次の頂点(%)
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)

        while len(edgelist):
            # まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d

    # N:頂点数   W:辺数
    edge = [[] for i in range(N)]
    # edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(M):
        a, b = map(int, input().split())
        edge[a - 1].append((1, b - 1))
        edge[b - 1].append((1, a - 1))

    d = dijkstra_heap(0, edge)
    max_times = max(d)

    times_list = [[] for _ in range(max_times+1)]
    for id, val in enumerate(d):
        times_list[val].append(id)

    def main():
        mark = [0]+[-1]*(N-1)
        cur = 1
        for i in range(1, N):
            if d[i] == 1:
                mark[i] = 0
            else:
                if times_list[d[i]-1]:
                    mark[i]=times_list[d[i]-1][0]
                else:
                    return False
        return mark[1:]

    if main():
        print('Yes')
        for i in main():
            print(i+1)
    else:
        print('No')

resolve()

Submission status: Accepted

Solution code:
import collections

def get_input():
    return list(map(lambda x:int(x), input().split()))

def main():
    inp = get_input()
    n, m = inp[0], inp[1]
    adj_list = [[] for i in range(n)]
    for i in range(m):
        inpu = get_input()
        a, b = inpu[0], inpu[1]
        adj_list[a - 1].append(b - 1)
        adj_list[b - 1].append(a - 1)
    
    q = collections.deque()
    visited = set()
    q.append(0)
    visited.add(0)
    p = [-1] * n

    #print(adj_list)
    while q:
        u = q.popleft()
        for i in adj_list[u]:
            #print("checking", u, i)
            if i not in visited:
                q.append(i)
                visited.add(i)
                p[i] = u
    #print(p)
    
    for i in range(1, len(p)):
        if p[i] == -1:
            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 = list(map(int, input().split()))

room_dict = {i+1:[] for i in range(N)}
for _ in range(M):
  _a, _b = list(map(int, input().split()))
  room_dict[_a].append(_b)
  room_dict[_b].append(_a)

rooms = set(room_dict.keys())
s_dict = {i+1:None for i in range(1, N)}
traversed_rooms = set([1])

now_rooms = [1]
from operator import add
while now_rooms:
    next_rooms = set()
    for _room in now_rooms:
        traversed_rooms.add(_room) # 訪問済みを保存
        _n_rooms  = [i for i in room_dict[_room] 
                         if (not i in traversed_rooms) and (s_dict[i] is None)]
        for n_room in _n_rooms:
            next_rooms.add(n_room) # 今の次の階層を、次のiteration用に入れる
            s_dict[n_room] = _room # 次の階層は、今の階層への道標を置けば十分
    now_rooms = [i for i in next_rooms if not i in traversed_rooms] # まだ訪れてない部屋を探す
    
print('Yes') # 常に答えは存在する

for i in range(2, N+1):
    print(s_dict[i])

Submission status: Accepted

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

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

ans = [10**9] * (N+1)
ans[0] = 0
ans[1] = 0

from collections import deque
q = deque([1])

while q:
    p = q.popleft()
    for i in root[p]:
        if ans[i] == 10**9:
            ans[i] = p
            q.append(i)

if 10**9 in set(ans):
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(ans[i])

Submission status: Accepted

Solution code:
nm = input().split()
n = int(nm[0])
m = int(nm[1])

load = []
load_roomn = {}

for i in range(m):
  l = list(map(lambda x:int(x), input().split()))
  load.append(l)
  #print(l)
  if l[0] in load_roomn:
    load_roomn[l[0]].append(i)
  else:
    load_roomn[l[0]] = [i]
  if l[1] in load_roomn:
    load_roomn[l[1]].append(i)
  else:
    load_roomn[l[1]] = [i]
    
#print(load)
#print(load_roomn)

visitCost = [10^5+1]*(n+1)#部屋が10^5個しかないのでこれがinfでいいはず

marker = [-1]*(n+1)
marker[1] = 0
visitable = [1]
visited = []
visitednum = 1

#count = 0
while visitednum < n:
  #count += 1
  #最短で行ける場所確認
  visiting = visitable.pop(0)
  #print("visit from " + str(visiting))
  for i in load_roomn[visiting]:
    if load[i][0] == visiting:
      if marker[load[i][1]] == -1:
        visitable.append(load[i][1])
        marker[load[i][1]] = visiting
        visitednum += 1
        #print("visit" + str(load[i][1]))
    elif load[i][1] == visiting:
      if marker[load[i][0]] == -1:
        visitable.append(load[i][0])
        marker[load[i][0]] = visiting
        visitednum += 1
        #print("visit" + str(load[i][0]))
    else:
      print("error")

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

Submission status: Accepted

Solution code:
from collections import deque

class Node():
    def __init__(self, val):
        self.val = val
        self.sign = None
        self.adj = []

n, m = map(int, input().split())
a, b = [], []
nodes = []

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(m):
    A, B = map(int, input().split())
    nodeA, nodeB = nodes[A-1], nodes[B-1]
    nodeA.adj.append(nodeB)
    nodeB.adj.append(nodeA)
    # a.append(A)
    # b.append(B)

q = deque()
q.append(nodes[0])
done = set()

while q:
    node = q.popleft()
    parent = node.val

    for adj in node.adj:
        if adj not in done:
            done.add(adj)
            adj.sign = parent
            q.append(adj)
            
print('Yes')            

for i in range(1, len(nodes)):
    print(nodes[i].sign)

Submission status: Accepted

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

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

out=[0 for i in range(n)]

seen={1}
next=[[1],[]]
i=0
while len(next[0])+len(next[1]) != 0:
    if i == 0:
        x=1
    else:
        x=0
    
    for j in next[i]:
        for k in ilist[j-1]:
            if not k in seen:
                seen.add(k)
                next[x].append(k)
                out[k-1]=j
    next[i]=[]
    i=x

print("Yes")
for o in out[1:]:
    print(o)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
import sys
rel=defaultdict(set)
n,m=map(int,input().split())
for s in sys.stdin:
  a,b=map(int,s.split())
  rel[int(a)].add(int(b))
  rel[int(b)].add(int(a))
cand=deque([1])
visited=set([1])
dlist=[0]*n
while len(visited)!=n:
  now=cand.popleft()
  for i in rel[now]:
    if i not in visited:
      cand.append(i)
      visited.add(i)
      dlist[i-1]=now
print('Yes')
print(*dlist[1:],sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
path = [list(map(int, input().split())) for i in range(M)]

edges = [[] for j in range(N+1)]
for p in path:
    x, y = p
    edges[x].append(y)
    edges[y].append(x)

que = deque([])
dic = {1: 0}
def bfs(now):
    e = edges[now]
    for q in e:
        if not q in dic:
            dic[q] = now
            que.append(q)
    try:
        n = que.popleft()
        bfs(n)
    except IndexError:
        pass

bfs(1)

if len(dic) != N:
    print("No")
else:
    print('Yes')
    dic_sort = sorted(dic.items())
    for elem in dic_sort:
        if elem[0] != 1:
            print(elem[1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from collections import deque

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 = [-1] * (N + 1)
ans = [-1] * (N + 1)
que = deque()
root = 1
ans[root] = 0
que.append(root)
while que:
    now = que.popleft()
    for next_ in G[now]:
        if ans[next_] == -1:
            que.append(next_)
            ans[next_] = now

for i in ans[1:]:
    if i == -1:
        print ('No')
        exit()
print ('Yes')
print (*ans[2:], sep = '\n')

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

ans = [0]*(N-1)
next_root = [0]
zumi = {}
while True:
    # 次のルートが全部探索済みなら終わり
    for root in next_root:
        if not(root in zumi):
            break
    else:
        break

    tmp_next_root = []
    for root in next_root:
        if root in zumi:
            continue
        for v in tree[root]:
            if v in zumi:
                continue
            if ans[v-1] == 0:
                ans[v-1] = root+1
                tmp_next_root.append(v)
        zumi[root] = True
    next_root = tmp_next_root

if ans.count(0) == 0:
    print('Yes')
    for a in ans:
        print(a)
else:
    print('No')

Submission status: Accepted

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

que = []
seen = [-1 for i in range(n+1)]
back = [-1 for i in range(n+1)]

seen[1] = 0
que.append(1)

while len(que) != 0:
  now = que.pop(0)
  
  for nxt in cave[now]:
    if seen[nxt] != -1:
      continue
    
    seen[nxt] = seen[now] + 1
    back[nxt] = now
    que.append(nxt)
    
flag = True
for i in back[2:]:
  if i == -1:
    flag = False

if flag == True:
  print("Yes")
  for i in back[2:]:
    print(i)
else:
  print("No")

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  ans=[-1]*n

  q=collections.deque()
  v=[[] for _ in range(n)]
  for _ in range(m):
    a,b=LI()
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    if a==0:
      q.append((0,b,0))
    elif b==0:
      q.append((0,a,0))

  while q:
    moto,nxt,stp=q.popleft()
    if ans[nxt]==-1:
      ans[nxt]=moto
    else:
      continue

    for x in v[nxt]:
      if ans[x]==-1:
        q.append((nxt,x,stp+1))

  if -1 in ans[1:]:
    print('No')
    exit()

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

main()
# print(main())

Submission status: Accepted

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

rinsetu = {}
mitisirube = {}
kyori = {}
for i in range(1, N+1):
    rinsetu[i] = []
    mitisirube[i] = None
    kyori[i] = None
kyori[1]=0

for ab in AB:
    rinsetu[ab[0]].append(ab[1])
    rinsetu[ab[1]].append(ab[0])

queue = [1]
while queue:
    this = queue.pop(0)
    #print(this, ":", rinsetu[this])
    for r in rinsetu[this]:
        if kyori[r] is None:
            kyori[r] = kyori[this] + 1
            mitisirube[r] = this
            queue.append(r)


#for n in range(1, N+1):
#    print(n, ":", mitisirube[n], kyori[n])

all_mitisirube = [mitisirube[i] for i in range(2, N+1)]
if None in all_mitisirube:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(mitisirube[i])

Submission status: Accepted

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
def solve(N, M, graph):
    dist = {0: 0}
    queue = [0]
    parent = {}
    for node in queue:
        for nei in graph[node]:
            if nei not in dist:
                dist[nei] = dist[node] + 1
                parent[nei] = node
                queue.append(nei)

    if len(parent) != N - 1:
        return
    return [parent[i] for i in xrange(1, N)]

N, M = rrm()
graph = [[] for _ in xrange(N)]
for _ in xrange(M):
    u,v = rrm()
    u -= 1;v-=1
    graph[u].append(v)
    graph[v].append(u)
ans= solve(N,M,graph)
if ans is None:
    print "No"
else:
    print "Yes"
    for x in ans: print x+1

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
link=[[] for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  link[a-1].append(b-1)
  link[b-1].append(a-1)
q=[0]
visited=[0]*n
visited[0]=1
while q:
  x=q.pop(0)
  for i in link[x]:
    if visited[i]==0:
      visited[i]=x+1
      q.append(i)
print('Yes')
print(*visited[1:],sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/python3
from collections import defaultdict

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

paths = defaultdict(list)

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

checked = set([1])
ct = set([1])
rp = defaultdict(int)

while ct:
    nt = set()
    for r in ct:
        for nr in paths[r]:
            if nr in checked:
                continue
            rp[nr] = r
            checked.add(nr)
            nt.add(nr)
            
            
    ct = nt

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

Submission status: Accepted

Solution code:
import numpy
import queue

n,m=map(int,input().split())#n=room m=way

r=[]
for i in range(n):
    r.append([])

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

#reach=numpy.zeros(n,dtype=int)
mark=numpy.zeros(n,dtype=int)

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

while q.empty()==False:
    c=q.get()
    for i in iter(r[c-1]):
        if mark[i-1]==0:
            q.put(i)
            mark[i-1]=c


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 17 20:56:20 2020

@author: Kanaru Sato
"""
import collections

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

distance = [-1,0]
for i in range(n-1):
    distance.append(-1)

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

q = [1]
q = collections.deque(q)

while q:
    cp = q.popleft()
    for np in connected[cp]:
        if ans[np] == -1 or distance[ans[np]] > distance[cp]:
            q.append(np)
            ans[np] = cp
            distance[np] = distance[cp] + 1

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

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int, input().split())
rooms = [[] for _ in range(N)]

for _ in range(M):
    a, b= map(int,input().split())
    a -= 1
    b -= 1
    rooms[a].append(b)
    rooms[b].append(a)
reached = [-1]*N
def bfs():
    d = deque() 
    d.append(0)
    reached[0] = 0
    while d:
        # 現在の部屋
        now = d.popleft()
        for i in rooms[now]:
            # すでにその部屋を訪れていない
            if reached[i] == -1:
                reached[i] = now
                d.append(i)
bfs()
print('Yes')
for i in range(1,N):
    print(reached[i]+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify

N,M=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト

for _ in range(M):
	a,b=map(int, sys.stdin.readline().split())
	al[a].append(b)
	al[b].append(a)

d=[ float("inf") for _ in range(N+1)]
restore=[ None for _ in range(N+1)]

#Dijkstra
def dij(fro):
	d[fro]=0
	hq=[]
	heappush(hq,(0,fro))
	while hq:
		cost,fro=heappop(hq)
		for to in al[fro]:
			alt=d[fro]+1
			if alt<d[to]:
				d[to]=alt
				restore[to]=fro
				heappush(hq, (alt,to))

dij(1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(9**9)
n,m=map(int,input().split())
L=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
A=[0]+[-1]*(n-1)
B=[[0,L[0]]]
def wfs(A,B):
    C=[]
    f=False
    for b in B:
        for l in b[1]:
            if A[l]==-1:
                A[l]=b[0]
                C.append([l,L[l]])
                f=True
    if f:
        return wfs(A,C)
    else:
        print('Yes')
        for a in A[1:]:
            print(a+1)
wfs(A,B)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

for A, B in AB:
    doors[A-1].append(B)
    doors[B-1].append(A)
#print(doors)
#exit()

answer = [sys.maxsize for _ in range(N-1)]
distance = [sys.maxsize for _ in range(N)]
distance[0] = 0
q = deque([1])

while len(q) > 0:
  current = q.popleft()
  for nextroom in doors[current-1]:
    if distance[current-1] + 1 < distance[nextroom-1]:
        q.append(nextroom)
        distance[nextroom-1] = distance[current-1] + 1
        answer[nextroom-2] = current
    else:
        pass
if sys.maxsize in answer:
    print('No')
    exit()
print('Yes')
for a in answer:
    print(a)

Submission status: Accepted

Solution code:
from queue import Queue

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

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

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

shortest_adj = [None] * n
room_queue = Queue()
room_queue.put(0)
while not room_queue.empty():
    room = room_queue.get()
    for next_room in adj_list[room]:
        if shortest_adj[next_room] is None:
            shortest_adj[next_room] = room
            room_queue.put(next_room)

can_reach = all([x is not None for x in shortest_adj])

if not can_reach:
    print('No')
    exit()

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

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
paths = {}
for m in range(M):
	path = map(int, raw_input().split())
	a_p = paths.get(path[0],[])
	b_p = paths.get(path[1],[])
	a_p.append(path[1])
	b_p.append(path[0])
	paths[path[0]] = a_p
	paths[path[1]] = b_p

visited = [False] * (N+1)

visited[0] = True
to_visit = [1]
signposts = [None] * (N+1)
i = 0
while len(to_visit) > i:
	curr = to_visit[i]
	if visited[curr]:
		i += 1
	else:
		path = paths[curr]
		for p in path:
			if signposts[p] == None:
				signposts[p] = curr
				to_visit.append(p)
		visited[curr] = True
		i += 1
all_visited = all(visited)

if all_visited:
	print 'Yes'
	for s in range(2,len(signposts)):
		print signposts[s]
else:
	print 'No'

Submission status: Accepted

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

roads = [[] for _ in range(N)]
for _ in range(M):
    _from, _to = map(int, input().split())
    roads[_from-1].append(_to-1)
    roads[_to-1].append(_from-1)

visited = [False] * N
ans = [None] * N
visited[0] = True
prevs = [0]
for _ in range(N):
    next_prevs = []
    for prev in prevs:
        for to in roads[prev]:
            if not visited[to]:
                visited[to] = True
                ans[to] = prev
                next_prevs.append(to)
    prevs = next_prevs

if not all(visited):
    print("No")
    exit(0)
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())
path=[[] for i in range(n)]
start=[]
visited=[0]*n
visited[0]=1
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    start.append(b-1)
    visited[b-1]=1
  if b==1:
    start.append(a-1)
    visited[a-1]=1
  path[a-1].append(b-1)
  path[b-1].append(a-1)
que=deque(start)
while que:
  x=que.popleft()
  for i in path[x]:
    if visited[i]==0:
      visited[i]=x+1
      que.append(i)
print('Yes')
for i in range(n-1):
  print(visited[i+1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
li = []
for _ in range(m):
    tmp = list(map(int,input().split()))
    li.append(tmp)
#print(li)
ma = [[] for i in range(n)]
#print(ma)[[], [], [], []]
for l in li:
    a = l[0]-1
    b = l[1]-1
    ma[a].append(b)
    ma[b].append(a)
#print(ma)
# [[1], [0, 2, 3], [1, 3], [2, 1]]
ans = [-1]*(n) # 最後に先頭削除
q = [0]
while q:
    #print(q)
    que = q.pop(0)
    for e in ma[que]:
        if ans[e]== -1:
            ans[e] = que
            q.append(e)
ans.pop(0)
if -1 in ans:
    print('No')
else:
    print('Yes')
    for aaa in ans:
        print(aaa+1)

Submission status: Accepted

Solution code:
# D - 

import queue

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

INF = 10 ** 5 + 1
ans = [INF] * N
Q = queue.Queue()
Q.put(0)
ans[0] = 0
while not Q.empty():
    u = Q.get()
    for g in G[u]:
        if ans[g] == INF:
            ans[g] = u + 1
            Q.put(g)

if max(ans) == INF:
    print('No')
else:
    print('Yes')
    for i in range(1, len(ans)):
        print(ans[i])

Submission status: Accepted

Solution code:
input_list = lambda : list(map(int,input().split()))


#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node):
    c=[-1 for _ in range(n)]
    c[0]=0
    
    side_num_arr=list(map(lambda x :len(x),node))
    #print(l)
    queue=[-1 for _ in range(n)]
    now=0
    queue[now]=s
    ans=[-1 for _ in range(n)]
    ans[0]=[0]
    last_ind=1
    while last_ind<n:
        
        if now>=n:
            return []
        c[queue[now]]=True
        if side_num_arr[queue[now]]<=0:
            now+=1
            continue
        for edge in node[queue[now]]:
            #edge=i[0]
            if side_num_arr[edge]<=0 or c[edge]==True:
                continue
            side_num_arr[edge]-=1
            
            queue[last_ind]=edge
            last_ind+=1
            c[edge]=True
            ans[edge]=queue[now]

        side_num_arr[queue[now]]=0
        now+=1
    return ans



n,m=input_list()
node=[[] for _ in range(n)]

for i in range(m):
    u,v=input_list()
    u-=1
    v-=1
    node[u].append(v)
    node[v].append(u)

#print(np.array(node))

ans=bfs(0,n,node)
if len(ans)==0:
    print("No")
    exit()

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
import sys


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


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)
if len(set(graph.keys())) != N:
    print('No')
    exit()

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v]:
        if nv in visited:
            continue
        if tokens[nv] < 0:
            tokens[nv] = v
            q.append(nv)

print('Yes')
[print(t + 1) for t in tokens[1:]]

Submission status: Accepted

Solution code:
import collections


def bfs(dq, g, current, before, seen: {}):
    # reached = False
    while len(dq) > 0:
        base = dq.popleft()
        _crt = base[0]
        _cnt = base[1]
        _cnt2 = _cnt + 1
        _nxt = g[_crt]
        for x in _nxt:
            # さっき来たところなら行かない
            if x == before:
                continue
            # seen登録済ならスルー
            seen.setdefault(x, (-1, -1))
            if seen[x][0] != -1:
                continue
            # 次の探索候補に追加
            seen[x] = (_crt, _cnt2)
            dq.append((x, _cnt2))


def main():
    n, m = map(int, input().split())

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

    dq = collections.deque()
    # (current, count)
    dq.append((1, 1))

    seen = {1: (-1, 0)}

    bfs(dq, g, 1, -1, seen)

    if len(seen.keys()) != n:
        print("No")
    else:
        print("Yes")
        for i in range(2, n + 1):
            print(seen[i][0])


main()

Submission status: Accepted

Solution code:
def bfs(G,start):
    from collections import deque
    dist = [-1] * n
    dist[start] = 0
    parent = [-1] * n
    parent[start] = 0
    q = deque([start])
    add,pop=q.append,q.popleft
    while q:
        v = pop()
        for nv in G[v]:
            if dist[nv] < 0:
                dist[nv] = dist[v]+1
                parent[nv] = v+1
                add(nv)
            # 2部グラフ判定
            # else:
            #     if dist[v]%2 == dist[nv]%2:
            #         is_bipartite = False
    return dist,parent

import numpy as np
import math
n,m = map(int,input().split())
roads = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    roads[a-1].append(b-1)
    roads[b-1].append(a-1)
dist, parent = bfs(roads,0)
if -1 in dist:
    print('No')
else:
    print('Yes')
    for i in parent[1:]:
        print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
AB = []
d = defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    # A, B = A - 1, B - 1  # 0-indexed
    A, B = min(A, B), max(A, B)
    AB.append((A, B))
    d[A].append(B)
    d[B].append(A)
# print('AB', AB)
# print('d', d)

V = [-1] * (N + 1)
R = [-1] * (N + 1)
V[1] = 0

q = d[1]
for i in d[1]:
    R[i] = 1
cnt = 0
while True:
    cnt += 1
    qq = []
    for i in q:
        if V[i] != -1:
            continue
        V[i] = cnt
        for j in d[i]:
            if R[j] == -1:
                qq.append(j)
                R[j] = i
    # print('qq', qq, V, R)
    if qq:
        q = qq
    else:
        break
# print('V', V)
# print('R', R)

print('Yes')
for r in R[2:]:
    print(r)