#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int a[N] = {0};

int find(int n){
	if(a[n] == n) return n;
	else a[n] = find(a[n]);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t, n, l, r, jg;
	cin >> t;
	while(t--){
		cin >> n;
		jg = 1;
		for(int i = 0; i <= n; i++)	a[i] = i;
		for(int i = 0; i <= n; i++){
			cin >> l >> r;
			if(find(l - 1) == find(r)) jg = 0;
			else a[find(l - 1)] = find(r); 
		}
		printf("%d\n",jg);
	}
 	return 0;
}