题目描述

给定一棵有 $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$ 中的边数。

样例 1

输入

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

输出

6

样例 2

输入

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

样例 3

输入

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 \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 翻译