题目描述

有一个大小为 $n$ 的无根树，树上节点编号从 $1$ 到 $n$。一开始所有的节点都没有染色。

你需要选择给其中的一些节点染色，并且染色后满足如下条件：

对于树上任意一个没有被染色的节点 $u$，和它相邻的节点中至少有一个节点被染色。

求：满足上述条件的情况下，最少要给几个节点染色？

输入格式

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

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

数据保证这是一棵树。

输出格式

输出最少需要染色的节点数。

样例

5
1 2
2 3
2 4
4 5

2

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 10$
• 对于 $60\%$ 的数据，$n \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$