小w有一颗$n$个点的无根树，他想要把这棵树上的节点两两匹配起来，任何一个点只能在一对匹配中。

可是小w发现，无论怎么匹配，树上还是最多只能有$a$对匹配。

小w非常生气，他决定自己动手，往树上加一条边，使得树上有$a + 1$对匹配。

请问小w有多少种加边的方案，可以达成自己的目标呢？

输入格式

第一行一个整数$n$，表示树的点数。

接下来$n - 1$行，每行两个整数$a$和$b$，表示树的一条边$(a,b)$。

输出格式

样例一

input

6 
1 2 
1 3 
1 4 
1 5 
2 6

output

3

数据范围

时间限制 1s, 空间范围 512MB