[Usaco2008 Jan]电话网络

Farmer John 决定为所有奶牛配备手机，以鼓励她们互相交流。为此，他需要在奶牛居住的 $N$ 块草地中选择一些草地建造无线电通信塔。

所有草地依次编号为 $1$ 到 $N$。其中恰有 $N-1$ 对草地相邻，并且任意两块不同的草地之间都存在一条由相邻草地组成的路径。

无线电通信塔只能建在草地上。每座塔的服务范围包括其所在的草地，以及与该草地相邻的所有草地。

请计算为了使所有草地都被通信信号覆盖，Farmer John 最少需要建造多少座无线电通信塔。

输入格式

第一行包含一个整数 $N$，表示草地数量。

接下来 $N-1$ 行，每行包含两个以空格分隔的整数 $A$ 和 $B$，表示编号为 $A$ 和 $B$ 的两块草地相邻。

输出格式

输出一个整数，表示覆盖所有草地最少需要建造的无线电通信塔数量。

样例输入

5
1 3
5 2
4 3
3 5

样例输出

2

数据范围

• $1\le N\le 10^4$；
• $1\le A\le N$，$1\le B\le N$，且 $A\ne B$；
• 草地之间共有 $N-1$ 对相邻关系，并且任意两块草地之间均相互连通。

来源与许可

本题为 USACO 2008 January 试题「电话网络」，题面与测试数据整理自 BZOJ。

样例 1

输入

5
1 3
5 2
4 3
3 5

输出

2