题目描述

现在有 $n$ 个路口，它们被 $n-1$ 条街道连通（是一个树形结构）。
你需要在一些路口部署士兵。当你在某个路口部署了一个士兵，它能够侦查到所有连接这个路口的街道。
现在需要你选择一些路口部署士兵，使得所有的街道都能够被侦查到。
请计算至少需要在几个路口部署士兵？

输入格式

输入的第一行包含一个整数 $n( \le 1500)$，用于表示路口的数量。
接下来 $n-1$ 行，每行包含两个整数 $a$ 和 $b(1 \le a,b \le n)$，表示 $a$ 和 $b$ 之间有一条街道连通。

输出格式

输出一个整数，用于表示最少需要部署士兵的路口的数量。

4
1 2
2 3
2 4

1