Villages
In the thirtieth kingdom, there are n villages. Some pairs of these villages are connected by roads. To optimize resources, there are no redundant roads, meaning there is exactly one path between any two villages.
Recent studies have revealed that the thirtieth kingdom is situated in a seismically active area. Consequently, the king is interested in understanding the potential impact of an earthquake on his kingdom. Specifically, he wants to determine the minimum number of roads that need to be destroyed to form an isolated group of exactly p villages. Within this group, it should still be possible to travel between any two villages using the remaining roads. A group is considered isolated if no remaining road connects a village in this group to a village outside of it.
Your task is to write a program to assist him in this analysis.
Input
The first line contains two integers n and p (1 ≤ p ≤ n ≤ 150). The subsequent lines describe the roads, with each line containing two integers representing the villages connected by that road. All input numbers are separated by spaces and/or line breaks.
Output
Output a single integer – the minimum number of roads that must be destroyed.