Settlement#5485
In a distant land known as the thirtieth kingdom, there are 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 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.
The first line of the input contains two integers: and (1 \leq P \leq N \leq 150). Each subsequent line describes a road, with each road specified by two integers representing the villages it connects (ranging from to ). All numbers in the input are separated by spaces and/or line breaks.
Output a single integer—the minimum number of roads that need to be destroyed.
Example 1