题目内容

在一个树形的网络拓扑中，有 n 台设备，编号 1 到 n ，其中我们固定 1 为根设备。根设备下可挂多台设备（如设备编号 2、3），以此类推每一台设备下都可能下挂1台或者多台设备，最后没有下挂设备的设备成为边缘设备（如设备 3、5、6、7）。

现在我们希望对网络进行整改，将组网中的部分设备移除，使得所有的边缘设备到根设备的距离相同，请你计算下最少需要移除多少台设备。

如上图：我们只需要移除 3 号和 5 号设备，可以使得剩下的所有边缘设备（6、7）到根设备的距离相同。

注：整个网络是单个连通的树型组网且没有环

输入描述

用例第一行为一个整数 n (3 <=n <=5000) ，代表网络设备数目。

接下来 n 行每行包含两个整数 u, v (1 <= u, v <= n, u ≠ v) ，代表设备 u 与设备 v 相连接（注意仅代表链接关系，不表明父子关系）。

注：我们保证每个设备的编号都小于等于 n ， n 个网络设备，必然有 n-1 条连接。

输出描述

输出最少移除多少台设备，可以使得剩下的所有边缘设备到根设备距离都相同。

样例1

输入

7
1 2
1 3
2 4
2 5
4 6
4 7

输出

2

说明

如题目实例图中：我们移除 3 号和 5 号 2 台设备，可以使得剩下的所有边缘设备（6/7）到根设备的距离相同。

样例2

输入

5
4 1
2 4
5 1
5 3

输出

0

说明

该用例中的树形图为如下，可见不需要移除任何设备就满足边缘设备（2和3）到根设备1的距离都相等。

样例3

输入

7
1 2
2 3
3 4
1 5
1 6
1 7

输出

2

说明

该用例移除设备 4 后，再移除设备 3 即可。