题目描述

有一个n个点的树，你想要覆盖树上的所有边恰好一次。

你有两个操作：

1.选择两个点u，v，将u到v路径上的每一条边都覆盖一次。

2.选择一个点u,将与u直接相邻的每一条边都覆盖一次。

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

输入格式

第一行一个整数n.

接下来n−1行，每行两个整数u,v。

输出格式

一个整数，表示答案。

样例输入1

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

样例输出1

3

数据范围

测试点1,2,3,满足n≤15

测试点4,5,6满足n≤100

测试点7满足n≤1000

测试点8满足n≤10000

测试点9,10满足n≤100000