题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIII Olimpiada Informatyczna — III etap Parada

每年春天，拜托城都会举办盛大的拜托尼亚春季队列表演，迎接新季的到来。今年，国王 Bajtazar XVI 亲临现场，为队列表演增添光彩。拜托城的路网由 $n$ 个路口通过 $n-1$ 条双向街道连接而成，确保从任一路口可到达其他任意路口。

队列表演的具体路线尚未确定，但已知它将从某路口出发，沿若干街道行进，最终在另一路口结束。为避免单调，队列表演路线每条街道至多经过一次。

为确保队列表演参与者的安全，需在队列表演经过的路口（包括起点和终点）处，对未被队列表演使用的街道入口设置路障。请计算最多可能需要多少路障。

输入格式

第一行包含一个整数 $n$ $(n \geq 2)$，表示拜托城的路口数量。路口编号为 $1$ 至 $n$。

接下来的 $n-1$ 行描述拜托城的路网，每行包含两个整数 $a, b$ $(1 \leq a, b \leq n, a \neq b)$，表示路口 $a$ 和 $b$ 间存在一条双向街道。

输出格式

输出一行，包含一个整数，表示保障安全最多可能需要的路障数量。

8
1 2
2 3
4 2
5 2
6 5
5 7
7 8

5

提示

样例 1 解释

若从路口 $2$ 出发，至路口 $7$ 结束，需设置 $5$ 处路障（路口 $2$ 的 $3$ 个入口各一处，路口 $5$ 和 $7$ 各一处）。

附加样例

1. $n=20$，路网为路径。
2. $n=20$，路网为星形。
3. $n=1000$，随机样例，第 $i$ 条街道（$i=1, \ldots, n-1$）连接路口 $i+1$ 与某编号更小的路口。

详细子任务附加限制及分值如下表所示。