Problem Background

A group of people, after having lunch, are preparing to visit the examination venue. IY, SY, QM, MY, and UU had already agreed to meet up that afternoon. Everyone unanimously agreed to pass the responsibility of arranging the itinerary to IY.

(IY: ??? Why me?)

(QM: Here's some candy.)

(IY: Sure, no problem, leave it to me.)

Problem Description

The city where IY lives has $n$ intersections connected by $n-1$ bidirectional roads, forming a tree structure. The distance between two distinct intersections is defined as the number of roads on their simple path, with the distance of an intersection to itself being $0$.

We define the importance of a road. If a road is unusable, it prevents $t$ pairs of intersections from reaching each other, then $t$ is the importance of that road. For example:

The road between (3,4) has an importance of $9$ because the pairs (1,4), (2,4), (3,4), (1,5), (2,5), (3,5), (1,6), (2,6), (3,6) all need to pass through this edge to reach each other.

IY received bad news that construction is happening at an intersection (but IY doesn't know where). The construction affects areas within a distance of $k$ from the construction site, and all intersections within this distance are closed. This prevents the group from passing through affected intersections and the roads directly connected to them.

IY has to consider the worst-case scenario since he doesn't know the location of the construction. He wants to know the maximum sum of the importance of the roads affected by the construction.

Input Format

The first line contains two numbers $n, k$.

The next $n-1$ lines each contain two numbers $u, v$ describing a road, indicating that intersection $u$ is directly connected to intersection $v$.

Output Format

A single number representing the maximum sum of the importance of the roads affected by the construction.

Sample Input and Output

Sample Input #1

6 0
1 3
3 2
5 4
3 4
4 6

Sample Output #1

19

Sample Input #2

5 1
1 2
2 3
3 4
4 5

Sample Output #2

20

Notes

• Sample Explanation

Sample #1: This is the example from the problem statement. If the construction is at intersection $3$ or $4$, the sum of the importance of the affected roads is $19$. No larger value can be found.

Sample #2: This example has the special property of a chain.

• Data Range

For the first $20\%$ of test cases, $n \le 100, 0 \le k \le 7$.

For the first $40\%$ of test cases: The data is guaranteed to be random.

Specifically: The third test case only has $k == 0$.

For $100\%$ of test cases: $n \le 30000, 0 \le k \le 200$.

Specifically: The tenth test case degenerates into a chain.

见题面 Input 部分

见题面 Output 部分