暂无测试数据。

Background

抓住夏天的尾巴。

Description

李华终于逃离了无尽的英语作文， 重获自由的他对一棵树产生了兴趣。
首先，他想知道一棵树是否能分成大小相同的几块（即切掉一些边，使得每个连通块的点数相同）。 然后，他觉得这个问题过于简单，于是他想知道一共有多少种方案可以把这棵树分成大小相同的几块。
然后他发现自己不会了，于是向聪明的你求助。

Format

Input

第一行一个数，表示数的大小。
第二行至第 N 行，每行两个数 x,y 表示 x 和 y 之间有一条边。

Output

一行，表示方案数。

Sample 1

Input

6
1 2
2 3
2 4
4 5
5 6

Output

3

Limitation

对于 30%的数据， 1<=n<=100。
对于 60%的数据， 1<=n<=100000。
对于 100%的数据， 1<=n<=1000000。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST