Optimizing Patrol Route With Additional Roads

In a region there are \(n\) villages numbered \(1,2,\dots,n\). There are \(n-1\) roads connecting these villages such that any village can reach any other via these roads; i.e. the villages form a tree. Every road has length \(1\). To ensure the safety of the region a patrol car must travel on every road each day. The police station is located at village \(1\), and the patrol car always starts from village \(1\) and eventually returns there.

In the original setting the patrol car would have to traverse each road twice, so the total distance traveled is \(2(n-1)\). In order to reduce this distance, the region plans to build exactly \(K\) new roads between the villages. Each new road can connect any two villages (possibly the same village to itself). Note that \(K\) can only be \(1\) or \(2\). In addition, to fully use the funds the patrol car must travel along each newly built road exactly once.

For example, consider a region with \(8\) villages. One possible configuration for the underlying tree is shown below (village \(1\) is marked specially). Without any new road the total distance is \(2\times7=14\). In one plan, a single new road is built so that the patrol route has a total length of \(11\) units; in another plan, two new roads are built so that the total patrol distance becomes \(10\) units; however, in some configurations with two new roads the total patrol distance may even increase (for example, to \(15\) units) if the new roads are not chosen optimally.

Your task is to help determine the best plan. Given the tree structure of the villages and the number \(K\) of new roads to be built, compute the minimal total patrol distance that can be achieved by optimally choosing the new roads.

Note: All roads (both original and new) have unit length. The patrol car must traverse every original road at least once (and they will be traversed twice if no shortcuts are made), and each new road exactly once. All formulas must be in \(\LaTeX\) format; for example, the total distance when no new roads are built is \(2(n-1)\).

inputFormat

The first line contains two integers \(n\) and \(K\) (where \(K=1\) or \(K=2\)). Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) indicating that there is an edge (road) between villages \(u\) and \(v\).

outputFormat

Output a single integer, the minimum total distance of the patrol route.

sample

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

11