tree     

Consider a rooted tree with N nodes numbered from 1 to N. Node 1 is considered to be the root.

Task
Write a program that determines the minimum number of directed edges that have to be removed in order to have a subtree with P nodes. The subtree doesn't have to contain node 1.

Input Data
Input file tree.in contains positive integers N and P on the first line, separated by a space.
The following N -1 lines each contain two numbers I and J, between 1 and N, separated by a space, with the meaning that node J is a direct descendant of node I (there is a directed edge from I to J).

Output Data
Output file tree.out will contain a single line with a positive integer  X, representing the minimum number of removed direct edges.

Constraints
1 <=P <= N <= 150
0 <= X <= N-1


Example

tree.in tree.out Explanation

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

 2

E.g.: directed edges 1 5 and 1 4 are eliminated.
This is not the sole solution (e.g., directed edges 1 5 and 1 2 could be eliminated).

 

Time limit: 0.1 seconds/test

prof. Dana Lica
“Ion.Luca Caragiale” Ploiesti National High School
Contact: danal182001@yahoo.com