시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 16 14 13 86.667%

## 문제

Define the depth of a node in a rooted tree by applying the following rules recursively:

• The depth of a root node is 0.
• The depths of child nodes whose parents are with depth d are 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) equals S(T ′ , d) for all non-negative integer d.

You are given a rooted tree T with N nodes. The nodes of T are numbered from 1 to N. Node 1 is the root node of T. Let Ti be the rooted subtree of T whose root is node i. Your task is to write a program which calculates the number of pairs (i, j) such that Ti and Tj 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 ≤ N ≤ 100,000), which is the number of nodes in a tree. The following N − 1 lines give information of branches: the i-th line of them contains ai and bi, which indicates that a node ai is a parent of a node bi. (1 ≤ ai, bi ≤ N, ai ≠ bi) The root node is numbered by 1. It is guaranteed that a given graph is a rooted tree, i.e. there is exactly one parent for each node except the node 1, and the graph is connected.

## 출력

Print the number of the pairs (x, y) of the nodes such that the subtree with the root x and the subtree with the root y are similar and x < y.

## 예제 입력 1

5
1 2
1 3
1 4
1 5


## 예제 출력 1

6


## 예제 입력 2

6
1 2
2 3
3 4
1 5
5 6


## 예제 출력 2

2


## 예제 입력 3

13
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
6 10
7 11
8 12
11 13


## 예제 출력 3

14