题目描述

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

考虑通过反复执行以下操作向$G$中添加边：

• 选择三个整数$a$、$b$和$c$，使得$G$中有一条连接顶点$a$和$b$的边，一条连接顶点$b$和$c$的边，但是没有一条连接顶点$a$和$c$的边。如果在$T$中存在一个简单路径，该路径按照某个顺序包含了顶点$a, b$和$c$，则在$G$中添加一条连接顶点$a$和$c$的边。

打印当无法再添加边时$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$是一棵树。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_1$ $d_1$ $:$ $c_M$ $d_M$

输出

打印$G$中边的最终数量。

示例输入1

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

示例输出1

6

通过以下方式添加边，$G$中最多可以有六条边：

• 设$(a,b,c)=(1,5,4)$，添加一条连接顶点$1$和$4$的边。
• 设$(a,b,c)=(1,5,2)$，添加一条连接顶点$1$和$2$的边。
• 设$(a,b,c)=(2,1,4)$，添加一条连接顶点$2$和$4$的边。

示例输入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

示例输出2

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

示例输出3

27