There are N villages in the thirtieth state. Some pairs of villages are connected by roads. In order to save money, “superfluous” there are no roads, i.e. There is only one way to get from any village to any village by road.
The latest research has shown that the thirtieth state is located in a seismically dangerous zone. Therefore, the head of state wanted to know what kind of damage an earthquake could bring to his country. Namely, he wants to know what is the minimum number of roads that must be destroyed in order to form a group of exactly P villages, isolated from the rest, such that from any village from this group to any other village from this group it will still be possible to get by undestroyed roads (a group is isolated from the rest if no undamaged road connects a village in this group with a village not in this group).
You should write a program to help him with this.
Input data format
The first line of the input file contains two numbers: N and P (1 ≤ P ≤ N ≤ 150). All other lines contain road descriptions, one per line: the road description consists of two village numbers (from 1 to N) that this road connects. All numbers in the input file are separated by spaces and/or newlines.
Output data format
In the output file print a single number — desired number of roads.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3 2
1 2
3 2 |
1 |
|
| 2 |
11 6
1 2
1 3
14
15
26
27
28
49
4 10
4 11 |
2 |
A group of villages (1, 2, 3, 6, 7, 8) will be isolated from the rest if roads 1–4 and 1–5 are destroyed. |