#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <fstream>
#define maxM 610
using namespace std;

int T, N, M, i, j, A[maxM], B[maxM], x, bit, fn;
int main ()
{
	ifstream fin ("sortari.in");
	freopen ("sortari.out", "w", stdout);	
	fin >> T;	
	srand (time (NULL));
	while (T--)
	{
		fin >> N >> M;
		for (j = 1; j <= M; j++)
		{
			fin >> A[j] >> B[j];
			A[j]--;
			B[j]--;
		}
		int x1, x2;
		for (fn = 0, i = 1; i <= 40000; i++)
		{	
			x1 = 1 << N;
			x1--;
			x = (rand () % x1) + 1;	
			for (j = 1; j <= M; j++)
			{	
				x1 = (1 << A[j]);
				if (x1 & x) {
				       x2 = (1 << B[j]);
				       if ((x2 & x) == 0) {
						x -= (1 << A[j]);
						x += (1 << B[j]);
					}
				}
			}
			
			bit = 0;
			while (((1 << bit) & x) == 0) 
				bit++;

			while ((1 << bit) & x) {
				x -= (1 << bit);
				bit++;
			}
			if (bit != N)
			{
				printf ("0\n");
				fn = 1;
				break;
			}
		}
		if (fn == 0) printf ("1\n");
	}
	return 0;
}