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

using i64 = long long;
using u64 = unsigned long long;

constexpr int N = 1e6 + 10;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr i64 infll = 0x3f3f3f3f3f3f3f3f;

#define debug(x) std::cerr << #x << " = " << x << std::endl
int vis[N],d[N];    
int n;
vector<int>e[N];
int toposort()
{
    queue<int> q;
    for(int i = 1;i <= n; i++)
        vis[i] = 0;
    for(int i = 1; i <= n; i++)
        if(d[i] <= 1)
            q.push(i),vis[i] = true;
    int cnt=0;
    while(!q.empty())
    {
        cnt++;
        int u = q.front();  q.pop();
        for(auto v : e[u])
            if(--d[v] <= 1 && !vis[v])
                q.push(v),vis[v] = true;
    }   
    return cnt==n;
}

void solve(){

    cin>>n;
    for(int i=1;i<=n;i++) e[i].clear(),d[i]=0;
    for(int i=1;i<=n;i++)
    {

        int l,r;
        cin>>l>>r;
        l--;
        e[l].push_back(r);
        e[r].push_back(l);
        d[l]++;
        d[r]++;
    }
    cout<<toposort()<<'\n';
    
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
    return 0;
}