Cut 'em all!

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You're given a tree with $\mathrm{nn vertices.}$

Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size.

Input

The first line contains an integer $\mathrm{nn (1\le n\le 1051\le n\le 105)\; denoting\; the\; size\; of\; the\; tree.}$

The next $\mathrm{n-1n-1 lines\; contain\; two\; integers uu, vv (1\le u,v\le n1\le u,v\le n)\; each,\; describing\; the\; vertices\; connected\; by\; the ii-th\; edge.}$

It's guaranteed that the given edges form a tree.

Output

Output a single integer $\mathrm{kk —\; the\; maximum\; number\; of\; edges\; that\; can\; be\; removed\; to\; leave\; all\; connected\; components\; with\; even\; size,\; or -1-1 if\; it\; is\; impossible\; to\; remove\; edges\; in\; order\; to\; satisfy\; this\; property.}$

Examples

input

Copy

4 2 4 4 1 3 1

output

Copy

1

input

Copy

3 1 2 1 3

output

Copy

-1

input

Copy

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

output

Copy

4

input

Copy

2 1 2

output

Copy

0

Note

In the first example you can remove the edge between vertices $\mathrm{11 and 44.\; The\; graph\; after\; that\; will\; have\; two\; connected\; components\; with\; two\; vertices\; in\; each.}$

In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is $-1-1.$

 

#include