#P2842. 魔法手镯

    ID: 1948 传统题 1000ms 512MiB 尝试: 18 已通过: 9 难度: 7 上传者: 标签>CF2200提高+/省选-Burnside 引理矩阵快速幂欧拉函数约数成对枚举试除法分解质因数模逆元

魔法手镯

题目描述

用 MM 种颜色的珠子串成一个长度为 NN 的环,每种颜色可以重复使用。给定 KK 对不能相邻的颜色。相邻限制是双向的,可以禁止同种颜色相邻。最后一颗和第一颗也相邻。特别地,当 N=1N=1 时,唯一的珠子和自身相邻。

只要两个环能通过旋转重合,就视为同一个方案。翻转后的方案只有在它也能通过旋转重合时才视为相同。求合法方案数对 99739973 取模后的值。

输入格式

第一行一个正整数 TT,表示测试数据组数。每组数据的第一行给出三个整数 N,M,KN,M,K,接下来 KK 行各给出一对不能相邻的颜色编号 i,ji,j(1≤i,j≤M1\le i,j\le M)。

输出格式

对每组数据输出一行一个整数,表示合法方案数模 99739973 的值。

数据范围

1≤T≤201\le T\le20,1≤N≤1091\le N\le10^9,1≤M≤101\le M\le10,0≤K≤M(M+1)/20\le K\le M(M+1)/2,且 N mod 9973≠0N\bmod9973\ne0。

样例

4
3 2 0
3 2 1
1 2
3 2 2
1 1
1 2
3 2 3
1 1
1 2
2 2
4
2
1
0

题目来源