Tree

Time limit2sMemory limit256 MB

Summary

Starting from a single vertex, using only edge deletion and adding pairs of leaves to a vertex of degree at most one, find the minimum operations to build a given tree, or -1.

Level: Hard8 of 10
Topics: Tree, DFS, Greedy, Dynamic programming
Solved: No attempts yet

Problem

The art of growing dwarf trees, bonsai, is more than two thousand years old, and over that time many different styles and techniques have been devised. In this problem you are also asked to grow a tree, but in a somewhat different sense.

A tree is an undirected connected graph without cycles. Initially you have a tree consisting of a single vertex. Two operations are available on your tree: delete one edge and keep either of the two resulting parts, and add two new vertices and connect them to a vertex that previously had at most one adjacent vertex. What is the minimum number of operations needed to obtain a given tree?

Input

The first line contains an integer n (1 ≤ n ≤ 105). Each of the following n - 1 lines contains two numbers ui, vi, the edges of the tree: (1 ≤ ui, vi ≤ n for all i from 1 to n - 1). The given graph is guaranteed to be a tree.

Output

If such a tree cannot be built, output the single number -1. Otherwise, output the minimum number of operations needed to obtain the given tree.

Examples3

Example 1
Input
```
2
1 2
```
Expected output
```
2
```
Example 2
Input
```
3
1 2
2 3
```
Expected output
```
1
```
Example 3
Input
```
5
1 2
1 3
1 4
1 5
```
Expected output
```
-1
```