Similarity of Subtrees

The depth of a node in a rooted tree is defined by applying the following rules recursively.

• The depth of the root node is 0.
• A child of a node with depth $d$ has depth $d+1$.

Let $S(T, d)$ be the number of nodes of $T$ with depth $d$. Two rooted trees $T$ and $T'$ are similar if and only if $S(T, d) = S(T', d)$ for every non-negative integer $d$.

You are given a rooted tree $T$ with $N$ nodes. The nodes of $T$ are numbered from 1 to $N$, and node 1 is the root of $T$. Let $T_i$ be the rooted subtree of $T$ whose root is node $i$. Write a program that counts the pairs $(i, j)$ such that $T_i$ and $T_j$ are similar and $i < j$.

The input consists of a single test case.

N
a1 b1
...
aN-1 bN-1

The first line contains an integer $N$ ($1 \le N \le 100{,}000$), the number of nodes in the tree. The following $N-1$ lines describe the branches: the $i$-th of them contains $a_i$ and $b_i$, meaning that node $a_i$ is the parent of node $b_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$). The root node is numbered 1. The given graph is guaranteed to be a rooted tree: every node except node 1 has exactly one parent, and the graph is connected.

Print the number of pairs $(x, y)$ of nodes such that the subtree rooted at $x$ and the subtree rooted at $y$ are similar and $x < y$.