营火

Problem Description

在二维平面上，有 $n$ 个火种，其中第 $i$ 个火种的坐标是 $\left(i^3,0\right)$，除了火种之外，还有 $n_1$ 个黑点在 $x$ 轴上方，$n_2$ 个白点在 $x$ 轴下方，其中黑点和黑点，黑点和火种，白点和白点，白点和火种之间有一些边连接了若干点，但保证黑点和白点之间，火种和火种之间没有任何连边。如果只看黑点和火种，那么保证所有黑点和火种，以及它们之间的边构成一个连通图，白点和火种同样。 小 K 会对这些点施加影响，小 K 会随机选择一个黑点 $A$ 和一个白点 $B$ ，把所有 $Y$ 坐标不小于 $Y_A$ 的黑点和 $Y$ 坐标不大于 $Y_B$ 的白点全部删去（当然，连接的边也会消失），现在小 K 想知道有多少种选择黑点和白点的方式，使得所有的火种连通。

Input

第一行一个整数 $T$（$1\le T\le 10^3$），表示数据组数。 对于每组数据： 第一行三个整数 $n,n_1,n_2$（$1\le n,n_1,n_2\le 10^5$），表示火种，黑点，白点的数量。 接下来一行两个正整数 $m_1,m_2$（$1\le m_1,m_2\le 3\cdot 10^5$），分别表示黑点与火种构成的连通图的边数，和白点与火种构成的连通图边数。 接下来 $n_1$ 行，每行两个整数 $x_i,y_i$（$y_i>0$），表示第 $i$ 个黑点的坐标。 接下来 $n_2$ 行，每行两个整数 $x_i,y_i$（$y_i<0$），表示第 $i$ 个白点的坐标。 接下来 $m_1$ 行，每行三个正整数 $op,u,v$，描述一条黑点与火种的边：

• 如果 $op=1$，则表示有一条连接火种 $u$ 和黑点 $v$ 的边（$1\le u\le n,1\le v\le n_1$）；
• 如果 $op=2$，则有一条连接黑点 $u$ 和黑点 $v$ 的边（$1\le u,v\le n_1,u\neq v$）。 接下来 $m_2$ 行，每行三个正整数 $op,u,v$，描述一条白点与火种的边：
• 如果 $op=1$，则表示有一条连接火种 $u$ 和白点 $v$ 的边（$1\le u\le n,1\le v\le n_2$）；
• 如果 $op=2$，则有一条连接白点 $u$ 和白点 $v$ 的边（$1\le u,v\le n_2,u\neq v$）。 保证所有黑白点的坐标 $|x_i|,|y_i|\le 10^9$。 保证所有数据的 $n$ 之和，$n_1$ 之和，$n_2$ 之和都不超过 $3\cdot 10^5$，所有数据的 $m_1$ 之和，$m_2$ 之和都不超过 $10^6$。

Output

对于每组数据，输出一个整数表示选择不同的黑点和白点，使得火种连通的方案数。

Sample Input

2
2 1 2
2 3
1 1
1 -1
1 -2
1 1 1
1 2 1
1 1 1
1 2 1
2 1 2
3 3 4
12 11
-3 9
-8 1
1 5
-3 -8
-5 -10
-5 -1
1 -7
2 2 1
2 3 2
1 1 2
1 2 1
1 3 2
2 2 1
1 1 3
2 2 3
2 2 3
2 2 3
2 3 2
1 2 1
2 2 1
2 3 2
2 4 3
1 1 2
1 2 3
1 3 2
2 4 2
1 3 4
1 2 2
1 3 2
1 2 1

Sample Output

1
4

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（5）