UOJ Logo

NOI.AC

1S 512MB
统计

小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

测试点编号 $n$的规模
1,2$n \leq 20$
3,4$n \leq 500$
5,6$n \leq 3000$
7,8,9,10$n \leq 200000$