Background

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

The specific rules are as follows:

Lonely death: If a cell has at most $1$ neighbor, then it will die in the next step.

Overcrowding death: If a cell has at least $4$ neighbors, then it will die in the next step.

Stable: If a cell has $2$ or $3$ neighbors, then it stays alive in the next step.

Revival: If a position has no living cell, and it has exactly $3$ neighbors, then a cell will be born at that position.

Under these rules, many interesting patterns appear. For example, the image below shows five consecutive turns of a "Lightweight Spaceship": its period is $4$, and it moves one cell to the right every $2$ turns.

Problem Description

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

In each turn, all nodes whose current remaining degree is $k$, along with the edges connected to them, are deleted instantly and simultaneously.

Formally, in each turn, the following operations are performed in order:

• Count the current remaining degree of each node (the degree of a node is the number of edges currently connected to it).
• Mark all nodes whose degree is exactly $k$.
• Delete all nodes marked in the previous step and all edges incident to them.

We want to know, after infinitely many turns, into how many connected components the tree will be split. If two nodes can be connected directly or indirectly through some edges in the end, then 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 spaces.

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

The input size is large, so using fast input is recommended.

Output Format

One line with one integer, representing the number of connected components remaining after infinitely many turns.

3 1
1 2
2 3

1

4 2
1 2
2 3
3 4

2

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

5

Hint

For Sample 1:

The initial shape of the tree is:

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

After one turn, nodes $1,3$ are deleted.

The tree becomes:

It is easy to see that the shape of the tree will not change anymore, so the final number of connected components is $1$.

For Sample 2:

The initial shape is:

After one turn it becomes:

Then it stays unchanged, so the final number of connected components is $2$.

For Sample 3:

The initial shape:

After one turn it becomes:

After another turn it becomes:

Then it stays unchanged, so the final number of connected components is $5$.

Translated by ChatGPT 5