Speed Cameras

Time limit1sMemory limit128 MB

Summary

Place the most cameras on the intersections of a tree so no simple route passes more than k cameras.

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

Problem

The Lord Mayor of Bytetown wants to put radar speed cameras on the city's intersections. Bytetown has $n$ intersections numbered $1$ to $n$ and $n - 1$ two-way street segments. Each segment joins two intersections, and the network is connected, so a driver can get from any intersection to any other one.

Cameras go on intersections, at most one per intersection, and the mayor wants as many of them as he can get. To keep the drivers' anger down, he also decided that a route which never passes through the same intersection twice may hold at most $k$ cameras. Cameras at the two ends of the route count towards that number.

Find the largest number of cameras that can be installed.

Input

The first line contains the number of intersections $n$ and the largest number of cameras allowed on a single route $k$ ( $1 \le n \le 10^6$ , $1 \le k \le 10^6$ ).

Each of the next $n - 1$ lines describes one street segment. Line $i$ holds two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le n$ ), meaning that a two-way street segment joins intersections $a_i$ and $b_i$ . For $n = 1$ these lines are absent.

Output

Print one line with the largest number of cameras that can be installed in Bytetown.

Examples3

Example 1
Input
```
5 2
1 3
2 3
3 4
4 5
```
Expected output
```
3
```
Example 2
Input
```
4 1
1 2
1 3
1 4
```
Expected output
```
1
```
Example 3
Input
```
1 1000000
```
Expected output
```
1
```