Description

After a terrible earthquake, people rebuilt Farmer John's ranch with $N$ barns (numbered $1 \sim N$). Since there was no time to build extra roads, there is a unique path between any two barns. Therefore, the ranch road network forms a tree.

John wants to know how severe the damage would be in another earthquake. Some roads, once destroyed, would separate a subtree containing $P$ barns from the remaining barns. John wants to know the minimum number of such roads.

Input Format

The first line contains two integers, $N$ and $P$.

From the second line to the $N$-th line (i.e., $N - 1$ lines), each line contains two integers $I$ and $J$, indicating that node $I$ is the parent of node $J$. The road network can be built as a tree rooted at node $1$.

Output Format

Output a single line containing the minimum number of roads whose destruction would separate a subtree with exactly $P$ nodes.

11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11

2

Hint

Sample explanation: If roads $1-4$ and $1-5$ are destroyed, the subtree containing nodes ($1, 2, 3, 6, 7, 8$) will be separated.

Constraints: $1 \le N \le 150$, $1 \le P \le N$. It is guaranteed that the input forms a tree.

Translated by ChatGPT 5