纠缠点对

Problem Description

给定两棵由 $n$ 个顶点构成的无根树 $T_1$ 和 $T_2$。 定义点对 $(u,v)$ 和 $(x,y)$ 相互纠缠，当且仅当，在 $T_1$ 上和 $T_2$ 上，从 $u$ 到 $v$ 和从 $x$ 到 $y$ 的最短路径都有至少一个交点。 现给定 $m$ 对点对 $(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)$，计算：有多少对点对相互纠缠。即，存在多少对 $i < j$，使得点对 $(x_i, y_i)$ 和点对 $(x_j,y_j)$ 相互纠缠。

Input

第一行一个整数 $t$ $(1 \leq t \leq 10)$，表示测试数据的组数。 对于每组数据： 第一行两个整数 $n$ $(1 \leq n \leq 10^5)$ 和 $m$ $(1 \leq m \leq 10^5)$。 接下来 $n-1$ 行，每行两个整数 $u$，$v$，表示 $T_1$ 上的一条边。 接下来 $n-1$ 行，每行两个整数 $u$，$v$，表示 $T_2$ 上的一条边。 接下来 $m$ 行，每行两个整数 $x$，$y$，表示给定的一个点对。

Output

对每组数据输出一行一个整数，表示所求答案。

Sample Input

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

Sample Output

2
1

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）