問題文

頂点に $1$ から $N$ の番号が付いた $N$ 個の白い頂点からなる無向木 $T$ が与えられます。$i$ 番目の辺は頂点 $u_i, v_i$ を結びます。

$1$ 以上 $N$ 以下の整数 $i, j$ について、頂点 $i$ を赤色の頂点 $N+1$ と繋げ、頂点 $j$ を緑色の頂点 $N+2$ と繋げてできる、頂点数 $N+2$ の木を $T(i, j)$ とします。 $(i, j) \neq (i', j')$ かつ $(i, j), (i', j') \in S$ ならば木 $T(i, j),~ T(i', j')$ が同型でないような $\{(i, j) ~|~ 1 \leq i \leq N, 1 \leq j \leq N\}$ の部分集合 $S$ について、$S$ の要素数として取りうる最大値を出力してください。

ただし「木 $T, T'$ が同型である」とは、任意の $1$ 以上 $N+2$ 以下の整数 $i, j$ について、

• $T$ の頂点 $i, j$ 間に辺があることと、$T'$ の頂点 $f(i), f(j)$ 間に辺があることが同値である。
• $T$ の頂点 $i$ と $T'$ の頂点 $f(i)$ の色は同じである。

制約

• $2 \leq N \leq 10^5$
• $1 \leq u_i < v_i \leq N$
• 与えられるグラフは木である。
• 入力される値は全て整数である。

入力

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

出力

答えを整数で一行で出力してください。

サンプル

5
1 2
2 3
2 4
4 5

17