题目描述
如下是一份并查集的代码实现：
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$ ，保证输入是一棵树。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $n\le 9$ | $15$ |
| $2$ | $n\le 11$ | $15$ |
| $3$ | $n\le 16$ | $15$ |
| $4$ | 输入是一条链 | $15$ |
| $5$ | 存在一个 $k$ ，使得每个点的度数是 $1$ 或 $k$ | $10$ |
| $6$ | $n\le 100$ | $15$ |
| $7$ | $ $ | $15$ |