#P17959. Bipartite Graph Matching Problem
Bipartite Graph Matching Problem
给定一个二分图。左部有 个顶点,编号为 到 ;右部有 个顶点,编号为 到 。图中有 条边,每条边连接一个左部顶点和一个右部顶点。
对于右部的每个区间 (),保留全部左部顶点、编号在 内的右部顶点,以及两个端点均被保留的边。 记所得子图的最大匹配大小为 。匹配是一组没有公共端点的边。
求
$$\sum_{1\le\ell\le r\le n_2} f(\ell,r)\cdot\ell\cdot r\cdot((\ell\oplus r)+1)$$对 取模的结果,其中 表示按位异或。
输入格式
第一行一个整数 (),表示测试用例数。
每个测试用例第一行三个整数 (,)。 接下来 行,每行两个整数 (,),表示连接左部 与右部 的边。
没有重边。一个输入文件中所有测试用例的 ,。
输出格式
每个测试用例输出一行一个整数,表示所求结果。
样例 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