#include <vector>
#include <string> 
#include <set> 
#include <map> 
#include <unordered_set>
#include <unordered_map>
#include <queue> 
#include <bitset> 
#include <stack>
#include <list>

#include <numeric> 
#include <algorithm> 
#include <random>
#include <chrono>

#include <cstdio>
#include <fstream>
#include <iostream> 
#include <sstream> 
#include <iomanip>
#include <climits>

#include <cctype>
#include <cmath> 
#include <ctime>
#include <cassert>

using namespace std;

#define ULL unsigned long long
#define LL long long
#define PII pair <int, int>
#define VB vector <bool>
#define VI vector <int>
#define VLL vector <LL>
#define VD vector <double>
#define VS vector <string>
#define VPII vector <pair <int, int> >
#define VVI vector < VI >
#define VVB vector < VB >
#define SI set < int >
#define USI unordered_set <int>
#define MII map <int, int>
#define UMII unordered_map <int, int>
#define MS multiset
#define US unordered_set
#define UM unordered_map
#define UMS unordered_multiset
#define UMM unordered_multimap

#define FORN(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define SZ size()
#define BG begin() 
#define EN end() 
#define CL clear()
#define X first
#define Y second
#define RS resize
#define PB push_back
#define MP make_pair
#define ALL(x) x.begin(), x.end()
#define INS insert
#define ER erase
#define CNT count

#define MOD int(1e9 + 7)

int n, m, nComp;
VVI g, gt;
VI comp;
stack <int> order;
SI c;
VB was;

void add(int p, int q)
{
	int nonp = p <= n ? p + n + 1 : p - n - 1;
	int nonq = q <= n ? q + n + 1 : q - n - 1;
	g[nonp].PB(q);
	gt[q].PB(nonp);
	g[nonq].PB(p);
	gt[p].PB(nonq);
}

void df(int node, VVI &gr)
{
	comp[node] = nComp;
	for (int next : gr[node])
		if (comp[next] == 0) df(next, gr);
	order.push(node);
}

void kosaraju()
{
	comp.CL, comp.RS(2 * n + 2);
	nComp = 1;
	FOR(i, 0, 2 * n + 1) df(i, g);
	fill(ALL(comp), 0);
	while (!order.empty())
	{
		int node = order.top();
		order.pop();
		if (comp[node] == 0) 
		{
			df(node, gt);
			++nComp;
		}
	}
}

bool sat()
{
	FOR(i, 0, n)
		if (comp[i] == comp[i + n + 1]) return false;
	return true;
}

void dfc(int node)
{
	c.INS(comp[node]);
	if (node <= n) c.INS(comp[node + n + 1]);
	else c.INS(comp[node - n - 1]);
	was[node] = true;
	for (int next : g[node]) 
		if (!was[next]) dfc(next);
}

int main()
{
	int test;
	cin >> test;
	FOR(t, 1, test)
	{
		cin >> n >> m;
		g.CL, g.RS(2 * n + 2);
		gt.CL, gt.RS(2 * n + 2);
		FOR(i, 1, m)
		{
			int x, y;
			cin >> x >> y;
			add(x - 1, y);
			add(x - 1 + n + 1, y + n + 1);
		}
		kosaraju();
		if (!sat()) cout << 0 << endl;
		else
		{
			c.CL;
			was.CL, was.RS(2 * n + 2);
			int sol = 1;
			FOR(i, 1, n)
			{
				int cp = comp[i];
				if (cp == comp[0] || cp == comp[n + 1]) continue;
				if (c.CNT(cp) == 0) sol = sol * 2 % MOD;
				dfc(i);
			}
			cout << sol << endl;
		}
	}

	return 0;
}