代码如下

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int N=2e6+10;
int n,ct;
int dis[N],cnt[N];
bool vis[N];
vector<PII> v[N];
unordered_map<int,int> mp;
int cl;
class node{
    public:

    int x,y,op;
}d[N];
int a[N];

bool SPFA(int s){
    dis[s]=0;
    int mx=0;
    stack<int> q;
    q.emplace(s);
    vis[s]=1;cnt[s]++;
    while(!q.empty()){
        int now=q.top();q.pop();
        vis[now]=0;
        for(auto[v,w]:v[now])
            if(dis[v]>dis[now]+w){
                dis[v]=dis[now]+w;
                if(!vis[v])
                    vis[v]=1,q.emplace(v),cnt[v]++;
                mx=max(mx,cnt[v]);
                if(cnt[v]>=ct)
                    return 0;
            }
        if((double)clock()/CLOCKS_PER_SEC/(double)cl>0.18) 
        {
            if(mx>ct/8000) return 0;
            else return 1;
        }
    }
    return 1;
}

void _main(){
    cl++;
    memset(dis,0x7f,sizeof(dis));
    memset(cnt,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    mp.clear();

    cin>>n;
    ct=0;
    v[0].clear();
    

    for(int i=1;i<=n;i++)
        cin>>d[i].x>>d[i].y>>d[i].op,
        a[++ct]=d[i].x,a[++ct]=d[i].y;
    
    sort(a+1,a+1+ct);

    ct=unique(a+1,a+1+ct)-a;
    for(int i=1;i<=n;i++)
        d[i].x=lower_bound(a+1,a+ct,d[i].x)-a,
        d[i].y=lower_bound(a+1,a+ct,d[i].y)-a;
    ct--;

    for(int i=1;i<=ct;i++)
        v[i].clear(),v[0].emplace_back(i,0);

    bool flag=1;
    for(int i=1;i<=n;i++){
        if(d[i].op){
            if(d[i].x!=d[i].y)
                v[d[i].x].emplace_back(d[i].y,0),v[d[i].y].emplace_back(d[i].x,0);
        }
        else{
            if(d[i].x==d[i].y)
                flag=0;
            else{
                if(d[i].x>d[i].y)
                    swap(d[i].x,d[i].y);
                v[d[i].x].emplace_back(d[i].y,-1);  
            }
        }
    }
        
    ct++;

    if(flag && SPFA(0))
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int T;
    cin>>T;
    while(T--)
        _main();
    
    return 0;
}