重建道路

重建道路

问题描述

5·12大地震后,给四川带来了毁灭性的打击。四川人们在全国各族人民的热心帮助下自力更生,重建家园。人们用N个牲口棚(1<=N<=150,编号1..N)重建了农夫老杨的牧场,由于人们没有时间建设多余的道路,所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此牧场运输系统可以被构建成一棵树。如今四川地区余震不断,老杨想要知道另一次地震会造成多严重的破坏,有些道路一旦被破坏,就会使一棵含有P(1<=P<=n)个牲口棚的子树和剩余的牲口相分离,老杨向知道这些道路的最小数目。

输入格式

第1行2个数,N和P。
第2..n行,每行2个整数i和j,表示结点i是结点j的父结点。

输出格式

单独一行,包含一旦被破坏将分离出恰含p个结点的子树的道路的最小数目。

输入样例

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

输出样例

2

样例说明

如果道路1-4和1-5被破坏,含有结点(1,2,3,6,7,8)的子树将被分离出来。