[AGC033F] Adding Edges

给你一棵 $N$ 个点的树 $T$ 和一张 $N$ 个点 $M$ 条边的无向图 $G$。每个图的顶点编号为 $1\sim N$ 。$T$ 中 $N - 1$ 条边中的第 $i$ 条连接顶点 $a_i$ 和顶点 $b_i$，$G$ 中 $M$ 条边中的第 $j$ 条连接顶点 $c_j$ 和顶点 $d_j$。 通过重复以下操作向 $G$ 中添加边: + 选择三个不同的整数 $a, b, c$ 使得在 $G$ 中存在一条连接顶点 $a, b$ 的边和一条连接顶点 $b, c$ 的边，但不存在连接顶点 $a, c$ 的边。 + 如果在 $T$ 中存在一条简单路径以某种顺序包含了所有的三个顶点 $a, b, c$ 那么在 $G$ 中添加连接 $a, c$ 的边。 输出操作到无法操作时 $G$ 中边的数量。可以证明这不取决于如何选择操作。

[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 $ $ M $ $ a_1 $ $ b_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $ $ c_1 $ $ d_1 $ $ : $ $ c_M $ $ d_M $

最終的な $ G $ の辺の数を出力せよ。

5 3
1 2
1 3
3 4
1 5
5 4
2 5
1 5

6

7 5
1 5
1 4
1 7
1 2
2 6
6 3
2 5
1 3
1 6
4 6
4 7

11

13 11
6 13
1 2
5 1
8 4
9 7
12 2
10 11
1 9
13 7
13 11
8 10
3 8
4 13
8 12
4 7
2 3
5 11
1 4
2 11
8 10
3 5
6 9
4 10

27

### 制約 - $ 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 $ の間に辺を追加する。