题目描述

$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$ の辺の数を出力せよ。

题目大意

给你一棵 $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$ 中边的数量。可以证明这不取决于如何选择操作。

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