Gas stations

The KOI country has $N$ villages, numbered $1$ through $N$. There are $N - 1$ roads, and each road directly connects two different villages. The roads are also numbered $1$ through $N - 1$, and road $i$ connects village $x_i$ and village $y_i$. Any two villages in the KOI country are connected by exactly one path.

A path from village $x$ to village $y$ is a sequence of villages $x, z_1, z_2, \cdots, z_t, y$ that satisfies both of the following:

• Each pair of adjacent villages in the sequence is connected by a road.
• No village appears more than once in the sequence.

The length of a path is the number of roads it uses, which is $t + 1$.

You want to build gas stations in some of the villages. By KOI law, the stations must satisfy this condition:

• Every path of length $k$ contains at least one village with a gas station.

Find the minimum number of gas stations that satisfies this condition.

The first line contains $N$ and $k$, separated by a space. Each of the next $N - 1$ lines contains $x_i$ and $y_i$, the two villages connected by road $i$, separated by a space.

Print the minimum number of gas stations on the first line.

• $2 \le N \le 200000$
• $1 \le k \le N - 1$
• $1 \le x_i \le N$, $1 \le y_i \le N$, $x_i \ne y_i$ ($1 \le i \le N - 1$)
• Any two villages are connected by exactly one path.
• At least one path of length $k$ exists.
• All input values are integers.