#include<bitsdc++.h>
#include<bits/extc++.h>
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define all(x) (x).begin(),(x).end()
#define Yes(x,y) cout<<((x)?"Yes":"No")<<y
#define YES(x,y) cout<<((x)?"YES":"NO")<<y
#define ls ((u)<<1)
#define rs ((u)<<1|1)
#define mid (((l)+(r))>>1)
#define lowbit(x) ((x)&(-(x)))
#define itn int
#define asn ans
#define reisze resize
#define pdd pair<double,double>
#define pll pair<LL,LL>
#define pii pair<int,int>
#define tll tuple<LL,LL,LL>
#define tii tuple<int,int,int>
#define plll pair<LLL,LLL>
#define ULL unsigned long long
#define LL long long
#define LLL __int128
#define ld long double
#define ui64 uint64_t
#define ui32 uint32_t
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using RBTree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
T fang(const T& a){
    return a*a;
}
template<typename T,typename Q>
bool chmax(T& u1,T& u2,const Q& v){
    if(v>u1) { u2 = u1, u1 = v;return true;}
    if(v>u2){u2=v;return true;}
    return false;
}
template<typename T,typename Q>
bool chmin(T& u1,T& u2,const Q& v){
    if(v<u1) { u2 = u1, u1 = v;return true;}
    if(v<u2){u2=v;return true;}
    return false;
}
template<typename T,typename Q>
bool chmin(T& a,const Q& b){
    return a > b && (a = b, true);
}
template<typename T,typename Q>
bool chmax(T& a,const Q& b){
    return a<b&&(a=b,true);
}
template<typename t1,typename t2>
istream& operator>>(istream& in,pair<t1,t2>& pa){
    in>>pa.first>>pa.second;
    return in;
}
template<typename t1,typename t2>
ostream& operator<<(ostream& out,const pair<t1,t2>& pa){
    out<<pa.first<<' '<<pa.second;
    return out;
}
template<typename T>
istream& operator>>(istream& in,vector<T>& arr){
    for(auto& v:arr)in>>v;
    return in;
}
template<typename T>
ostream& operator<<(ostream& out,const vector<T>& arr){
    for(auto& v:arr)out<<v<<' ';
    return out;
}
const ld eps=1e-9;
const int N=6e5+5;
const int SIZ=1e7;
const LL inf=1e17;
void solve(){
    itn n;
    cin>>n;
    vector<pll> A(n);
    cin>>A;
    for(auto& [a,b]:A)a--;
    vector<int> fa(n+1);
    iota(all(fa),0);
    function<int(int)> find=[&](int x)->int{
        return x==fa[x]?x:fa[x]=find(fa[x]);
    };
    auto merge=[&](itn x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        fa[x]=y;
    };
    map<int,vector<pll>> M;
    for(int i=0;i<n;i++){
        auto& [a,b]=A[i];
        M[a].emplace_back(i,b);
        M[b].emplace_back(i,a);
        merge(a,b);
    }
    set<int> has;
    set<int> al;
    for(int i=1;i<=n;i++){
        if(find(i)!=find(0)&&find(i)!=i){
            cout<<0<<'\n';
            return;
        }
    }
    queue<int> q;
    q.push(0);
    has.insert(0);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto& [a,b]:M[x]){
            if(al.count(a))continue;
            al.insert(a);
            if(has.count(b)){
                cout<<0<<'\n';
                return;
            }
            has.insert(b);
            q.push(b);
        }
    }
    cout<<1<<'\n';
}
signed main(){
    IOS;
    int _;
    cin>>_;
    while(_--)solve();
}

answer.code:1:9: fatal error: bitsdc++.h: No such file or directory
    1 | #include<bitsdc++.h>
      |         ^~~~~~~~~~~~
compilation terminated.