Little Alexey was playing with trees while studying two new awesome concepts: subtree and isomorphism.
A tree is a connected, undirected graph with no cycles. We can denote a tree by a pair , where is the set of vertices and is the set of edges. Here's an example of a tree:
Let be a subset of , and let be the set of edges between the vertices in . If the graph is is a tree, then it is called a subtree of . Here's an example of a subtree of the tree above:
Two trees are said to be isomorphic if they contain the same number of vertices and those vertices are connected in the same way. For example, the following two trees are isomorphic:
More formally, two trees and are said to be isomorphic if there exists a one-to-one correspondence such that if and only if .
Now he wonders, how many non-isomorphic trees can he construct using such a procedure? He asks you for help!
Input Format
The first line contains a single integer denoting the number of vertices of the tree. The number of edges is . The vertices are numbered to .
The next lines describe the edges of the tree. The such line contains two space-separated integers and denoting the vertices that the edge connects.
Constraints
- It's guaranteed that the given graph forms a tree.
Output Format
Print a single line containing a single integer denoting the number different non-isomorphic trees that Little Alexey can obtain.
Sample Input 0
3
1 2
1 3
Sample Output 0
3
Explanation 0
Here are the three trees that Little Alexey can obtain from the tree in this sample:
- a single vertex,
- Two vertices with edge between them, and
- the whole tree.
The following image illustrates it:
