#P17959. Bipartite Graph Matching Problem

Bipartite Graph Matching Problem

给定一个二分图。左部有 n1n_1 个顶点,编号为 11 到 n1n_1;右部有 n2n_2 个顶点,编号为 11 到 n2n_2。图中有 mm 条边,每条边连接一个左部顶点和一个右部顶点。

对于右部的每个区间 [ℓ,r][\ell,r](1≤ℓ≤r≤n21\le\ell\le r\le n_2),保留全部左部顶点、编号在 [ℓ,r][\ell,r] 内的右部顶点,以及两个端点均被保留的边。 记所得子图的最大匹配大小为 f(ℓ,r)f(\ell,r)。匹配是一组没有公共端点的边。

求

$$\sum_{1\le\ell\le r\le n_2} f(\ell,r)\cdot\ell\cdot r\cdot((\ell\oplus r)+1)$$

对 998244353998244353 取模的结果,其中 ⊕\oplus 表示按位异或。

输入格式

第一行一个整数 tt(1≤t≤20001\le t\le2000),表示测试用例数。

每个测试用例第一行三个整数 n1,n2,mn_1,n_2,m(1≤n1,n2≤50001\le n_1,n_2\le5000,1≤m≤1041\le m\le10^4)。 接下来 mm 行,每行两个整数 u,vu,v(1≤u≤n11\le u\le n_1,1≤v≤n21\le v\le n_2),表示连接左部 uu 与右部 vv 的边。

没有重边。一个输入文件中所有测试用例的 ∑n1≤5000\sum n_1\le5000,∑n2≤5000\sum n_2\le5000。

输出格式

每个测试用例输出一行一个整数,表示所求结果。

样例 1

输入

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

输出

81
529
12
81