题目背景

边境有一片小镇，小镇之间道路连成一棵树，指挥官需要最少驻军覆盖全部道路。

题目描述

给定一棵 $n$ 个节点的无根树，每个节点可以驻扎士兵。 若一个节点驻扎士兵，则与它直接相连的所有道路都会被监视。 要求树上每一条道路至少被一个端点的士兵监视，求最少需要驻扎多少士兵。

输入格式

第一行一个整数 $n$，表示小镇（节点）数量。 接下来 $n-1$ 行，每行两个整数 $u,v$，代表 $u$ 和 $v$ 之间有一条双向道路。 节点编号：$1 \le u,v \le n$。

输出格式

输出一行一个整数，即覆盖所有道路所需最少士兵数量。

输入输出样例 #1

输入

4
1 2
2 3
2 4

输出

1

样例解释

只需要在节点2放置1个士兵，四条道路全部被监视。

输入输出样例 #2

输入

5
1 2
1 3
3 4
3 5

输出

2

样例解释

最优方案：节点1、3各放一个士兵，共2人。

数据范围

$1 \le n \le 1500$，保证输入是合法树，无重边无自环。