题目描述

给定一棵 $n$ 个节点的无根树 $T$。

菊花图的定义：一个无向图，其中一个节点（中心节点）与其他所有节点（叶子节点）都相连，且除了这些边之外没有其他边。

你需要求出至少去掉多少条边，才能使得剩下的图（可能是一个森林）中的每个连通块都是一个菊花图。

注意：

1. 一个孤立的节点（1 个节点，0 条边）是一个特殊的菊花图。
2. 一条边连接的两个节点（2 个节点，1 条边）是一个特殊的菊花图。

输入格式

第一行一个正整数 $n$，表示树的节点数。 接下来 $n-1$ 行，第 $i$ 行两个正整数 $u_i, v_i$，表示树上的一条边。节点编号为 $1 \sim n$。

输出格式

输出一个整数，表示最少需要去掉的边数。

5
1 2
1 3
2 4
2 5

1

1 ~ 2 ~ 3
    \
     4 ~ 5

删掉 2~4 即可。

5
1 2
2 3
3 4
4 5

1

删除 2~3 或 3~4

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

1

1 ~ 2 ~ 3 ~ 4 ~ 5 ~ 6
                |
                7

如果只删除一条边，只能删除 3~4

数据规模与约定

对于所有数据，$2 \le n \le 10^5$。

• 子任务 1（30 分）：保证 $u_i=i,v_i=i+1$。
• 子任务 2（30 分）：保证 $n\le 1000$。
• 子任务 3（40 分）：无特殊限制。