//
// Created by Mrlaolu on 2024/7/10.
//

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define x first
#define y second
#define lc root<<1
#define rc root<<1|1
const int N = 1e5+2;
using namespace std;
using PII = pair<int,int>;
using i128 = __int128;
#define debug0
vector<vector<int>>node;
vector<bool>mark;
int cnt = 0;
int huan = 0;
void dfs(int x,int fa){
    if(mark[x]){huan = 0;return;}
    mark[x] = 1;
    cnt++;
    for(int i = 0;i < node[x].size();++i){
        if(fa != node[x][i])dfs(node[x][i],x);
    }
}

void solve(){
    int n;cin >> n;
    cnt = 0;
    huan = 0;
    node = vector<vector<int>>(n + 1);
    mark = vector<bool>(n+1);

    for(int i = 0;i < n;++i){
        int a,b;cin >> a >> b;
        node[a - 1].push_back(b);
        node[b].push_back(a - 1);
    }

    dfs(1,-1);
    if(cnt >= n && huan == 0){cout << 1 << endl;}
    else {cout << 0 << endl;}
}

#define FILE
#define MULTI

signed main() {


#ifndef ONLINE_JUDGE
#ifdef FILE
    freopen("in.txt", "r",stdin);
    freopen("out.txt", "w",stdout);
#endif
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;

#ifdef MULTI
    cin >> T;
#endif

    while (T--) {
        solve();
    }
    return 0;
}