题目描述

给你一棵大小为 $n$ 的树，树上结点编号从 $1$ 到 $n$。

初始时每个结点都没有被染色。

现在你需要选择 最少的 结点，并对这些结点进行染色。且满足染色后：

• 树上任意一条边连接的两个端点中至少存在一个被染色的结点。

求：最少需要对多少个结点进行染色？

输入格式

第一行，一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示树上一条边连接的两个端点的编号。

输出格式

输出一个整数，表示答案。

样例

5
1 2
1 3
1 4
1 5

1

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

3

说明/提示

数据规模与约定

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