問題文

プログラミング初心者のすぬけくんが，以下のようなコードを書きました．

N = read_integer()

parent = array(N, -1) //長さ N の配列 parent を作り，すべての要素を -1 で初期化

find(v):
    if parent[v] == -1:
        return v
    else:
        return find(parent[v])

union(a,b):
    parent[find(b)] = find(a)

for i = 0 to N-2:
    A_i = read_integer()
    B_i = read_integer()
    union(A_i,B_i)

これは，N 頂点の木の情報を受けとり，Union-Find で辺を結ぶだけのプログラムです．

プログラミングマスターのりんごさんは，このプログラムの欠陥に気が付きました． すなわち，Union-Find に一切の高速化が施されていないのです．

今，りんごさんは N 頂点からなる木 T を持っています． T の頂点には 0 から N-1 までの番号が，辺には 0 から N-2 までの番号がついています． 辺 i は頂点 A_i と頂点 B_i を結ぶ辺です．

りんごさんは，すぬけくんのプログラムに T を入力として与えようとしています． ただしその前に，T の辺の番号と，辺の端点の順番を自由に入れ替えることができます．

りんごさんは，すぬけくんのプログラムが非効率的であることを示すために，find 関数が呼ばれる回数を最大化したいです． find 関数が呼ばれる回数の最大値を求めてください．

制約

• 2 \leq N \leq 2000
• 0 \leq A_i,B_i \leq N-1
• A_i \neq B_i
• 入力されるグラフは木である

入力例 1

2
0 1

出力例 1

2

find 関数は必ず 2 回呼ばれます．

入力例 2

3
0 1
0 2

出力例 2

5

辺 0 の端点の順番を入れ替え，以下のような入力を作ると，find 関数が 5 回呼ばれます．

3
1 0
0 2

入力例 3

5
0 1
0 2
0 3
3 4

出力例 3

13

辺の順番と辺の端点の順番を適切に入れ替え，以下のような入力を作ると，find 関数が 13 回呼ばれます．

5
3 0
4 3
1 0
0 2

入力例 4

20
6 16
10 6
16 8
1 5
9 4
5 3
13 16
19 10
12 2
14 10
12 18
0 2
15 16
12 7
11 14
1 10
6 4
17 8
12 1

出力例 4

148