考虑以下关于树上边着色的游戏。

给定一棵树。初始时，所有边的颜色均为白色。定义一条“有效路径”为一条满足以下条件的简单路径：路径上的所有边均为白色，且路径的两个端点均为树的叶子节点。在游戏的每一步中，你可以选择一条有效路径，并将该路径上的所有边涂成黑色。直到无法找到任何有效路径为止，游戏才能结束。

该游戏的目标是使用最少的步数完成游戏。请计算给定树完成游戏所需的最少步数。

输入格式

输入的第一行包含一个整数 $N$，表示给定树的节点数。 接下来的 $N - 1$ 行，每行包含两个整数 $x$ 和 $y$，表示树中第 $x$ 个节点和第 $y$ 个节点之间有一条边相连。节点编号从 $1$ 到 $N$。

• $2 \le N \le 10^5$
• $1 \le x, y \le N$
• 给定的图是一棵树。

输出格式

输出一个整数：在给定树上完成游戏所需的最少步数。

样例

样例输入 1

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

样例输出 1

1

样例输入 2

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

样例输出 2

3