输入格式:
第一行一个整数T,表示测试数据的个数 每个测试数据第一行给出 n,m 分别表示点数与边数 接下来 m 行,每行给出两个数 a,b ,表示 a,b 之间有一条无向边
输出格式:
每个测试数据,输出一个整数,表示给出的无向图的生成树的个数
输入输出样例
输入样例#1:
4
4 5
3 4
4 2
2 3
1 2
1 3
2 1
2 1
1 0
3 3
1 2
2 3
3 1
输出样例#1:
8
1
1
3
辗转相除
code:
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define LL long long
#define M(a,b) memset(a,(b),sizeof(a))
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define C(i,a,b) for(register int i=(b);i>=(a);i--)
#define E(i,u) for(register int i=head[u];i;i=nxt[i])
using namespace std;
LL rd() {
LL x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f;c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
}
const int N=15;
int n,m;
LL mat[N][N];
LL det(LL da[N][N],int n) {
LL ans=1;
F(i,1,n) {
F(j,i+1,n) while(da[j][i]) {
LL t=da[i][i]/da[j][i];
F(k,i,n) da[i][k]=(da[i][k]-da[j][k]*t),swap(da[i][k],da[j][k]);
ans=-ans;
}
if(!da[i][i]) return 0;
ans*=da[i][i];
}
return abs(ans);
}
int main() {
int T=rd();
while(T--) {
M(mat,0);
n=rd(),m=rd();
F(i,1,m) {
int a=rd(),b=rd();
mat[a][b]=mat[b][a]=-1;
mat[a][a]++,mat[b][b]++;
}
printf("%lld\n",det(mat,n));
}
return 0;
}