We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. HourRank 21
  3. Tree Isomorphism

Tree Isomorphism

Problem
Submissions
Leaderboard
Discussions
Editorial

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:

image

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:

image

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:

image

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:

image

Author

gorbunovdv

Difficulty

Hard

Max Score

70

Submitted By

377

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download all test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature