#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200000], V[200000];
pair<int,int> x[200000], y[200000];
int numx[200000], num_rev[200000], numy[200000], color[200000], tree[200001];
int find_(int a)
{
return color[a]=a==color[a] ? a:find_(color[a]);
}
void union_(int a, int b)
{
a=find_(a); b=find_(b);
if(V[a].size()<V[b].size()) swap(a,b);
color[b]=a;
for(auto v: V[b]) V[a].push_back(v);
V[b].clear();
}
void update(int n, int v)
{
for(++n;n<=200000;n+=n&-n) tree[n]+=v;
}
int get_cnt(int n)
{
int ret=0;
for(++n;n;n-=n&-n) ret+=tree[n];
return ret;
}
int get_cnt(pair<int,int> S)
{
return get_cnt(S.second)-get_cnt(S.first-1);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
int M=X.size(), Q=S.size(), j=N-1, k;
vector<tuple<int,int,int>> temp(Q);
vector<int> ret(Q);
for(int i=0;i<M;i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i=0;i<Q;i++) temp[i]=make_tuple(L[i],S[i],i);
sort(temp.rbegin(),temp.rend());
for(int i=0;i<N;i++) {
V[i].resize(1);
color[V[i][0]=i]=i;
}
for(int i=0;i<Q;i++) {
int l, s, idx;
tie(l,s,idx)=temp[i];
for(;j>=l;j--) for(auto n: adj[j]) if(n>j && find_(j)!=find_(n)) union_(j,n);
s=find_(s);
x[idx]={V[s].front(),V[s].back()};
L[i]=R[i]=i;
}
for(;j>=0;j--) for(auto n: adj[j]) if(n>j && find_(j)!=find_(n)) union_(j,n);
j=find_(0);
for(int i=0;i<N;i++) numx[num_rev[i]=V[j][i]]=i;
for(int i=0;i<Q;i++) temp[i]=make_tuple(R[i],E[i],i);
sort(temp.begin(),temp.end());
for(int i=0;i<N;i++) {
V[i].resize(1);
color[V[i][0]=i]=i;
}
for(int i=j=0;i<Q;i++) {
int r, e, idx;
tie(r,e,idx)=temp[i];
for(;j<=r;j++) for(auto n: adj[j]) if(n<j && find_(j)!=find_(n)) union_(j,n);
e=find_(e);
y[idx]={V[e].front(),V[e].back()};
}
for(;j<N;j++) for(auto n: adj[j]) if(n<j && find_(j)!=find_(n)) union_(j,n);
j=find_(0);
for(int i=0;i<N;i++) numy[V[j][i]]=i;
for(int i=0;i<Q;i++) {
L[i]=R[i]=i;
x[i].first=numx[x[i].first];
x[i].second=numx[x[i].second];
y[i].first=numy[y[i].first];
y[i].second=numy[y[i].second];
}
sort(L.begin(),L.end(),[&](int a, int b) {return x[a].first<x[b].first;});
sort(R.begin(),R.end(),[&](int a, int b) {return x[a].second<x[b].second;});
for(int i=j=k=0;i<N;i++) {
for(;j<Q && x[L[j]].first==i;j++) ret[L[j]]-=get_cnt(y[L[j]]);
update(numy[num_rev[i]],1);
for(;k<Q && x[R[k]].second==i;k++) ret[R[k]]+=get_cnt(y[R[k]]);
}
for(int i=0;i<Q;i++) ret[i]=ret[i]>0;
return ret;
}
