刘老师得到一棵包含 $N$ 个顶点的树。他可以删除其中若干条边。删除以后，原树会分成若干个互不相交的连通块。

刘老师希望每一个连通块都恰好包含偶数个顶点，并且在满足这个条件的前提下，让删除的边数尽可能多。

请计算最多能够删除多少条边。如果无论怎样删除，都不能让所有连通块的顶点数为偶数，就输出 $-1$。

输入格式

第一行输入一个整数 $N$，表示树的顶点数量。

接下来 $N-1$ 行，每行输入两个整数 $u_i$ 和 $v_i$，表示顶点 $u_i$ 与顶点 $v_i$ 之间有一条边。

输出格式

如果能够满足要求，输出最多可以删除的边数；否则输出 $-1$。

6
1 3
3 5
3 6
1 2
4 3

1

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

3

2
1 2

0

数据范围与约定

• $2\le N\le10^5$
• 输入图是一棵树