I love 李慕婉

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9+7;

using ll = long long;

#define f first
#define s second

struct mi {
int v;
explicit operator int() const { return v; }
mi() { v = 0; }
mi(ll _v):v(int(_v%MOD)) { v += (v<0)MOD; }
};
mi& operator+=(mi& a, mi b) {
if ((a.v += b.v) >= MOD) a.v -= MOD;
return a; }
mi& operator-=(mi& a, mi b) {
if ((a.v -= b.v) < 0) a.v += MOD;
return a; }
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator(mi a, mi b) { return mi((ll)a.vb.v); }
mi& operator=(mi& a, mi b) { return a = ab; }
mi pow(mi a, ll p) { assert(p >= 0); // asserts are important!
return p==0?1:pow(aa,p/2)*(p&1?a:1); }

using vi = vector<int>;
using vmi = vector<mi>;

int N,M;
vector<vi> adj;

vector<array<int,2>> gen_dist() { // BFS
vector<array<int,2>> dist(N,{MOD,MOD});
queue<pair<int,int>> q;
auto ad = [&](int a, int b) {
if (dist[a][b%2] != MOD) return;
dist[a][b%2] = b; q.push({a,b});
};
ad(0,0);
while (!q.empty()) {
pair<int,int> p = q.front(); q.pop();
for (int t: adj[p.f]) ad(t,p.s+1);
}
return dist;
}

mi comb[105][105]; // comb[x][y] = (x choose y)
vmi p2; // stores powers of 2

void solve() {
cin >> N >> M;
adj = vector<vi>(N);
for (int i = 0; i < M; ++i) {
int a,b; cin >> a >> b; --a,--b;
adj[a].push_back(b), adj[b].push_back(a);
}
vector<array<int,2>> dists = gen_dist();
for (array<int,2>& t: dists)
if (t[0] > t[1]) swap(t[0],t[1]);
if (dists[0][1] == MOD) { // bipartite
vi num_at_dist(N);
for (int i = 0; i < N; ++i)
++num_at_dist[min(dists[i][0],dists[i][1])];
mi ans = 1;
for (int i = 1; i < N; ++i)
ans = pow(p2[num_at_dist[i-1]]-1,num_at_dist[i]);
cout << (int)ans << "\n";
return;
}
vector<vi> S(4N,vi(4N));
for (array<int,2> t: dists) ++S[t[0]][t[1]];
mi ans = 1;
for (int sum = 1; sum < 4N; sum += 2) {
vmi dp(S[0][sum]+1); dp.back() = 1;
for (int a = 1; a <= sum/2; ++a) { // solve in increasing order of a
int b = sum-a, num = S[a][b];
vmi dp_int(num+1);
{ // deal with s_{a-1,b+1} to s_{a,b}
int prev_num = S[a-1][b+1];
for (int x = 0; x <= num; ++x) { // x in s_{a,b} with no edges at all, num-x that receive edges
for (int y = 0; y <= prev_num; ++y) { // y nodes in s_{a-1,b+1} that need an edge
mi tot_mul = 0;
for (int k = 0; k <= y; ++k) { // suppose that k out of y didn't actually get an edge
mi mul = comb[y][k]pow(p2[prev_num-k]-1,num-x);
if (k&1) tot_mul -= mul;
else tot_mul += mul;
}
dp_int[x] += tot_muldp[y];
}
dp_int[x] = comb[num][x];
}
}
{ // deal with s_{a-1,b-1} to s_{a,b}
dp = vmi(num+1);
int lower_num = S[a-1][b-1];
for (int x = 0; x <= num; ++x) { // x will not be part of such an edge
for (int y = 0; x+y <= num; ++y) { // y urgently need an edge, num-y don't
mi mul = comb[num-y][x]pow(p2[lower_num]-1,num-x);
dp[x] += muldp_int[y];
}
}
}
}
// finally, deal with clique edges
mi ans_for_layer = 0;
int num = S[sum/2][sum/2+1];
for (int y = 0; y <= num; ++y) { // how many ways to complete if y need an edge
mi tot_mul = 0;
for (int k = 0; k <= y; ++k) {
mi mul = comb[y][k]p2[(num-k)(num-k+1)/2];
if (k&1) tot_mul -= mul;
else tot_mul += mul;
}
ans_for_layer += tot_muldp[y];
}
ans *= ans_for_layer;
}
cout << (int)ans << "\n";
}

int main() {
comb[0][0] = 1;
for (int i = 1; i < 105; ++i) {
comb[i][0] = 1;
for (int j = 1; j <= i; ++j)
comb[i][j] = comb[i-1][j]+comb[i-1][j-1];
}
p2 = {1};
for (int _ = 0; _ < 10000; ++_)
p2.push_back(2*p2.back());
int TC; cin >> TC;
while (TC--) solve();
}