AT_agc033_f.[AGC033F] Adding Edges

给定一棵有 $N$ 个顶点的树 $T$ 和一个有 $N$ 个顶点、$M$ 条边的无向图 $G$。每个顶点编号为 $1$ 到 $N$。树 $T$ 的第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。图 $G$ 的第 $j$ 条边连接顶点 $c_j$ 和顶点 $d_j$。

你可以对 $G$ 重复进行如下操作来添加边：

• 选择三个整数 $a$、$b$、$c$，使得 $G$ 中存在边 $ab$ 和 $bc$，但不存在边 $ac$。如果 $a$、$b$、$c$ 三个顶点在树 $T$ 的某条简单路径上按任意顺序都出现过，则在 $G$ 中添加一条 $ac$ 边。

当无法再添加边时，求 $G$ 中的边数。无论操作顺序如何，最终的边数都是相同的。

输入通过标准输入给出，格式如下：

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\cdots$ $a_{N-1}$ $b_{N-1}$ $c_1$ $d_1$ $c_2$ $d_2$ $\cdots$ $c_M$ $d_M$

输出最终 $G$ 中的边数。

限制条件

• $2 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• $1 \leq c_j, d_j \leq N$
• $c_j \neq d_j$
• $G$ 不含重边
• $T$ 是一棵树

样例解释 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$ 之间添加一条边。

由 ChatGPT 4.1 翻译