题解

首先路径不要求是简单的所以可以通过反复走一条边使得路径长度 +2。存在长度为 x 的路径意味着一定存在长度为 x+2 的路径，所以我们只关心一个点的奇最短路和偶最短路。

如果原图是一个二分图，那么每个点要么只存在奇路径要么只存在偶路径，所以只关心最短路。按照 dis
i
​
分层后，每个点连接到上一层即可，答案为 n−1。

接下来只考虑原图不是二分图的情况：令到该点的最短路长度为 x
i
​
，与最短路径奇偶不同的最短路长度为 y
i
​
，我们需要使得新图所有 (x
i
​
,y
i
​
) 和原图相同。

首先有一条边连接的 (x
u
​
,y
u
​
),(x
v
​
,y
v
​
) 一定有 ∣x
u
​
−x
v
​
∣≤1,∣y
u
​
−y
v
​
∣≤1，否则可以用较小者去更新较大者。

所以一个点 (x,y) 只可能和 (x±1,y±1) 连边（当然 x=y−1 时 (x+1,y−1) 为 (x,y) 自己）。

考察一组 (x,y) 的由来，由最短路的构成，一定满足以下两种情况之一：

从 (x−1,y−1) 转移来。
从 (x−1,y+1) 得到 x，从 (x+1,y−1) 得到 y（当 x=y−1 时 (x+1,y−1) 为 (x,y) 自己）。
(x+1,y+1) 可连可不连（对于这个点来说）。

特殊情况是 x=0 即 1 号点不需要向 (x−1,y+1) 连边。

然后接下来的思路很妙：考虑前面二分图按照 dis 分层，而现在难以按照 dis 分层了，分层的目的是为了将原图分成若干个相对较为独立的部分，现在考虑按照 x+y 分层，于是现在只需要考虑每层向上一层连当边和向这一层的左右连的边。

称 (x−1,y−1) 为 (x,y) 的“上面”，(x−1,y+1) 为“左边”，(x+1,y−1) 为“右边”，每个点要么连上面，要么同时连左右（右可能是自环）。

接下来考虑一层一层做。

考虑每层的样子一定形如有若干段，如果不是末尾可以连接自环的段的话一定两个端点都可以向上连。如果末尾可以连接自环那么末尾可能不能向上。（因为这些 (x,y) 是由原图求出来的，所以一定存在一种合法的构造，不会存在一个点上面左右都不能连接）

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int dis[205],n,m,ans,f[205][205][105],g[205][205][105],C[205][205],pw2[205][205],pw[40005],sum[205];
vector<int> G[205];
struct Pair{
	int x,y;
}a[205];
int Power(int x,int y){
	int ret=1;
	while(y) {
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
const bool operator <(const Pair x,const Pair y){
	if(x.x+x.y!=y.x+y.y)return x.x+x.y<y.x+y.y;
	return x.x<y.x;
}
const bool operator ==(const Pair x,const Pair y){
	return !(x<y)&&!(y<x);
}
void upd(int &x,int y){
	x=(x+y)%mod;
}
int F(int U,int x,int y){
	int ret=0;
	for(int i=0,f=1;i<=x;i++,f=mod-f)upd(ret,1ll*f*C[x][i]%mod*pw2[U-i][y]%mod);
	return ret;
}
void Solve(){
	scanf("%d%d",&n,&m),ans=1;
	for(int i=0;i<=2*n;i++)dis[i]=0x3f3f3f3f,G[i].clear();
	for(int i=0;i<=2*n;i++)for(int j=0;j<=2*n;j++)for(int k=0;k<=n;k++)f[i][j][k]=g[i][j][k]=0;
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v+n),G[v+n].push_back(u),G[u+n].push_back(v),G[v].push_back(u+n);
	}
	queue<int> q;
	q.push(1),dis[1]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int y:G[x])if(dis[y]>dis[x]+1)dis[y]=dis[x]+1,q.push(y);
	}
	if(dis[1+n]==0x3f3f3f3f){
		for(int i=0;i<=n;i++)sum[i]=0;
		for(int i=1;i<=n;i++)sum[min(dis[i],dis[i+n])]++;
		for(int i=1;i<=n;i++)ans=1ll*ans*Power(Power(2,sum[i-1])-1,sum[i])%mod;
		return cout<<ans<<'\n',void();
	}
	for(int i=1;i<=n;i++)a[i]={min(dis[i],dis[i+n]),max(dis[i],dis[i+n])};
	sort(a+1,a+n+1);
	map<Pair,int> s;
	for(int i=1;i<=n;i++){
		int j=i-1;
		while(a[j+1]==a[i]&&j<n)j++;
		s[a[i]]=j-i+1;
		int p=a[i].x,q=a[i].y,S=j-i+1,T=s[{p-1,q+1}],O=s[{p-1,q-1}];
		if(!T)g[p][q][(i==1?0:S)]=1;
		else {
			for(int x=0;x<=S;x++)
				for(int y=0;y<=T;y++)
					upd(g[p][q][x],1ll*f[p-1][q+1][y]*F(T,y,S-x)%mod*C[S][x]%mod);
		}
		for(int x=0;x<=S;x++){
			for(int y=0;x+y<=S;y++)
				upd(f[p][q][x],1ll*C[S-y][x]*g[p][q][y]%mod*pw2[O][S-x]%mod);
		}
		if(j==n||a[j+1].x!=p+1||a[j+1].y!=q-1){
			if(p+1!=q)ans=1ll*ans*f[p][q][0]%mod;
			else {
				int tmp=0;
				for(int i=0;i<=S;i++)
					for(int j=0,o=1;j<=i;j++,o=mod-o)
						upd(tmp,1ll*o*C[i][j]%mod*pw[(S-j)*(S-j+1)/2]%mod*f[p][q][i]%mod);
				ans=1ll*ans*tmp%mod;
			}
		}
		i=j;
	}
	cout<<ans<<'\n';
}
int main(){
	for(int i=0;i<=200;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		for(int j=0;j<=200;j++)pw2[i][j]=Power(Power(2,i)-1,j);
	}
	for(int i=0;i<=40000;i++)pw[i]=Power(2,i);
	int t;
	scanf("%d",&t);
	while(t--)Solve();
	return 0;
}