Definim recursiv nivelul unui nod într-un arbore cu rădăcină astfel:

• nivelul rădăcinii este 0
• nivelul fiilor unui nod cu adâncimea H este H+1

Fie S(R,H) numărul de noduri din subarborele cu rădăcina în R și care au adâncimea H. Subarborele nodului R îl include și pe el însuși. Doi arbori cu rădăcinile R și R’ sunt similari numai dacă S(R,H) este egal cu S(R’,H), pentru oricare număr natural H.

Cerința

Se consideră un arbore cu N noduri și rădăcina în nodul 1. Nodurile sunt numerotate de la 1 la N.
Fie TX = subarborele cu rădăcina în nodul X. Se cere să se calculeze numărul de perechi (X,Y) astfel încât subarborii TX și TY sunt similari și X<Y.

Date de intrare

Fișierul de intrare srh.in conține pe prima linie un număr natural N, reprezentând numărul de noduri al arborelui. Următoarele N-1 linii care conțin muchile arborelui: pe linia i+1 se găsesc două numere ai și bi, care înseamnă că ai este părintele lui bi.

Date de ieșire

Fișierul de ieșire srh.out conține o singură linie pe care se află numărul de perechi de noduri (X, Y) astfel încât subarborele cu rădăcina în nodul X să fie similar cu subarborele cu rădăcina în nodul Y și (X < Y).

Restricții și precizări

• 1 ≤ N ≤ 100.000
• Se garantează că arborele este bine format și fiecare nod are un singur părinte (în afară de rădăcina).

Exemple:

srh.in

6
1 5
5 6
6 3
1 2
2 4

srh.out

2

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

srh.out

14

Explicație

Pentru ultimul exemplu, comparăm subarborii din nodul 5 și nodul 6.
Subarborele nodului 5 conține următoarele noduri: nivel 0 – nod 5, nivel 1 – nod 7, nod 8, nivel 2 – nod 4, nod 9, nivel 3 – nod 10.
Subarborele nodului 6 conține următoarele noduri:nivel 0 – nod 6, nivel 1 – nod 2, nod 3, nivel 2 – nod 11, nod 12, nivel 3 – nod 13.
Se observă că subarborii nodului 5 și nodului 6 au același număr de noduri pe fiecare nivel și astfel sunt similari. Prin urmare prima pereche de subarbori similari este (5,6).
Urmatoarele 13 perechi sunt (8,9), (8,10), (8,12), (8,13), (9,10), (9,12), (9,13), (10,12), (10,13), (12,13), (3,4), (3,11), (4,11).