#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef pair<string,char> pii;
#define endl "\n"
const int N=2e5+5;
int a[N],p[N];
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
void solve()
{
   int n;
   cin>>n;
   for(int i=0;i<=n+20;i++) p[i]=i;
   int val=1;
   for(int i=1;i<=n+1;i++)
   {
       int l,r;
       cin>>l>>r;
       l--;
       int fa=find(l),fb=find(r);
       if(fa==fb) val=0;
       else p[fa]=fb;
       //cout<<l<<" "<<r<<endl;
   }
   cout<<val<<endl;
   
}
signed main()
{ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}