★★★高分★★★竞赛题——信息学家cici(Expert in Informatics cici)

cici在信息学中知识渊博，研究精深。可总有疏忽大意的时候，这不，在NOI2003中的《草莓》一题不慎失手:'(。比赛之后cici认真总结教训，呵呵，还根据那道题目改编了一道题目:D。【题目背景】(摘自NOI2003试题)
尽管不少人都吃过鲜美的草莓，却很少有人真正观察过野草莓的生长。它们从自己的枝上伸出一根根长长的触须，遇到合适的地方就会扎根发芽，长出一株新的草莓。所以，当你在森林中遇到一株草莓的时候，通常就意味着你会在它的周围找到一片草莓田。但这些草莓并非能够无忧无虑地生长，树林中穿梭的鸟儿和偶尔路过的鹿群都喜欢吃这种美味的浆果。不过，草莓最大的威胁却是来自那些贪吃的棕熊。他们不但可以吃掉整整一片草莓，而且还会粗鲁地把一片草莓田搞得乱七八糟。于是每当一块草莓田越长越大之后，森林中的精灵们就会把这片草莓田分成k块种到k个空地中去，以免被粗鲁的棕熊搞乱。她们希望每块空地上恰好放上一块用触须连接在一起的草莓田。不过，如果一块空地里的草莓太少，它们就会感到孤单，所以精灵们希望无论哪块空地含有草莓的总重量都不要太小。可是天真的精灵并不知道怎样来做这件事情，你可以帮助她们吗？
 
(注意你不需要解决上面所述题目背景)【本题任务】(需要你来解决)
    还是NOI2003那片美味可爱的草莓地，有n个草莓，1-n编号。每个草莓之间至多有一根藤相连。与其不同的是这里的草莓构成一个无环图(cici比赛的时候没有发现大多数数据都是树:-(()。任务也不是要将草莓尽量平均的分割，而是剪断最少的藤，使得恰好可以分割出一个含有p个草莓节点的子树。输入
第一行:两个整数N P
第二行-第n行:每行两个整数Xi Yi表示Xi Yi草莓间有藤相连。输出
仅一行最少的剪断藤的数目。数据规模
20%的数据0<N<=11
所有数据0<N<=150 0<P<=N样例infor.in
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11infor.out
2样例说明剪掉1-4 1-5的边，可以得到(1, 2, 3, 6, 7, 8)为节点的子树。