AT_toyota2023spring_final_g Git Gud

编程初学者すぬけくん写了如下代码。 ``` 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` 函数被调用次数的最大值。

输入通过标准输入给出，格式如下： > $N$ $A_0$ $B_0$ $A_1$ $B_1$ $\cdots$ $A_{N-2}$ $B_{N-2}$

请输出答案。

## 限制条件 - $2 \leq N \leq 2000$ - $0 \leq A_i, B_i \leq N-1$ - $A_i \neq B_i$ - 输入的图一定是一棵树 ## 样例解释 1 `find` 函数一定会被调用 $2$ 次。 ## 样例解释 2 将第 $0$ 条边的端点顺序交换，构造成如下输入，则 `find` 函数会被调用 $5$ 次。 ``` 3 1 0 0 2 ``` ## 样例解释 3 通过适当调整边的顺序和端点顺序，构造成如下输入，则 `find` 函数会被调用 $13$ 次。 ``` 5 3 0 4 3 1 0 0 2 ``` 由 ChatGPT 4.1 翻译