Migrated from Lutece 601 保护领地

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一棵树被一群鸟所占领，树有$N$($1 \leq N \leq 10,000$)个节点，$N-1$条边。这些鸟要保护它们的领地，当一只鸟在一个节点时，可以保护这个节点及与这个节点相邻的节点。求最少需要多少只鸟可以保护所有的节点。

Input

第一行一个整数$N$

接下来$N-1$行，每行$2$个整数$A,B$($1\leq A,B\leq N$),表示$A,B$由边相连。

Output

一个整数，表示最少需要的鸟。

Samples

5
1 3
5 2
4 3
3 5

2

Resources

UESTC Training for Dynamic Programming