https://codeforces.com/problemset/problem/1702/E
介绍: https://blog.csdn.net/QQ2530063577/article/details/125790411
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=4e5+5,M=1e6+7;
int f[N],a[N],n;
int fd(int x){
if(x!=f[x]) f[x]=fd(f[x]);
return f[x];
}
void merge(int x,int y){
int fx=fd(x),fy=fd(y);
if(fx!=fy) f[fx]=fy;
}
void solve()
{
cin>>n;
//1--n 朋友 n+1--2*n敌对
int ok=0;//扩展二倍
for(int i=1;i<=2*n;i++) f[i]=i,a[i]=0;
for(int i=1;i<=n;i++){
int x,y; cin>>x>>y;
if(ok) continue;
a[x]++,a[y]++;
if(x==y||a[x]==3||a[y]==3) ok=1;
//x与y是朋友关系,那么结束
if(fd(x)==fd(y)) ok=1;
else{
int dx=x+n,dy=y+n;
//x与dy dx与y是敌对关系
merge(x,dy);
merge(dx,y);
}
}
cout<< (ok ? "NO\n":"YES\n");
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t; cin>>t;
while(t--)
{
solve();
}
return 0;
}
大佬tql