Problem Description

In a region, there are $n$ villages numbered from $1$ to $n$. There are $n-1$ roads connecting these villages, each road connecting exactly two villages. From any village, one can reach any other village through these roads. The length of each road is $1$ unit. To ensure the safety of the region, a patrol car must patrol all roads every day. The police station is located in village $1$, and the patrol car always starts from and returns to the police station. The figure below represents a region with $8$ villages, where villages are denoted by circles (with village $1$ represented by a black circle) and roads are the lines connecting these circles. To traverse all roads, the patrol car needs to travel a distance of $14$ units, passing each road twice.

To reduce the total patrol distance, the region plans to build $K$ new roads between any two villages. Two new roads can meet or end at the same village, as shown in the example below (c). A new road can even be a loop, connecting to the same village at both ends. Due to limited funds, $K$ can only be $1$ or $2$. Additionally, to avoid wasting funds, the patrol car must traverse each new road exactly once. The figure below shows examples of building new roads:

In (a), a new road is built, resulting in a total distance of $11$. In (b), two new roads are built, resulting in a total patrol distance of $10$. In (c), two new roads are built, but since the patrol car must traverse each new road exactly once, the total distance becomes $15$. Write a program that reads the information about the roads between villages and the number of new roads to be built, calculates the best scheme for building new roads to minimize the total patrol distance, and outputs this minimum patrol distance.

Input Format

The first line contains two integers $n, K(1 ≤ K ≤ 2)$. The next $n-1$ lines each contain two integers $a, b$, indicating that there is a road between village $a$ and village $b$ $(1 ≤ a, b ≤ n)$.

Output Format

Output a single integer, which is the minimum patrol distance achievable after building $K$ new roads.

Sample Input and Output

Sample Input #1

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

Sample Output #1

11

Sample Input #2

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

Sample Output #2

10

Sample Input #3

5 2 
1 2 
2 3 
3 4 
4 5 

Sample Output #3

6

Notes

• $10\%$ of the test cases have $1 ≤ n ≤ 1000, K=1$;
• $30\%$ of the test cases have $K=1$;
• $80\%$ of the test cases have at most $25$ adjacent villages for each village;
• $90\%$ of the test cases have at most $150$ adjacent villages for each village;
• $100\%$ of the test cases have $3 ≤ n ≤ 10^5, 1 ≤ K ≤ 2$.

见题面 Input 部分

见题面 Output 部分