题目描述

如下是一份并查集的代码实现：

N = read_integer()
parent = array(N, -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)

这份代码的输入是一棵标号从 $0$ 到 $n-1$ 的树，每次读入一条边 $(A_i,B_i)$ ，并用并查集把 $A_i,B_i$ 所在的连通块合并。但是这份代码有一个问题：它的 find(v) 没有实现路径压缩，因此它的复杂度是错的。

作为省选的出题人，你当然不能容许复杂度错误的并查集通过你的题目。

给定一棵树，你可以把边的顺序任意打乱，并对每条边都可以交换 $A_i,B_i$​ （也可以不交换），求出以上代码调用 find(v) 的最大次数。

输入格式

第一行一个正整数 $n$ ，表示点数。

接下来 $n-1$ 行，每行两个非负整数 $A_i,B_i$ ，表示一条边。

输出格式

输出一行一个正整数，表示答案。

样例

样例输入 1

3
0 1
0 2

样例输出 1

5

样例解释

重排之后的输入是

3
1 0
0 2

样例输入 2

10
0 1
0 2
1 3
0 4
4 5
0 6
5 7
7 8
7 9

样例输出 2

41

样例 3

见下发文件。

数据范围

对于全部数据，保证 $1\le n\le 2000,0\le A_i,B_i\le n-1$ ，保证输入是一棵树。