P17617 [Math+Girl×1] QuomodocunquizE / A+B>C Problem

 $\color{white}\small 93^{\text{rd}}\text{ Problem by ArC.}$

给定 $N$。以下我们称长为 $N$ 的排列构成的三元组 $(A,B,C)$ 为排列三元组。 对于一个排列三元组 $(A,B,C)$，我们如下定义它的权值： * 设 $G$ 是一张 $N$ 个点 $N$ 条边的无向图，其第 $i$ 条边为 $(A_i,B_i)$。$(A,B,C)$ 的权值为 $G$ 的连通块数。 注意排列三元组的权值与 $C$ 无关。 --- 设 $S$ 是满足以下条件的排列三元组的集合。 * $\forall 1\leq i\leq N,A_i+B_i>C_i$. * 此外，我们会额外给出 $M_1+M_2$ 条限制。 * $M_1$ 条第一类限制形如：对于任意的 $i$，若 $\left\lceil\frac{N+A_i}2\right\rceil=a$，则 $C_i\neq c$。 * $M_2$ 条第二类限制形如：对于任意的 $i$，若 $B_i=b$，则 $C_i\neq c$。 设 $S_0$ 是 $S$ 中权值为偶数的元素个数，$S_1$ 是 $S$ 中权值为奇数的元素个数，你需要求 $S_0-S_1$。答案对 $119\times 2^{23}+1$ 取模。

本题多测。第一行一个整数 $T$，代表数据组数。接下来 $T$ 组数据。 对于每一组数据，第一行三个整数 $N,M_1,M_2$。 接下来 $M_1$ 行，每行两个整数 $a,c$，代表一条第一类限制。 接下来 $M_2$ 行，每行两个整数 $b,c$，代表一条第二类限制。

输出 $T$ 行，每行一个整数，分别代表每组数据的答案。

### 样例解释 第一组数据中 $N=3$。一组符合限制的排列三元组 $(A,B,C)$ 是 $((2,3,1),(2,1,3),(1,3,2))$，其对应的图 $G$ 为 $(2,2),(3,1),(1,3)$，有 $2$ 个连通块，于是这个三元组的权值是 $2$。 可以暴力枚举得到答案为 $6$。 注意 $((1,2,3),(1,2,3),(1,2,3))$ 是不合法的，因为 $B_2=2,C_2=2$ 不满足 $b=2,c=2$ 的限制。 ### 数据范围与约定 **本题开启捆绑测试。** ::cute-table{tuack} | 子任务 | $T\leq$ | 特殊限制 | 分值 | | :-: | :-: | :-: | :-: | | $1$ | $10$ | $N\leq 6$ | $5$ | | $2$ | ^ | $M_1=0$ | $10$ || | $3$ | ^ | $M_2=0$ | $10$ | | $4$ | $10^4$ | $\sum N^2\leq 100^2$ | $20$ | | $5$ | ^ | $\sum N^2\leq 500^2$ | $30$ | | $6$ | ^ | - | $25$ | 对于所有数据： * $1\leq T\leq 10^4$； * $2\leq N\leq 1500$； * $\sum N^2\leq 1500^2$； * $0\leq M_1,M_2\leq N^2$； * $\sum (M_1+M_2)\leq 6\times 10^5$； * $1\leq a,b,c\leq N$。