- All Contests
- HourRank 21
- Tree Isomorphism

# Tree Isomorphism

# Tree Isomorphism

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: