AT_toyota2023spring_final_g Git Gud

[problemUrl]: https://atcoder.jp/contests/toyota2023spring-final/tasks/toyota2023spring_final_g プログラミング初心者のすぬけくんが，以下のようなコードを書きました． ``` 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 $ $ \vdots $ $ 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 $ - 入力されるグラフは木である ### Sample Explanation 1 `find` 関数は必ず $ 2 $ 回呼ばれます． ### Sample Explanation 2 辺 $ 0 $ の端点の順番を入れ替え，以下のような入力を作ると，`find` 関数が $ 5 $ 回呼ばれます． ``` 3 1 0 0 2 ``` ### Sample Explanation 3 辺の順番と辺の端点の順番を適切に入れ替え，以下のような入力を作ると，`find` 関数が $ 13 $ 回呼ばれます． ``` 5 3 0 4 3 1 0 0 2 ```