题目描述

有一个 $n$ 个点的树，你想要覆盖树上的所有边恰好一次。你有两种操作：

1. 选择两个点 $u, v$，将 $u$ 到 $v$ 路径上的每一条边都覆盖一次。
2. 选择一个点 $u$，将与 $u$ 直接相邻的每一条边都覆盖一次。

问最少的操作次数可以完成目标。注意每条边不能重复覆盖，也就是如果执行操作的时候要保证对应的边都是空的。

输入格式

第一行一个整数 $n$ $(2 \leq n \leq 10^5)$。

接下来 $n-1$ 行，每行两个整数 $u, v$ $(1 \leq u,v \leq n)$。

输出格式

一个整数，表示答案。

样例

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

3