手指都敲废了

#include <bits/stdc++.h>
using namespace std;
#ifdef Fread
char buf[1 << 21], *iS, *iT;
#define gc() (iS == iT ? (iT = (iS = buf) + fread(buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define getchar gc
#endif
template <typename T>
void r1(T &x) {
	x = 0;
	char c(getchar());
	int f(1);
	for( ; c < '0' || c > '9'; c = getchar()){
        if(c == '-'){
            f = -1;
        }
    }
	for( ; '0' <= c && c <= '9'; c = getchar()){
        x = (x * 10) + (c ^ 48);
    }
	x *= f;
}
template <typename T,typename... Args> inline void r1(T& t, Args&... args){
    r1(t);  r1(args...);
}
#define Getmod
#ifdef Getmod
const int mod  = 1e9 + 7;
template <int mod>
struct typemod{
    int z;
    typemod(int a = 0) : z(a) {}
    inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);}
    inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);}
    inline int mul(int a,int b) const {return 1ll * a * b % mod;}
    typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));}
    typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));}
    typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));}
    typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;}
    typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;}
    typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;}
    int operator == (const typemod<mod> &x) const {return x.z == z;}
    int operator != (const typemod<mod> &x) const {return x.z != z;}
};
typedef typemod<mod> Tm;
#endif
const int maxn = 2e2 + 5;
const int maxm = maxn << 1;
Tm c[maxn][maxn], pw2[maxn][maxn];
Tm ksm(Tm x, int mi){
    Tm res(1);
    while(mi){
        if(mi & 1) res = res * x;
        mi >>= 1;
        x = x * x;
    }
    return res;
}
Tm pw[maxn * maxn];
void init() {
    c[0][0] = 1;
    int i, j;
    for(i = 0; i < maxn; ++i){
        c[i][0] = 1;
        for(j = 1; j < maxn; ++j){
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
        for(j = 0; j < maxn; ++j){
            pw2[i][j] = ksm(ksm(2, i) - 1, j);
        }
    }
    for(i = 0; i < maxn * maxn; ++i){
        pw[i] = ksm(2, i);
    }
}
vector<int> vc[maxn];
int n, m;
void add(int u,int v){
    vc[u].push_back(v);
}
Tm f[maxn][maxn][maxn], g[maxn][maxn][maxn];
int dis[maxn];
int sum[maxn];
struct pii{
    int first, second;
    pii(int a = 0,int b = 0) : first(a), second(b){}
    int operator < (const pii &b) const {
        if(first + second != b.first + b.second){
            return first + second < b.first + b.second;
        }else{
            return first < b.first;
        }
    }
    int operator == (const pii &b) const {
        return first == b.first && second == b.second;
    }
};
pii a[maxn];
#define mp pii
Tm F(int a,int x,int y) {
    Tm res(0);
    Tm vis[2] = {1, mod - 1};
    for(int i = 0; i <= x; ++i){
        res += vis[i & 1] * pw2[a - i][y] * c[x][i]; 
    }
    return res;
}
void Solve() {
    int i, j;
    r1(n, m);
    Tm ans(1);
    for(i = 0; i <= n * 2; ++i){
        vc[i].clear(), dis[i] = 0x3f3f3f3f;
    }
    for(i = 0; i <= n * 2; ++i){
        for(j = 0; j <= 2 * n; ++j){
            for(int k = 0; k <= n * 2; ++k){
                f[i][j][k] = g[i][j][k] = 0;
            }
        }
    }
    for(i = 1; i <= m; ++i) {
        int u, v;
        r1(u, v);
        add(u, v + n), add(v + n, u);
        add(u + n, v), add(v, u + n);
    }
    static queue<int> q;
    while(!q.empty()) q.pop();
    q.push(1);
    dis[1] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(i = 0; i < vc[x].size(); ++i){
            int to = vc[x][i];
            if(dis[to] > dis[x] + 1){
                dis[to] = dis[x] + 1;
                q.push(to);
            }
        }
    }
    if(dis[1 + n] == 0x3f3f3f3f){
        for(i = 0; i <= n; ++i){
            sum[i] = 0;
        }
        for(i = 1; i <= n; ++i){
            sum[min(dis[i], dis[i + n])]++;
        }
        for(i = 1; i <= n; ++i){
            ans = ans * pw2[sum[i - 1]][sum[i]];
        }
        printf("%d\n", ans.z);
        return ;
    }
    for(i = 1; i <= n; ++i){
        a[i] = mp(min(dis[i], dis[i + n]), max(dis[i], dis[i + n]));
    }
    sort(a + 1, a + n + 1);
    map<pii, int> ct;
    ans = 1;
    for(i = 1; i <= n; i = j + 1){
        j = i - 1;
        while(j < n && a[j + 1] == a[i]){
            ++ j;
        }
        ct[a[i]] = j - i + 1;
        int nx = a[i].first, ny = a[i].second;
        int A = ct[mp(nx - 1, ny - 1)], B = ct[mp(nx - 1, ny + 1)], D = j - i + 1;
        Tm vis[2] = {1, mod - 1};
        if(!B){
            g[nx][ny][(i == 1 ? 0 : D)] = 1;
    	}else{
            for(int x = 0; x <= D; ++x){
                for(int y = 0; y <= B; ++y){
                    g[nx][ny][x] += f[nx - 1][ny + 1][y] * c[D][x] * F(B, y, D - x);
            	}
            }
        }
        for(int x = 0; x <= D; ++x){
            for(int y = 0; x + y <= D; ++y){
                f[nx][ny][x] += c[D - y][x] * pw2[A][D - x] * g[nx][ny][y];
            }
        }
        if(j == n || a[j + 1].first != nx + 1 || a[j + 1].second != ny - 1) {
            if(nx + 1 != ny){
                ans *= f[nx][ny][0];
        	}else{
                Tm tmp(0);
                for(int x = 0; x <= D; ++ x){
                    for(int y = 0; y <= x; ++ y){
                        tmp += vis[y & 1] * c[x][y] * f[nx][ny][x] * pw[(D - y) * (D - y + 1) / 2];     
                    }
                }
                ans *= tmp;
            }
        }
    }
    printf("%d\n", ans.z);
}
signed main(){
    init();
    int T;
    r1(T);
    while(T--){
        Solve();
    }
	return 0;
}