Tree Separator

Time limit2sMemory limit512 MB

Summary

Given a tree, delete all vertices on some simple path between two chosen vertices; maximize the number of remaining components of size at least K.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, DFS, Greedy
Solved: No attempts yet

Problem

You are given a tree $T$ with $N$ vertices and an integer $K$ . Choose two distinct vertices $u$ and $v$ of $T$ , and let $P$ be the simple path between them. Remove every vertex on $P$ from $T$ , together with every edge that has at least one endpoint on $P$ .

Choose $u$ and $v$ so that the number of connected components with $K$ or more vertices in the remaining graph is as large as possible.

Input

The input is a single test case in the following format.

N K
u1 v1
.
.
.
uN-1 vN-1

The first line has two integers $N$ and $K$ ( $2 \le N \le 100000$ , $1 \le K \le N$ ). Each of the following $N-1$ lines describes one edge. Line $i+1$ has two integers $u_i$ and $v_i$ ( $1 \le u_i, v_i \le N$ , $u_i \ne v_i$ ), meaning that $\{u_i, v_i\}$ is an edge of $T$ . The given edges form a tree.

Output

Print the maximum number of connected components with $K$ or more vertices in one line.

Examples6

Example 1
Input
```
2 1
1 2
```
Expected output
```
0
```
Example 2
Input
```
7 3
1 2
2 3
3 4
4 5
5 6
6 7
```
Expected output
```
1
```

Example 3

Input

Expected output

Example 4
Input
```
3 1
1 2
2 3
```
Expected output
```
1
```
Example 5
Input
```
3 2
1 2
2 3
```
Expected output
```
0
```
Example 6
Input
```
9 3
1 2
1 3
1 4
4 5
4 6
4 7
7 8
7 9
```
Expected output
```
2
```