AT_agc033_f [AGC033F] Adding Edges

[problemUrl]: https://atcoder.jp/contests/agc033/tasks/agc033_f $ N $ 頂点からなる木 $ T $ と $ N $ 頂点 $ M $ 辺からなる無向グラフ $ G $ が与えられます。 それぞれの各頂点には $ 1 $ から $ N $ の番号が割り振られています。 $ T $ の $ N-1 $ 本の辺のうち、$ i $ 本目の辺は頂点 $ a_i $ と頂点 $ b_i $ を繋いでいます。 $ G $ の $ M $ 本の辺のうち、$ j $ 本目の辺は頂点 $ c_j $ と頂点 $ d_j $ を繋いでいます。 $ G $ に対して以下の操作を繰り返し行うことで、$ G $ に辺を追加することを考えます。 - $ 3 $ つの整数 $ a $,$ b $,$ c $ であって、$ G $ の頂点 $ ab $ 間と $ bc $ 間に辺があり、$ ac $ 間に辺がないようなものを選ぶ。 $ T $ のある単純パス上に頂点 $ a $,$ b $,$ c $ が何らかの順序ですべて含まれるとき、$ G $ の頂点 $ ac $ 間に辺を追加する。 これ以上辺を追加することができなくなったとき、$ G $ の辺の数はいくつになるか求めてください。 この数はどのように操作を行っても変わらないことが示せます。

N/A

N/A

### 制約 - $ 2\ ≦\ N\ ≦\ 2000 $ - $ 1\ ≦\ M\ ≦\ 2000 $ - $ 1\ ≦\ a_i,\ b_i\ ≦\ N $ - $ a_i\ \neq\ b_i $ - $ 1\ ≦\ c_j,\ d_j\ ≦\ N $ - $ c_j\ \neq\ d_j $ - $ G $ は多重辺を含まない - $ T $ は木である ### Sample Explanation 1 以下の順で辺を追加することで $ 6 $ 本まで辺を増やすことができます。 - $ (a,b,c)=(1,5,4) $ とし、頂点 $ 1 $ と頂点 $ 4 $ の間に辺を追加する。 - $ (a,b,c)=(1,5,2) $ とし、頂点 $ 1 $ と頂点 $ 2 $ の間に辺を追加する。 - $ (a,b,c)=(2,1,4) $ とし、頂点 $ 2 $ と頂点 $ 4 $ の間に辺を追加する。