#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
vi p,s;
vii a;
vector<pi> q,t;
int parent(int x){
if(p[x]==x)return x;
q.PB({x,p[x]});
return p[x]=parent(p[x]);
}
void merge(int x,int y){
x=parent(x);
y=parent(y);
if(x==y)return;
if(s[x]<s[y])swap(x,y);
t.PB({x,s[x]});
s[x]+=s[y];
q.PB({y,p[y]});
p[y]=x;
}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int m = S.size();
p.resize(n);s.resize(n,1);
REP(i,0,n)p[i]=i;
a.resize(n);
REP(i,0,X.size()){
a[X[i]].PB(Y[i]);
a[Y[i]].PB(X[i]);
}
vii b(m,vi(5));
REP(i,0,m)b[i]={L[i],R[i],S[i],E[i],i};
sort(all(b));
int k=log2(n)+1,pos=0,loc=k,prev=0;
vi ans(m,0);
while(pos<m){
p.clear();
p.resize(n);s.resize(n,1);
REP(i,0,n)p[i]=i;
vector<pi> arr;
REP(i,0,prev)for(auto u:a[i]){
if(u<prev)merge(i,u);
else arr.PB({u,i});
}
sort(all(arr));
REP(i,loc,n)for(auto u:a[i])if(u>=loc)merge(i,u);
q.clear();t.clear();
vii c;
while(pos<m&&b[pos][0]<loc)c.PB(b[pos++]);
int sz=c.size(),ps=0;
REP(i,0,sz)swap(c[i][0],c[i][1]);
sort(all(c));
REP(i,0,sz){
int x=c[i][1],y=c[i][0];
while(ps<arr.size()&&arr[ps].F<=y){
merge(arr[ps].F,arr[ps].S);
ps++;
}
q.clear();t.clear();
if(y>=loc){
REP(j,x,loc)for(auto u:a[j])merge(j,u);
}
else{
REP(j,x,y+1)for(auto u:a[j])merge(j,u);
REP(j,y+1,loc)for(auto u:a[j])if(u>=x)merge(j,u);
}
REP(j,prev,x)for(auto u:a[j])if(u<=y)merge(j,u);
if(parent(c[i][2])==parent(c[i][3]))ans[c[i][4]]=1;
reverse(all(q));reverse(all(t));
for(auto [u,v]:q)p[u]=v;
for(auto [u,v]:t)s[u]=v;
}
loc=min(loc+k,n);
}
return ans;
}
