You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个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