1067_B. Multihedgehog_28526
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 ≥ 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 ≤ n ≤ 10^{5}, 1 ≤ k ≤ 10^{9}) — number of vertices and hedgehog parameter.

Next n-1 lines contains two integers u v (1 ≤ u,    v ≤ n;    u ≠ 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.
from __future__ import division
from fileinput import input
from collections import defaultdict, deque

inp = input()
n, k = map(int, inp.readline().split())

graph = defaultdict(list)
for _ in range(n - 1):
    u, v = map(int, inp.readline().split())
    graph[u].append(v)
    graph[v].append(u)


def bfs(a):
    todo = deque()
    todo.append(a)
    vis = set()
    vis.add(a)
    fro = {}

    while len(todo) > 0:
        cur = todo.popleft()
        last = cur
        for ne in graph[cur]:
            if ne not in vis:
                vis.add(ne)
                todo.append(ne)
                fro[ne] = cur
    return last, fro


v2, _ = bfs(1)
v3, fro = bfs(v2)

path = [v3]
cur = v3
while cur in fro:
    path.append(fro[cur])
    cur = fro[cur]

if len(path) != k*2 + 1:
    print "No"
    exit()
mid = path[len(path) // 2]


def hh(mid, k, p):
    if k == 1:
        count = 0
        for ne in graph[mid]:
            if ne != p:
                count += 1
                if len(graph[ne]) != 1:
                    return False
        return count >= 3
    count = 0
    for ne in graph[mid]:
        if ne != p:
            count += 1
            if not hh(ne, k - 1, mid):
                return False
    return count >= 3


if hh(mid, k, 1000000000000):
    print "Yes"
else:
    print "No"

3 1
1 3
2 3
 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
 13 2
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
 14 3
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
 18 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
13 15
15 16
15 17
15 18
 25 2
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
4 14
14 15
14 16
14 17
4 18
18 19
18 20
18 21
1 22
22 23
22 24
22 25
 22 2
1 4
2 4
3 4
5 8
6 8
7 8
9 12
10 12
11 12
13 16
14 16
15 16
17 20
18 20
19 20
4 21
8 21
12 21
4 22
16 22
20 22
 33 2
3 13
17 3
2 6
5 33
4 18
1 2
31 5
4 19
3 16
1 3
9 2
10 3
5 1
5 28
21 4
7 2
1 4
5 24
30 5
14 3
3 11
27 5
8 2
22 4
12 3
20 4
26 5
4 23
32 5
25 5
15 3
29 5
 16 2
1 12
2 12
3 12
4 13
5 13
6 13
7 16
8 16
9 15
10 15
11 15
12 14
13 14
16 14
15 14
 8 2
8 2
2 5
5 1
7 2
2 4
3 5
5 6
 5 1
4 1
3 1
5 1
1 2
 1 1
 13 2
7 5
10 11
5 12
1 2
10 7
2 6
10 4
9 5
13 10
2 8
3 10
2 7
 2 1
2 1
 14 1
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
 10 980000000
5 4
7 1
3 2
10 6
2 8
6 4
7 9
1 8
3 10
 4 1
2 3
4 2
1 2
 2 1
1 2
 8 1
8 2
2 5
5 1
7 2
2 4
3 5
5 6
 16 2
1 12
2 12
3 12
4 13
5 13
6 13
7 14
8 14
9 15
10 15
11 15
12 16
13 16
14 16
15 16
 13 1000000000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
 7 1
1 2
1 3
1 4
5 1
1 6
1 7
 21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21
 18 2
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
1 7
8 6
13 6
9 6
13 15
15 16
15 17
15 18
 18 2
1 4
2 4
3 4
4 13
10 6
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6
13 15
15 16
15 17
15 18
 8 2
8 2
4 5
5 1
7 2
2 4
3 5
5 6
 5 1
4 1
3 2
5 1
1 2
 16 3
1 12
2 12
3 12
4 13
5 13
6 13
7 14
8 14
9 15
10 15
11 15
12 16
13 16
14 16
15 16
 21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
14 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21
 13 2
1 2
2 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
 33 2
3 13
17 3
2 6
5 33
4 18
1 2
31 5
4 19
3 16
1 3
9 2
10 3
5 1
5 28
21 4
7 2
1 4
5 24
30 5
14 3
3 11
27 5
8 2
22 4
12 3
20 4
26 5
4 23
32 1
25 5
15 3
29 5
 8 2
8 2
2 5
3 1
7 2
2 4
3 5
5 6
 1 1
4 1
3 1
5 1
1 2
 1 2
 2 2
2 1
 10 980000000
5 4
7 1
3 2
10 6
3 8
6 4
7 9
1 8
3 10
 4 1
2 3
4 1
1 2
 13 1000000000
1 2
1 3
1 4
1 5
2 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
 33 2
4 13
17 3
2 6
5 33
4 18
1 2
31 5
4 19
3 16
1 3
9 2
10 3
5 1
5 28
21 4
7 2
1 4
5 24
30 5
14 3
3 11
27 5
8 2
22 4
12 3
20 4
26 5
4 23
32 1
25 5
15 3
29 5
 14 3
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 4
13 6
9 6
 22 2
1 4
2 4
3 4
5 8
6 8
7 8
9 12
10 12
11 12
13 16
14 16
15 16
17 20
18 20
19 20
4 21
8 21
12 1
4 22
16 22
20 22
 8 1
8 2
2 5
5 1
7 2
2 4
3 4
5 6
 10 980000000
5 4
7 1
3 2
10 6
2 8
1 4
7 9
1 8
3 10
 4 1
1 3
4 2
1 2
 8 1
8 2
2 5
6 1
7 2
2 4
3 5
5 6
 21 2
3 1
4 1
5 2
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21
 21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
20 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21
 1 1
4 1
3 1
6 1
1 2
 10 1323614652
5 4
7 1
3 2
10 6
3 8
6 4
7 9
1 8
3 10
 33 2
4 13
17 3
2 6
5 33
4 18
1 2
31 5
4 19
3 16
1 3
9 2
10 3
5 1
5 28
21 4
7 2
1 4
5 24
30 5
14 3
3 11
27 5
8 2
22 4
12 3
20 4
26 5
4 23
32 1
25 5
15 6
29 5
 22 2
1 4
2 4
3 4
5 8
6 8
7 8
9 14
10 12
11 12
13 16
14 16
15 16
17 20
18 20
19 20
4 21
8 21
12 1
4 22
16 22
20 22
 8 1
8 2
2 5
5 1
7 1
2 4
3 4
5 6
 21 2
3 1
4 1
5 2
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
4 20
12 21
 21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
20 11
9 12
10 13
10 14
10 15
5 16
11 17
11 18
12 19
12 20
12 21
 1 1
4 1
3 1
6 1
0 2
 8 1
8 2
2 5
5 1
7 1
1 4
3 4
5 6
 21 2
3 1
4 1
5 2
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
3 13
10 14
10 15
11 16
11 17
11 18
12 19
4 20
12 21
 1 1
4 1
3 1
6 1
-1 2
 8 1
8 2
2 5
5 1
7 1
1 4
3 8
5 6
 1 1
4 1
3 1
0 1
-1 2
 8 1
8 2
2 5
5 1
7 1
1 4
3 6
5 6
 1 1
4 1
3 2
0 1
-1 2
 1 2
4 1
3 2
0 1
-1 2
 1 2
4 1
3 2
0 1
-1 0
 1 1
4 1
3 2
0 1
-1 0
 22 2
1 4
2 4
3 4
5 8
6 8
7 8
9 12
10 12
11 12
13 16
14 16
15 13
17 20
18 20
19 20
4 21
8 21
12 21
4 22
16 22
20 22
 16 2
1 12
2 12
3 12
4 13
5 13
6 13
7 16
8 13
9 15
10 15
11 15
12 14
13 14
16 14
15 14
 1 1
1 2
 8 1
8 2
2 5
5 1
7 2
2 4
3 5
4 6

No
 Yes
 No
 No
 Yes
 No
 No
 Yes
 No
 No
 Yes
 No
 No
 No
 No
 No
 Yes
 No
 No
 No
 No
 Yes
 No
 No
 Yes
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
