背景

$\color{white}\small 93^{\text{rd}}\text{ Problem by ArC.}$
题目描述
给定 N。以下我们称长为 N 的排列构成的三元组 (A,B,C) 为排列三元组。
对于一个排列三元组 (A,B,C),我们如下定义它的权值:
- 设 G 是一张 N 个点 N 条边的无向图,其第 i 条边为 (Ai,Bi)。(A,B,C) 的权值为 G 的连通块数。
注意排列三元组的权值与 C 无关。
设 S 是满足以下条件的排列三元组的集合。
- ∀1≤i≤N,Ai+Bi>Ci.
- 此外,我们会额外给出 M1+M2 条限制。
- M1 条第一类限制形如:对于任意的 i,若 ⌈2N+Ai⌉=a,则 Ci=c。
- M2 条第二类限制形如:对于任意的 i,若 Bi=b,则 Ci=c。
设 S0 是 S 中权值为偶数的元素个数,S1 是 S 中权值为奇数的元素个数,你需要求 S0−S1。答案对 119×223+1 取模。
输入格式
本题多测。第一行一个整数 T,代表数据组数。接下来 T 组数据。
对于每一组数据,第一行三个整数 N,M1,M2。
接下来 M1 行,每行两个整数 a,c,代表一条第一类限制。
接下来 M2 行,每行两个整数 b,c,代表一条第二类限制。
输出格式
输出 T 行,每行一个整数,分别代表每组数据的答案。
7
3 1 1
3 2
2 2
3 1 1
2 2
2 2
4 1 1
3 2
3 2
2 0 0
6 8 8
4 3
6 3
4 6
5 2
5 4
5 6
6 2
6 5
5 1
1 5
6 1
5 2
5 6
2 6
4 2
4 3
7 8 8
1 7
2 6
3 5
5 3
5 4
7 3
6 2
7 2
5 1
6 1
5 2
4 2
3 7
5 7
4 3
7 4
5 5 10
5 1
5 3
5 4
4 1
4 5
1 2
1 3
2 4
2 5
3 3
3 5
4 1
4 2
5 2
5 4
6
998244347
24
998244351
720
10080
0
提示
样例解释
第一组数据中 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)) 是不合法的,因为 B2=2,C2=2 不满足 b=2,c=2 的限制。
数据范围与约定
本题开启捆绑测试。
::cute-table{tuack}
| 子任务 |
T≤ |
特殊限制 |
分值 |
| 1 |
10 |
N≤6 |
5 |
| 2 |
^ |
M1=0 |
10 |
| 3 |
M2=0 |
| 4 |
104 |
∑N2≤1002 |
20 |
| 5 |
^ |
∑N2≤5002 |
30 |
| 6 |
- |
25 |
对于所有数据:
- 1≤T≤104;
- 2≤N≤1500;
- ∑N2≤15002;
- 0≤M1,M2≤N2;
- ∑(M1+M2)≤6×105;
- 1≤a,b,c≤N。