서브트리의 유사성

루트가 있는 트리에서 노드의 깊이는 다음 규칙을 재귀적으로 적용해서 정한다.

• 루트 노드의 깊이는 0이다.
• 깊이가 $d$인 노드의 자식 노드는 깊이가 $d+1$이다.

$S(T, d)$를 트리 $T$에서 깊이가 $d$인 노드의 개수라고 하자. 루트가 있는 두 트리 $T$와 $T'$는 모든 음이 아닌 정수 $d$에 대해 $S(T, d) = S(T', d)$일 때, 그리고 그때에만 유사하다고 한다.

노드가 $N$개인 루트 있는 트리 $T$가 주어진다. 노드에는 1부터 $N$까지 번호가 붙어 있고, 노드 1이 $T$의 루트이다. $T_i$를 노드 $i$를 루트로 하는 $T$의 서브트리라고 하자. $T_i$와 $T_j$가 유사하고 $i < j$인 쌍 $(i, j)$의 개수를 구하는 프로그램을 작성하시오.

입력은 테스트 케이스 하나로 이루어진다.

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

첫째 줄에 트리의 노드 개수 $N$ ($1 \le N \le 100{,}000$)이 주어진다. 다음 $N-1$개의 줄에는 간선 정보가 주어진다. 그중 $i$번째 줄에는 $a_i$와 $b_i$가 주어지며, 이는 노드 $a_i$가 노드 $b_i$의 부모라는 뜻이다. ($1 \le a_i, b_i \le N$, $a_i \ne b_i$) 루트 노드의 번호는 1이다. 주어지는 그래프는 루트가 있는 트리임이 보장된다. 즉, 노드 1을 제외한 모든 노드에는 부모가 정확히 하나씩 있고, 그래프는 연결되어 있다.

노드 $x$를 루트로 하는 서브트리와 노드 $y$를 루트로 하는 서브트리가 유사하고 $x < y$인 노드 쌍 $(x, y)$의 개수를 출력한다.