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 sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

    node = [INF] * (N+1)
    ans = [-1] * (N+1)

    q = [(0,1,-1)]
    heapify(q)
    node[1] = 0

    while q:
        d,v,f = heappop(q)
        node[v] = d
        ans[v] = f
        for u in root[v]:
            if node[u] <= d+1: continue
            node[u] = d+1
            heappush(q,(d+1,u,v))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys


readline = sys.stdin.readline
readall = sys.stdin.read
ins = lambda: readline().rstrip()
ini = lambda: int(readline().rstrip())
inm = lambda: map(int, readline().split())
inl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')


n,m = inm()
W = [[] for _ in range(n)]
for _ in range(m):
    a,b = inm()
    W[a-1].append(b-1)
    W[b-1].append(a-1)

res = [0] * n
dis = [n] * n
dis[0] = 0

q = deque()
q.append(0)
while q:
    c = q.popleft()
    for i in W[c]:
        if dis[i] > dis[c] + 1:
            dis[i] = dis[c] + 1
            res[i] = c + 1
            q.append(i)

print('Yes')
prl(res[1:])

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
root = [set() for i in range(N + 1)]
ans = [0 for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    root[a].add(b)
    root[b].add(a)
task = deque([1])
itta = {1}
while len(task) > 0:
    now = task.popleft()
    additional = root[now] - itta
    for i in additional:
        ans[i] = now
        itta.add(i)
    task.extend(list(additional))
print("Yes")
for i in range(2, N + 1):
    print(ans[i])

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, M = nm()
adj = [[] for _ in range(N)]
for i in range(M):
    a, b = nm()
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


def solve():
    q = collections.deque([(0, 0, -1)])
    visited = [False] * N
    prev = [None] * N
    while q:
        l, node, pnode = q.popleft()
        if visited[node]:
            continue
        visited[node] = True
        prev[node] = pnode
        for nxt in adj[node]:
            if not visited[nxt]:
                q.append((l + 1, nxt, node))
    print("Yes")
    for i in range(1, N):
        print(prev[i] + 1)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math
from collections import deque
from collections import defaultdict

def readInt():
	return int(input())
def readInts():
	return map(int, input().split())
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq

n,m = map(int, input().split())
puted = [True]*(n+1)

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

q = deque([1])
flg = [-1]*n
flg[0] = 0

while q:
	item = q.popleft()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.append(i)
			puted[i]=False

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Submission status: Accepted

Solution code:
from collections import deque

n,m = list(map(int, input().split()))
puted = [True]*(n+1)

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

q = deque([1])
flg = [-1]*n
flg[0] = 0

while q:
	item = q.popleft()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.append(i)
			puted[i]=False

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Submission status: Accepted

Solution code:
from collections import deque

n,m = list(map(int, input().split()))
puted = [1]*(n+1)

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

q = deque([1])
flg = [-1]*n
flg[0] = 0

while q:
	item = q.popleft()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.append(i)
			puted[i]=0

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Submission status: Accepted

Solution code:
import queue

n,m = list(map(int, input().split()))
puted = [1]*(n+1)

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

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.put(i)
			puted[i]=0

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Submission status: Accepted

Solution code:
import queue

n,m = list(map(int, input().split()))
puted = [1]*(n+1)

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

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.put(i)
			puted[i]=0

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Submission status: Accepted

Solution code:
import queue

n,m = list(map(int, input().split()))
puted = [0]*(n+1)

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

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]==0:
			flg[i-1]=item
			q.put(i)
			puted[i]=1

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)

parent = {i:-1 for i in range(1,n+1)}
parent[1] = 0
q = [1]
while len(q):
    u = q.pop(0)
    for v in graph[u]:
        if parent[v] == -1:
            q.append(v)
            parent[v] = u

if -1 in list(parent.values()):
    print("No")
    exit()
print("Yes")
for i in range(2,n+1):
    print(parent[i])

Submission status: Accepted

Solution code:
import queue
n,m=map(int,input().split())
road_list=[set() for i in range(n)]
mitisirube=[0]*n
mitisirube[0]=1
for i in range(m):
    a,b=map(int,input().split())
    road_list[a-1].add(b)
    road_list[b-1].add(a)

q = queue.Queue()

counter_set=set()
counter_set.add(1)
for i in road_list[0]:
    q.put(i)
    mitisirube[i-1]=1
    counter_set.add(i)

while not q.empty():
    tmp=q.get()
    for i in road_list[tmp-1]:
        if i not in counter_set:
            q.put(i)
            counter_set.add(i)
            if mitisirube[i-1]==0:
                mitisirube[i-1]=tmp
print("Yes")
for i in range(1,len(mitisirube)):
    print(mitisirube[i])

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

from collections import deque

def bfs(graph,s,n):
    visited=[False for _ in xrange(n+1)]
    ans = [None for _ in xrange(n+1)]
    stack=deque([s])
    while stack:
        node=stack.popleft()
        for nodes in graph[node]:
            if not visited[nodes]:
                if ans[nodes] is None:
                    ans[nodes] = str(node)
                stack.append(nodes)
                visited[nodes] = True
    return ans


n,m = (int(x) for x in input().split())
graph = dict()
for x in xrange(m):
    a,b = (int(x) for x in input().split())
    try:
        graph[a].append(b)
    except:
        graph[a] = [b]
    try:
        graph[b].append(a)
    except:
        graph[b] = [a]
ans = bfs(graph,1,n)
print('Yes')
print('\n'.join(ans[2:]))

Submission status: Accepted

Solution code:
#BFS(幅優先探索のテンプレート)
from collections import deque
inf = float("INF")
 
N,M = map(int,input().split())
path = [[] for i in range(N)]
dist = [inf for i in range(N)]
visited = [0 for i in range(N)]
 
for _ in range(M):
    a,b = map(int,input().split())
    a = a - 1
    b = b - 1
    path[a].append(b)
    path[b].append(a)
 
def bfs(path,root,visited):
    #頂点の距離は0
    dist[root] = 0
    #頂点0を初期ノードに設定、訪問済みにする
    visited[root] = 1
    #初期ノードをキューに追加
    queue = deque([root])
    #BFS開始(キューが空になるまで行う)
    while queue:
        #キューから先頭頂点を取り出す
        current = queue.popleft()
        for i in path[current]:
            #すでに訪問図済みの頂点は探索しない
            if visited[i] == 1:
                continue
            else:
                #新たな頂点iに対して距離情報を更新してキューに追加
                dist[i] = current + 1#距離情報の更新
                visited[i] = 1#訪問済みにする
                queue.append(i)#キューに追加
 
    if all([i == 1 for i in visited]):
        return "Yes"
    else:
        return "No"
 
flag = bfs(path,0,visited)
print(flag)
 
if flag == "Yes":
    for i in range(1,N):
        print(dist[i])

Submission status: Accepted

Solution code:
# D - .. (Double Dots)
from collections import deque
from typing import List


def bfs(source, graph: List[List[int]], signposts: List[int]) -> None:
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not signposts[v]:
                signposts[v] = u
                queue.append(v)


def main():
    N, M, *AB = map(int, open(0).read().split())

    graph = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(AB)] * 2):
        graph[a].append(b)
        graph[b].append(a)

    signposts = [0] * (N + 1)
    signposts[1] = 1
    bfs(1, graph, signposts)

    print("Yes")
    print("\n".join(map(str, signposts[2:])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split()) #n:頂点数　w:辺の数


way = [[] for i in range(N)]
depth = [float("inf") for i in range(N)]
visited = [False for i in range(N)]
que=[0]

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

for i in que:
  for j in way[i]:
    if visited[j]:
      continue
    que.append(j)
    visited[j]=True
    depth[j] = min(i+1,depth[j])
print("Yes")
for i in range(1,N):
  print(depth[i])

Submission status: Accepted

Solution code:
# D - .. (Double Dots)
from collections import deque


def main():
    N, M, *AB = map(int, open(0).read().split())

    graph = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(AB)] * 2):
        graph[a].append(b)
        graph[b].append(a)

    # bfs
    queue = deque([1])
    signposts = [0] * (N + 1)
    signposts[1] = 1
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not signposts[v]:
                signposts[v] = u
                queue.append(v)

    if all(signposts[2:]):
        print("Yes")
        print("\n".join(map(str, signposts[2:])))
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    p = q.get()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.put(c)
print('Yes')
for i in range(2,n+1): print(ans[i])

Submission status: Accepted

Solution code:
# D - .. (Double Dots)
from collections import deque


def main():
    N, M, *AB = map(int, open(0).read().split())

    graph = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(AB)] * 2):
        graph[a].append(b)
        graph[b].append(a)

    # bfs
    depth = [1 << 30] * (N + 1)
    depth[1] = 0
    queue = deque([(1, 0)])
    while queue:
        u, cur_depth = queue.popleft()
        next_depth = cur_depth + 1
        for v in graph[u]:
            if depth[v] > next_depth:
                depth[v] = next_depth
                queue.append((v, next_depth))

    # place signposts
    signposts = [0] * (N + 1)
    for u, cur_depth in enumerate(depth[2:], 2):
        prev_depth = cur_depth - 1
        for v in graph[u]:
            if depth[v] == prev_depth:
                signposts[u] = v
                break

    print("Yes")
    print("\n".join(map(str, signposts[2:])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - .. (Double Dots)
from collections import deque


def main():
    N, M, *AB = map(int, open(0).read().split())

    graph = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(AB)] * 2):
        graph[a].append(b)
        graph[b].append(a)

    # bfs
    depth = [1 << 30] * (N + 1)
    depth[1] = 0
    queue = deque([(1, 0)])
    while queue:
        u, cur_depth = queue.popleft()
        next_depth = cur_depth + 1
        for v in graph[u]:
            if depth[v] > next_depth:
                depth[v] = next_depth
                queue.append((v, next_depth))

    # place signposts
    signposts = [0] * (N + 1)
    for u, cur_depth in enumerate(depth[2:], 2):
        prev_depth = cur_depth - 1
        for v in graph[u]:
            if depth[v] == prev_depth:
                signposts[u] = v
                break
        if not signposts[u]:
            print("No")
            return

    print("Yes")
    print("\n".join(map(str, signposts[2:])))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
  N, M = map(int, readline().split())
  dist = {}
  pre = {}
  A = {}
  for i in range(N):
    dist[i+1] = -1
    pre[i+1] = -1
    A[i+1] = []
  dist[1] = 0
  pre[1] = 0
  for i in range(M):
    ai, bi = map(int, readline().split())
    A[ai].append(bi)
    A[bi].append(ai)
  cnt = 1
  depth = 1
  D = [1]
  while cnt < N:
    next = []
    for i in range(len(D)):
      for j in range(len(A[D[i]])):
        if dist[A[D[i]][j]] == -1:
          dist[A[D[i]][j]] = depth
          pre[A[D[i]][j]] = D[i]
          next.append(A[D[i]][j])
          cnt += 1
    D = next
    depth += 1
    if len(next) == 0:
      break
    elif depth > N:
      break
  if cnt == N:
    print('Yes')
    for i in range(1, N):
      print(pre[i+1])
  else:
    print('No')

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:

from collections import defaultdict
CH = defaultdict(list)

N, M = map(int, input().split())
P = [[] for _ in range(N)]
ans = [0] * (N-1)

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

#print(P)

def bfs(s):
    d = [-1] * N
    d_pre = [0] * N
    d[s-1] = 0
    p_old = [s]
    cnt = 1
    #print(d, d_pre, p_old)
    while p_old:
      p_new = []
      for i in p_old:
        for j in P[i-1]:
          if d[j-1] == -1:
            d[j-1] = cnt
            d_pre[j-1] = i
            p_new.append(j)
      p_old = p_new
      cnt += 1
      #print(d, d_pre, p_old)
    return d_pre

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

Submission status: Accepted

Solution code:
from collections import deque

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

room_q = deque()
room_q.append(1)
michihsirube_room = [-1 for _ in range(N + 1)]
while room_q:
    node = room_q.popleft()
    for near_room_id in relation_list[node]:
        if michihsirube_room[near_room_id] == -1:
            michihsirube_room[near_room_id] = node
            room_q.append(near_room_id)
print('Yes')
for i in range(2, N + 1):
    print(michihsirube_room[i])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = [[] for _ in range(n)] 
 
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
from collections import deque
 
def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0 
    l = [[] for _ in range(n)] 
    dic = {}
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                l[i].append(v)
                dic[i] = v
    return d,l,dic
d,l,dic = bfs(0)
if None in d:
    print("No")
else:
    print("Yes")
    l.remove(l[0])
    [print(i[0]+1) for i in l]

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from collections import deque
sys.setrecursionlimit(10 ** 9)
inf = float("inf")
readline = sys.stdin.buffer.readline
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
nt = lambda: tuple(map(int, readline().split()))

# BFS
def main():
    N, M = nm()
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = nm()
        a, b = a-1, b-1
        edges[a].append(b)
        edges[b].append(a)

    ans = [-1] * N
    deq = deque([0])
    while deq:
        node = deq.popleft()
        for next_node in edges[node]:
            # ans[next_node] == -1 -> not seen
            if ans[next_node] == -1:
                ans[next_node] = node
                deq.append(next_node)
    print("Yes")
    [print(i+1) for i in ans[1:]]

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

is_reachable = True

d = deque()
is_visited = [False] * N
rooms = [-1] * N
distance = [0] * N

d.append(0)
is_visited[0] = 1

while (d):
    v = d.popleft()

    for u in adj[v]:
        if is_visited[u]:
            continue

        is_visited[u] = 1
        rooms[u] = v+1
        distance[u] = distance[v] + 1
        d.append(u)

for i in range(1, N):
    d1 = distance[i]
    sign1 = rooms[i]-1
    if d1 <= distance[sign1]:
        is_reachable = False

if is_reachable:
    print("Yes")
    print(*rooms[1:], sep="\n")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

    for i in range(len(e[node])):
        nex = e[node][i]
        if t[nex] == -1:
            q.append(nex)
            t[nex] = node
print("Yes")
for i in range(2,n+1):
    print(t[i])

Submission status: Accepted

Solution code:
def resolve():
    N, M = [int(i) for i in input().split()]
    path = [[] for _ in range(N)]
    for _ in range(M):
        A, B = [int(i) for i in input().split()]
        path[A - 1].append(B - 1)
        path[B - 1].append(A - 1)
    visited = [-1] * N
    que = [0]
    visited[0] = 0

    while que:
        v = que.pop(0)
        for nv in path[v]:
            if visited[nv] != -1:
                continue
            visited[nv] = v + 1
            que.append(nv)

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


resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

edges=[[] for _ in range(n)]#[[１番目の部屋からいける部屋],[２番目の部屋からいける部屋]...]

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

todo=deque([[0,0]])
seen=[-1]*n
seen[0]=0

while todo:
    node,parent=todo.popleft()#現在探索している部屋、その親
    
    for to in edges[node]:
        if seen[to]!=-1:
            continue

        todo.append([to,node])
        seen[to]=node

print('Yes')

for parent in seen[1:]:
    print(parent+1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
input = sys.stdin.readline
#INF = 1145141919810893364
#S,L,R = map(int, input().split())

#入力、ついでに辺集合を作る
N,M = map(int,input().split())
edge = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a-=1;b-=1
    edge[a].append(b)
    edge[b].append(a)


#BFSの準備
Ans = [-1]*N;
visited = [False]*N;
Queue = deque([0])

#BFS
while(Queue):
    t = Queue.popleft()
    for v in edge[t]:
        if visited[v]:
            continue
        Queue.append(v)
        Ans[v]=t
        visited[v]=True
    
#Noの条件を満たさないかどうかチェック
#余談:今回はNoにならないことを示せる
for i in range(1,N):
    if Ans[i]==-1:
        print("No")
        sys.exit()
    
#答えの出力
print("Yes")
for i in range(1,N):
    print(Ans[i]+1)

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True

    #次見る頂点を格納するキュー
    queue=deque([s])

    visited_num=1

    #問題固有の配列
    ans=[-1 for _ in range(n)]
    ans[0]=0
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return []

        now_vertex=queue.popleft()
        #インデックスがない場合は
        #for next_vertex in node[now_vertex]:
        for each_node_arr in node[now_vertex]:
            #探索する頂点とインデックス
            next_vertex=each_node_arr[0]
            next_ind=each_node_arr[1]

            if check[next_vertex]==True:
                continue
            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            ans[next_vertex]=now_vertex+1
            visited_num+=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,i])
    node[v].append([u,i])

#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)

Submission status: Accepted

Solution code:
n,m=[int(j)for j in input().split()]
l=[[]for i in range(n+1)]
for i in range(m):
    a,b=[int(j)for j in input().split()]
    l[a].append(b)
    l[b].append(a)
ans=[0]*(n+1)
from collections import deque
q=deque([1])
s=set([1])
while q:
    i=q.popleft()
    for k in l[i]:
        if k not in s:
            ans[k]=i
            q.append(k)
            s.add(k)

if 0 not in ans[2:]:
    print("Yes")
    print('\n'.join(map(str,ans[2:])))
else:
    print("No")

Submission status: Accepted

Solution code:
#BFS(幅優先探索のテンプレート)
from collections import deque
inf = float("INF")

N,M = map(int,input().split())
path = [[] for i in range(N)]
dist = [inf for i in range(N)]
visited = [0 for i in range(N)]

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

def bfs(path,root,visited):
    #頂点の距離は0
    dist[root] = 0
    #頂点0を初期ノードに設定、訪問済みにする
    visited[root] = 1
    #初期ノードをキューに追加
    queue = deque([root])
    #BFS開始(キューが空になるまで行う)
    while queue:
        #キューから先頭頂点を取り出す
        current = queue.popleft()
        for i in path[current]:
            #すでに訪問図済みの頂点は探索しない
            if visited[i] == 1:
                continue
            else:
                #新たな頂点iに対して距離情報を更新してキューに追加
                dist[i] = current + 1#距離情報の更新
                visited[i] = 1#訪問済みにする
                queue.append(i)#キューに追加

    if all([i == 1 for i in visited]):
        return "Yes"
    else:
        return "No"

flag = bfs(path,0,visited)
print(flag)

if flag == "Yes":
    for i in range(1,N):
        print(dist[i])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [[] for _ in range(N)]
ans = [0]*N
for _ in range(M):
  a,b = map(int,input().split())
  AB[a-1].append(b-1)
  AB[b-1].append(a-1)

from collections import deque

node = 0
q = deque([0])

check = [0]*N
check[0] = 1
while len(q) > 0:
  node = q.popleft()
  for i in AB[node]:
    if check[i] == 0:
      q.append(i)
      check[i] = 1
      ans[i] = node
print("Yes")
for i in range(1,N):
  print(ans[i]+1)

Submission status: Accepted

Solution code:
print("Yes")
N, M = map(int, input().split())
path = [[] for _ in range(N)]
ind = [0 for _ in range(N)]
lis = [0] + [1 for _ in range(N-1)]
for i in range(M):
    A, B = map(int, input().split())
    path[A-1].append(B-1)
    path[B-1].append(A-1)
que = path[0]
for p in que:
    lis[p] = 0
for l in que:
    U = path[l]
    for m in U:
        if lis[m] ==1:
            ind[m] = l
            lis[m] = 0
            que.append(m)
    if lis == {}:
        break
for z in range(1,N):
    ind[z] += 1
    print(ind[z])

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
graph = [[] for j in range(N)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node

if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)