题目描述

农夫约翰决定给他的每头奶牛配备一部手机，以促进它们之间的社交互动。然而，这需要他在他的 $N$（$1 \leq N \leq 10,000$）个牧场（编号为 $1..N$）上建立手机信号塔，以确保所有牧场都能通信。

恰好有 $N-1$ 对牧场是相邻的，并且对于任意两个牧场 $A$ 和 $B$（$1 \leq A \leq N$；$1 \leq B \leq N$；$A \neq B$），存在一个相邻牧场的序列，使得 $A$ 是序列的第一个牧场，$B$ 是最后一个牧场。农夫约翰只能在牧场中建立信号塔，每个信号塔的覆盖范围包括它所在的牧场以及与之相邻的所有牧场。

请帮助他确定最少需要建立多少个信号塔，才能确保每个牧场都能接收到手机信号。

输入格式

• 第 1 行：一个整数 $N$，表示牧场的数量。
• 第 2 行到第 $N$ 行：每行包含两个用空格分隔的整数 $A$ 和 $B$，表示一对相邻的牧场。

输出格式

• 第 1 行：一个整数，表示最少需要建立的信号塔数量。

样例输入 1

5
1 3
5 2
4 3
3 5

样例输出 1

2

来源

USACO 2008 January Gold

补充说明

• 题目描述的牧场结构是一棵树（$N$ 个节点，$N-1$ 条边，且连通）。
• 每个信号塔可以覆盖 自身所在的牧场 和 所有直接相邻的牧场。
• 目标是选择最少的牧场建立信号塔，使得所有牧场都被覆盖。
• 这是一个典型的 最小支配集（Minimum Dominating Set） 问题，属于图论中的经典问题。