Minimum Road Destruction to Isolate a P‐Barn Subtree in a Tree

After a devastating earthquake, Farmer John’s ranch has been rebuilt using N barns (numbered from 1 to N) connected by exactly N-1 roads such that there is exactly one unique path between any two barns, i.e. the network forms a tree. In a subsequent earthquake, some roads may be destroyed. If a road is destroyed and this action disconnects the tree into two components such that one component has exactly P barns, then that road is said to be destructive.

John wonders: What is the minimum number of roads that must be destroyed simultaneously so that one of the resulting connected components (subtrees) has exactly P barns? In other words, you are to choose a set of roads (edges) to remove; after removal, if at least one connected component has exactly P nodes, what is the smallest possible number of roads that you might have removed? Note that if the entire tree has exactly P barns, then no road removal is needed.

If it is impossible to obtain a connected subtree with exactly P barns by removing roads, output -1.

Important: Once you choose a connected subset S of barns with exactly P nodes, the cost (or number of roads to cut) needed to isolate S from the rest of the tree equals the number of edges from S to its complement. For instance, if S is a branch hanging off the tree, its boundary may consist of a single edge. However, if S lies in the middle of the tree, you might need to remove two or more roads. Your task is to find the connected subtree S of exactly P nodes for which this boundary (the number of cut roads) is minimized.

inputFormat

The first line contains two integers N and P (1 ≤ P ≤ N), where N is the number of barns and P is the desired size of the subtree.

Each of the following N-1 lines contains two integers u and v (1 ≤ u, v ≤ N) indicating that there is a road connecting barn u and barn v.

outputFormat

Output a single integer, the minimum number of roads that must be destroyed so that one of the resulting connected components has exactly P barns. If it is impossible, output -1.

sample

3 1
1 2
2 3

1