Problem Statement

You are given an undirected tree $T$ consisting of $N$ white vertices numbered from $1$ to $N$. The $i$-th edge connects vertices $u_i, v_i$.

For integers $i, j$ between $1$ and $N$ inclusive, let $T(i, j)$ be the tree with $N+2$ vertices obtained by connecting vertex $i$ to a red vertex $N+1$ and connecting vertex $j$ to a green vertex $N+2$. Consider subsets $S$ of $\{(i, j) ~|~ 1 \leq i \leq N, 1 \leq j \leq N\}$ such that, whenever $(i, j) \neq (i', j')$ and $(i, j), (i', j') \in S$, the trees $T(i, j),~ T(i', j')$ are not isomorphic. Output the maximum possible number of elements of such a subset $S$.

Here, "trees $T, T'$ are isomorphic" means that there exists a bijective function $f$ such that, for any integers $i, j$ between $1$ and $N+2$ inclusive, both of the following hold:

• There is an edge between vertices $i, j$ of $T$ if and only if there is an edge between vertices $f(i), f(j)$ of $T'$.
• Vertex $i$ of $T$ and vertex $f(i)$ of $T'$ have the same color.

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq u_i < v_i \leq N$
• The given graph is a tree.
• All input values are integers.

Input

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

Output

Output the answer as an integer on a single line.

Sample

5
1 2
2 3
2 4
4 5

17