Problem Background

In the famous Game of Life, the state of each cell in a two-dimensional grid (dead or alive) is determined by its eight neighboring cells (up, down, left, right, upper left, lower left, upper right, lower right).

The specific rules are as follows:

• Loneliness Death: If a cell has one or no neighbors, it will die in the next state.
• Crowded Death: If a cell has four or more neighbors, it will die in the next state.
• Stability: If a cell has two or three neighbors, it will remain stable and alive in the next state.
• Resurrection: If a position originally has no living cell and has exactly three neighbors, a cell will be resurrected at that position.

Under these rules, many interesting patterns have emerged. For example, the following is a sequence of five rounds for a "Lightweight Spaceship": its period is 4, and it moves one grid to the right every two rounds.

Problem Description

Now, we will play a simplified version of the Game of Life on a tree. Initially, we will be given a tree with $n$ nodes and $n-1$ edges, along with an integer $k$.

In each round, all nodes with degree $k$ and their connected edges will be removed simultaneously.

Formally, each round will proceed as follows:

• Count the degree of each remaining node (the degree of a node is defined as the number of edges connected to it).
• Mark all nodes with exactly degree $k$.
• Remove the marked nodes and their connected edges.

We want to know how many connected components will remain after an infinite number of rounds. If two nodes can be connected directly or indirectly through a series of edges, they are considered to be in the same connected component.

Input Format

The first line contains two integers $n, k$ ($0 \le k < n \le 10^6$), separated by a space.

The next $n-1$ lines each contain two positive integers $u_i, v_i$ ($1 \le u_i, v_i \le n$), separated by a space, indicating that there is an edge between $u_i$ and $v_i$.

The input data is large, so it is recommended to use fast input methods.

Output Format

Output a single integer on one line, representing the number of connected components remaining after an infinite number of rounds.

Sample Input and Output

Sample Input #1

3 1
1 2
2 3

Sample Output #1

1

Sample Input #2

4 2
1 2
2 3
3 4

Sample Output #2

2

Sample Input #3

10 3
1 2
2 3
9 4
3 5
5 6
6 7
3 9
5 8
5 10

Sample Output #3

5

Notes

For Sample 1:

The initial state of the tree is:

The degrees of the three nodes are $1, 2, 1$ respectively.

After one round, nodes $1, 3$ are removed.

The tree becomes:

It is easy to see that the tree's state will not change thereafter, so the final number of connected components is $1$.

For Sample 2:

The initial state is:

After one round, it becomes:

It remains unchanged thereafter, so the final number of connected components is $2$.

For Sample 3:

The initial state is:

After one round, it becomes:

After another round, it becomes:

It remains unchanged thereafter, so the final number of connected components is $5$.

见题面 Input 部分

见题面 Output 部分