Someone give a strange birthday present to Ivan. It is hedgehog — connected undirected graph in which one vertex has degree at least $3$ (we will call it center) and all other vertices has degree 1. Ivan thought that hedgehog is too boring and decided to make himself $k$-multihedgehog.

Let us define $k$-multihedgehog as follows: $1$-multihedgehog is hedgehog: it has one vertex of degree at least $3$ and some vertices of degree 1. For all $k \ge 2$, $k$-multihedgehog is $(k-1)$-multihedgehog in which the following changes has been made for each vertex $v$ with degree 1: let $u$ be its only neighbor; remove vertex $v$, create a new hedgehog with center at vertex $w$ and connect vertices $u$ and $w$ with an edge. New hedgehogs can differ from each other and the initial gift. 

Thereby $k$-multihedgehog is a tree. Ivan made $k$-multihedgehog but he is not sure that he did not make any mistakes. That is why he asked you to check if his tree is indeed $k$-multihedgehog.


-----Input-----

First line of input contains $2$ integers $n$, $k$ ($1 \le n \le 10^{5}$, $1 \le k \le 10^{9}$) — number of vertices and hedgehog parameter.

Next $n-1$ lines contains two integers $u$ $v$ ($1 \le u, \,\, v \le n; \,\, u \ne v$) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.


-----Output-----

Print "Yes" (without quotes), if given graph is $k$-multihedgehog, and "No" (without quotes) otherwise.


-----Examples-----
Input
14 2
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6

Output
Yes

Input
3 1
1 3
2 3

Output
No



-----Note-----

2-multihedgehog from the first example looks like this:

[Image]

Its center is vertex $13$. Hedgehogs created on last step are: [4 (center), 1, 2, 3], [6 (center), 7, 8, 9], [5 (center), 10, 11, 12, 13].

Tree from second example is not a hedgehog because degree of center should be at least $3$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Shortest paths


Solutions:
from collections import deque
(n, k) = list(map(int, input().split()))
Gg = [set() for _ in range(n + 1)]
(q, nq) = (deque(), deque())
for _ in range(n - 1):
	(u, v) = list(map(int, input().split()))
	Gg[u].add(v)
	Gg[v].add(u)
for u in range(1, n + 1):
	if len(Gg[u]) == 1:
		q.append(u)
step = 0
removed = 0
ok = True
while removed < n - 1:
	each = {}
	for u in q:
		nxt = Gg[u].pop()
		Gg[nxt].remove(u)
		each[nxt] = each.get(nxt, 0) + 1
		removed += 1
		if len(Gg[nxt]) == 0:
			break
		if len(Gg[nxt]) == 1:
			nq.append(nxt)
	if any((v < 3 for (k, v) in each.items())):
		ok = False
		break
	(q, nq) = (nq, deque())
	step += 1
if ok and step == k and (removed == n - 1):
	print('Yes')
else:
	print('No')


from collections import deque
(n, k) = map(int, input().split())
d = {}
for i in range(n):
	d[i + 1] = set()
for i in range(n - 1):
	(u, v) = map(int, input().split())
	d[u].add(v)
	d[v].add(u)
dist = {}
prev = {}
dist[1] = 0
q = deque()
q.append(1)
while len(q) > 0:
	cur = q.popleft()
	for x in d[cur]:
		if x not in dist:
			prev[x] = cur
			dist[x] = dist[cur] + 1
			q.append(x)
answer = True
if k > dist[cur]:
	answer = False
else:
	for i in range(k):
		cur = prev[cur]
	dist2 = {}
	dist2[cur] = 0
	q = deque()
	q.append(cur)
	while len(q) > 0:
		cur2 = q.popleft()
		if cur2 == cur and len(d[cur]) < 3:
			answer = False
			break
		if len(d[cur2]) == 1:
			if dist2[cur2] != k:
				answer = False
				break
		elif len(d[cur2]) < 4 and cur2 != cur:
			answer = False
			break
		for x in d[cur2]:
			if x not in dist2:
				dist2[x] = dist2[cur2] + 1
				q.append(x)
if answer:
	print('Yes')
else:
	print('No')


def push(d, u, v):
	if u not in d:
		d[u] = []
	if v not in d:
		d[v] = []
	d[u].append(v)
	d[v].append(u)

def push_v(d, u, val):
	if u not in d:
		d[u] = 0
	d[u] += val
(n, k) = map(int, input().split())
g = {}
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	push(g, u, v)
deg1 = []
used = [0] * (n + 1)
for u in g:
	if len(g[u]) == 1:
		used[u] = 1
		deg1.append(u)
flg = True
while k > 0:
	if k >= 1 and len(deg1) < 3:
		flg = False
		break
	cnt = {}
	for u in deg1:
		for v in g[u]:
			if used[v] == 0:
				push_v(cnt, v, 1)
	for v in deg1:
		used[v] = 1
	deg1 = []
	for (v, val) in cnt.items():
		if val < 3:
			flg = False
			break
		deg1.append(v)
	if flg == False:
		break
	k -= 1
if flg == True and len(deg1) > 1:
	flg = False
if flg == False:
	print('NO')
else:
	print('YES')


import sys
input = sys.stdin.buffer.readline
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root, depth):
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					if depth[i] != depth[element] + 1:
						return False
					queue.append(i)
					self.parent[i] = element
		return True

	def dfs(self, root, ans):
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					ans[i] = ans[element] + 1
					queue.append(i)
					self.parent[i] = element
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def ifcycle(self):
		self.bfs(0)
		queue = [0]
		vis = [0] * n
		queue = deque(queue)
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in graph[element]:
				if vis[i] == 1 and i != parent[element]:
					return True
				if vis[i] == 0:
					queue.append(i)
					vis[i] = 1
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue

	def lastcheck(self, root, depth):
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			if depth[element] != k + 1 and len(self.graph[element]) <= 3 and (element != root):
				return False
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
		return True

	def check(self):
		root = -1
		for i in range(self.n):
			if len(self.graph[i]) == 1:
				root = i
				break
		if root == -1:
			return False
		depth = [1] * self.n
		depth = self.dfs(root, depth)
		end = -1
		for i in range(self.n):
			if depth[i] == 2 * k + 1:
				end = i
				for j in range(k):
					end = self.parent[end]
					if end == -1:
						return False
				break
		if end == -1:
			return False
		root = end
		depth = [1] * self.n
		depth = self.dfs(root, depth)
		for i in range(self.n):
			if len(self.graph[i]) == 1 and depth[i] != k + 1:
				return False
			if len(self.graph[i]) == 2:
				return False
		if self.lastcheck(root, depth):
			return True
		return False
(n, k) = map(int, input().split())
g = Graph(n, False)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g.addEdge(u - 1, v - 1)
if g.check():
	print('Yes')
else:
	print('No')


from sys import stdin
from collections import deque
(n, k) = map(int, stdin.readline().split())
graph = [[] for _ in range(n)]
leaf = -1
for _ in range(n - 1):
	(a, b) = map(int, stdin.readline().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)

def bfs(G, s):
	Q = deque()
	Q.append(s)
	infinite = 10 ** 6
	d = [infinite] * n
	parent = [-1] * n
	valid = True
	d[s] = 0
	while Q:
		u = Q.popleft()
		not_visited_count = 0
		for v in G[u]:
			if d[v] == infinite:
				d[v] = d[u] + 1
				parent[v] = u
				Q.append(v)
				not_visited_count += 1
		if not_visited_count < 3 and d[u] != k:
			valid = False
	return (d, parent, valid)
leaf = -1
for (i, v) in enumerate(graph):
	if len(v) == 1:
		leaf = i
		break
(d, parent, _) = bfs(graph, leaf)
center = -1
farthest_leaf = -1
path = 2 * k
for (i, level) in enumerate(d):
	if level == path:
		farthest_leaf = i
		break
if len(graph[farthest_leaf]) != 1 or farthest_leaf == -1:
	print('NO')
	exit()
for _ in range(k):
	center = parent[farthest_leaf]
	farthest_leaf = center
(_, _, valid) = bfs(graph, center)
if valid:
	print('YES')
else:
	print('NO')


from collections import defaultdict
(n, k) = map(int, input().split())
connections = defaultdict(set)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	connections[u].add(v)
	connections[v].add(u)
leafs = set()
for node in connections:
	if len(connections[node]) == 1:
		leafs.add(node)
steps = 0
is_correct = True
while is_correct and steps <= k:
	new_leafs = set()
	for x in leafs:
		if len(connections[x]) > 1:
			is_correct = False
			break
		root = list(connections[x])[0]
		if len(connections[root]) < 4 and len(leafs) != 3:
			is_correct = False
			break
	if not is_correct:
		break
	for x in leafs:
		root = list(connections[x])[0]
		new_leafs.add(root)
		connections[root].remove(x)
	leafs = new_leafs
	steps += 1
	if len(leafs) == 1 and len(connections[list(leafs)[0]]) == 0:
		break
if is_correct and steps == k:
	print('Yes')
else:
	print('No')


from collections import Counter
(n, k) = map(int, input().split())
if k >= 20 or n <= 3:
	print('No')
	exit(0)
edges = [set() for _ in range(n)]
survived = list(range(n))
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edges[a - 1].add(b - 1)
	edges[b - 1].add(a - 1)
for _ in range(k):
	leaves = []
	new_survived = []
	for i in survived:
		if len(edges[i]) == 0:
			print('No')
			exit(0)
		elif len(edges[i]) == 1:
			leaves.append(i)
		else:
			new_survived.append(i)
	if len(new_survived) == 2:
		print('No')
		exit(0)
	removed = Counter()
	for i in leaves:
		nei = edges[i].pop()
		edges[nei].remove(i)
		removed[nei] += 1
	if min(removed.values()) < 3:
		print('No')
		exit(0)
	survived = new_survived
if len(survived) == 1:
	print('Yes')
else:
	print('No')


from sys import stdin
from collections import deque
(n, k) = map(int, stdin.readline().split())
graph = [set() for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, stdin.readline().split())
	graph[a - 1].add(b - 1)
	graph[b - 1].add(a - 1)
leafs = [i for (i, v) in enumerate(graph) if len(v) == 1]
new_leafs = []
valid = True
centers = dict()
count = 0
while len(leafs) > 1 and valid:
	for leaf in leafs:
		center = graph[leaf].pop()
		try:
			centers[center] += 1
		except KeyError:
			centers[center] = 1
		graph[center].remove(leaf)
		if len(graph[center]) == 0:
			break
		elif len(graph[center]) == 1:
			new_leafs.append(center)
	if any((mult < 3 for mult in centers.values())):
		valid = False
		break
	count = count + 1
	leafs = new_leafs
	new_leafs = []
	centers = {}
if valid and count == k:
	print('YES')
else:
	print('NO')


(n, k) = map(int, input().split(' '))
degrees = [0] * n
neighbors = [list() for x in range(n)]
for i in range(n - 1):
	(first, second) = map(int, input().split(' '))
	degrees[first - 1] += 1
	degrees[second - 1] += 1
	neighbors[first - 1] += [second]
	neighbors[second - 1] += [first]
curr = 0
for i in range(n):
	if degrees[i] == 1:
		curr = i + 1
		break
if curr == 0 or len(neighbors[curr - 1]) == 0:
	print('No')
	exit()
curr = neighbors[curr - 1][0]

def check(prev, parent, curr, level, degrees, neighbors, k):
	if level == 0:
		return (len(parent) == 1 and degrees[curr - 1] == 1, [])
	checked = []
	for neighbor in neighbors[curr - 1]:
		if len(prev) != 0 and prev[0] == neighbor:
			checked += [neighbor]
			continue
		if len(parent) != 0 and parent[0] == neighbor:
			continue
		(result, garbage) = check([], [curr], neighbor, level - 1, degrees, neighbors, k)
		if result:
			checked += [neighbor]
		elif len(parent) == 0:
			parent += [neighbor]
		else:
			return (False, [])
	if len(checked) > 2 and len(parent) == 0 and (level == k):
		return (True, [])
	elif len(checked) > 2 and len(parent) == 1 and (level != k):
		return (True, parent)
	else:
		return (False, [])
prev = []
parent = []
counter = 1
while counter <= k:
	(result, parent) = check(prev, [], curr, counter, degrees, neighbors, k)
	if not result:
		print('No')
		exit()
	if counter == k:
		print('Yes')
		exit()
	prev = [curr]
	curr = parent[0]
	counter += 1


import math
(n, k) = map(int, input().split())
edges = []
for i in range(n - 1):
	edges.append(tuple(map(int, input().split())))
degreelist = []
for i in range(min(k + 1, math.floor(math.log2(n)) + 10)):
	degreelist.append({})
degrees = degreelist[0]
for i in range(1, n + 1):
	degrees[i] = 0
for guy in edges:
	degrees[guy[0]] += 1
	degrees[guy[1]] += 1
small = []
center = None
done = False
for i in range(k):
	if not done:
		small = []
		for guy in degrees:
			if degrees[guy] == 2:
				print('No')
				done = True
				break
			if degrees[guy] == 3:
				small.append(guy)
				if center == None:
					center = guy
				elif center != guy:
					print('No')
					done = True
					break
			elif degrees[guy] > 1:
				small.append(guy)
		degrees = degreelist[i + 1]
		if center != None and center not in small:
			if not done:
				print('No')
			done = True
			break
		elif len(small) == 0:
			if not done:
				print('No')
			done = True
			break
		for guy in small:
			degrees[guy] = 0
		for guy in edges:
			if guy[0] in degrees and guy[1] in degrees:
				degrees[guy[0]] += 1
				degrees[guy[1]] += 1
		for guy in degrees:
			if degrees[guy] > 1 and degreelist[i][guy] != degrees[guy]:
				if not done:
					print('No')
				done = True
				break
	else:
		break
if not done:
	if len(degreelist[-1]) == 1:
		print('Yes')
	else:
		print('No')