经典的有限制条件的Burnside计数+矩阵乘法！！！
对于这种限制条件的情况我们可以通过矩阵连乘得到，先初始化矩阵array[i][j]为1.如果颜色a和颜色b不能涂在相邻的珠子，
那么array[a][b] = array[b][a] = 0;
对于具有n/L个循环节的置换(L为每个循环节的长度)。先求出array[][]的n/L次幂，然后将这个矩阵的array[i][i]
(1<=i<=m)全部加起来即为这种置换下涂色不变的方法数。
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
int m,mod=,cnt,prime[];
bool f[];
struct Matrix
{
int a[][];
};
Matrix Mul(Matrix A,Matrix B)
{
Matrix ans;
for(int i=;i<m;i++)
for(int j=;j<m;j++){
ans.a[i][j] = ;
for(int k=;k<m;k++)
{
if (A.a[i][k] && B.a[k][j])
ans.a[i][j] = ans.a[i][j]+A.a[i][k]*B.a[k][j];
}
ans.a[i][j]%=mod;//一定要在这里去摸，否则会超时的
}
return ans;
}
int pows(Matrix A,int b)
{
int i,j,re=;
Matrix ans;
for(i=;i<m;i++)
for(j=;j<m;j++)
ans.a[i][j]=(i==j);
while(b){
if (b&) ans = Mul(A,ans);
b>>=;
A = Mul(A,A);
}
for (i=;i<m;i++)
re = (re+ans.a[i][i])%mod;
return re;
}
int Euler(int n)
{
int ans = n;
for (int i=;i*i<=n;i++){
if (n%i==){
ans=(ans/i)*(i-);
n/=i;
while(n%i==)
n/=i;
}
}
if(n>) ans=(ans/n)*(n-);
return ans%mod;
}
int mypow(int a,int b)
{
int ans = ;
while(b){
if (b&) ans = (ans*a)%mod;
b>>=;
a=(a*a)%mod;
}
return ans;
}
int main(){
int i,n,sum,t,aa,bb,k,j;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&k);
Matrix p;
for(i=;i<m;i++)
for(j=;j<m;j++)
p.a[i][j]=;
for(i=;i<k;i++){
scanf("%d%d",&aa,&bb);
p.a[aa-][bb-]=p.a[bb-][aa-]=;
}
sum = ;
for(i=;i*i<=n;i++){
if(n%i==){
sum = (sum+pows(p,i)*Euler(n/i))%mod;
if(i*i!=n)
sum = (sum+pows(p,n/i)*Euler(i))%mod;
}
}
int x=mypow(n%mod,mod-);
sum = (sum*x)%mod;
printf("%d\n",sum);
}
return ;
}