题目描述

给你一个包含 $n$ 个节点的有根树。树上节点编号从 $1$ 到 $n$。根节点编号为 $1$。

现在，你要删除这棵树上的一些节点（删除节点时，连接这些节点的边也会相应地被删除掉），使得剩下的节点和边构成一棵 以节点 $1$ 为根的二叉树。

求：你最少需要删掉几个节点？

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示树上一条边连接的两个端点（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）。

输出格式

输出一个整数，表示你最少需要删除的节点数。

样例

5
1 2
1 3
1 4
1 5

2

6
1 2
1 3
2 4
2 5
3 6

0

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

2

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$；
• 对于 $40\%$ 的数据，$n \le 1000$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$。数据保证这是一棵树。