# include <bits/stdc++.h>

using namespace std;
using ll = long long;

# define int long long
# define endl '\n'
# define cy cout << "YES" << endl
# define cn cout << "NO" << endl
# define pb push_back
# define fi first
# define se second
# define in insert
# define all(a) a.begin(), a.end()
# define rep(i,a,n) for (int i = a;i <= n;i ++)
# define per(i,a,n) for (int i = n;i >= a;i --)

typedef pair<int,int> PII;
typedef double db;

const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int INF = 1e17;

priority_queue<ll,vector<ll>, greater<ll> > mi;
priority_queue<ll> ma;

int n, m,k;
vector <int> g[N];

void solve(){
    cin >> n;

    vector <int> a(2 * n,0); 
    for(int i = 1;i <= n;i ++ ){
    	int l,r;
    	cin >> l >> r;
    	l --;
    	a.pb(l);
    	a.pb(r);

    	g[l].pb(r);
    	g[r].pb(l);
    }

    vector <bool> st(n + 1,0);
    int cnt = 0;
    auto dfs = [&] (auto dfs,int u,int fa) -> bool{
    	st[u] = true;
    	for(auto l : g[u]){
    		if (!st[l]){
    			cnt ++;
    			if (dfs(dfs,l,u)) return true;
    		}
    		else if (l != fa){
    			return false;
    		}
    	}
    	return true;
    };

    if (!dfs(dfs,1,-1)){
    	cout << 0 << endl;
    	return;
    }
    if (cnt != n - 1){
    	cout << 0 << endl;
    	return;
    }

    for (int i = 0;i < 2 * n;i ++ ){
    	if (!st[a[i]]){
    		cout << 0 << endl;
    		return;
    	}
    }

    cout << 1 << endl;

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int _ = 1;
    cin >> _ ;

    while( _ -- )
    {

        solve();
    }
    return 0;
}