Problem4085--割树

4085: 割树

Time Limit: 1.000 Sec  Memory Limit: 256 MB
Submit: 18  Solved: 6
[Submit] [Status] [Web Board] [Creator:]

Description

小明刚刚学习了数据结构中“树”的相关知识，现在有一个N个点N−1条边的树，小明发现将其中一条边去掉之后，会变成两棵子树，他们的结点个数分别为K和N−K（1≤K≤N），我们把这样一次操作记为一次“删边操作”，现在问题来了，小明至少要经过几次操作，使得其中一棵子树的结点个数为P（1≤P≤N）

Input

第一行2个整数N，P

第2..N行，每行两个整数a和b，表示结点a和结点b有连有一条边


Output

一行一个整数，表示最少的操作数

Sample Input

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

Sample Output

2

HINT

样例解释

两次操作边为1-4和1-5

数据范围

对于40%的数据N≤15

对于70%的数据 N≤60

对于100%的数据 N≤150


Source/Category

 

[Submit] [Status]