Settlement
In a distant land known as the thirtieth kingdom, there are N villages. Some pairs of these villages are connected by roads. To maintain economic efficiency, there are no redundant roads, meaning there is exactly one path between any two villages. Recent studies have revealed that this kingdom is situated in a seismically active area. As a result, the ruler is concerned about the potential damage an earthquake might inflict on his realm.
He is particularly interested in determining the minimum number of roads that need to be destroyed to isolate a group of exactly P villages from the rest. This group should remain internally connected, meaning any village within the group should still be reachable from any other village in the group via the remaining roads. A group is considered isolated if no remaining road connects any village in the group to a village outside the group. Your task is to develop a program to assist him in this endeavor.
Input
The first line of the input contains two integers: N and P (1 ≤ P ≤ N ≤ 150). Each subsequent line describes a road, with each road specified by two integers representing the villages it connects (ranging from 1 to N). All numbers in the input are separated by spaces and/or line breaks.
Output
Output a single integer — the minimum number of roads that need to be destroyed.