Problem B
City Numbers

After the zombie invasion, everything in the country of Aabelrt was destroyed. To rebuild as quickly as possible, the government of Aabelrt decided to build the minimum possible number of roads between cities to make sure each city can reach every other city. Unfortunately, there is more construction work to be done—now that there are roads between cities, some residents are having trouble telling when they have crossed from one city into another. To remedy this, the government of Aabelrt has decided to give each city a number from $\{ 1, 2, \ldots , k\} $, making sure that pairs of cities with a road between them get different numbers. But this process is not free—when a city is given a number, there is a significant amount of rebranding and construction to be done. The cost of assigning a city the number $x$ is $x$ coins. To keep with the tradition of efficiency, the government would like to assign numbers in the cheapest way possible.

Input

The first line of input contains two space-separated integers $1 \leq n \leq 10^5$ and $1 \leq k \leq 20$, representing the number of cities and the largest number available to assign to cities.

The following $n - 1$ lines of input each contain two space-separated integers $1 \leq u, v \leq n$ ($u \neq v$) indicating there is a bidirectional road between cities $u$ and $v$.

It is guaranteed that each city is reachable from every other city.

Output

If it is possible to assign numbers such that each adjacent pair of cities get different numbers, output how many coins will be used in the cheapest way to do so. If it is impossible to do so, output $-1$.

3 3
1 2
3 1

4

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

12

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

11

2 1
1 2

-1