#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long ll;
const int N=200005;
struct DSU
{
int n;
int root;
vector<int> p;
vector<int> sz;
vector<vector<int>> g;
vector<int> tin;
vector<int> tout;
int tcnt;
vector<array<int,18>> up;
int edges;
DSU(int nn,int r)
{
n=nn;
root=r;
edges=n-1;
tcnt=0;
p.assign(n,0);
for(int i=0;i<n;i++) p[i]=i;
sz.assign(n,1);
g.resize(n);
tin.assign(n,-1);
tout.assign(n,-1);
up.resize(n);
for(int i=0;i<n;i++) up[i].fill(-1);
}
int find_set(int a)
{
if(a==p[a]) return a;
else return (p[a]=find_set(p[a]));
}
void merge_sets(int a,int b) //a should be parent if mergeable
{
a=find_set(a);
b=find_set(b);
if(a==b) return;
g[a].push_back(b);
p[b]=a;
sz[a]+=sz[b];
if((--edges)==0) dfs(root);
}
void dfs(int a)
{
tin[a]=tcnt++;
for(int i=1;i<18;i++)
{
if(up[a][i-1]==-1) break;
up[a][i]=up[up[a][i-1]][i-1];
}
for(int to:g[a])
{
up[to][0]=a;
dfs(to);
}
tout[a]=tcnt-1;
}
int find_up(int a,auto f)
{
for(int i=17;i>=0;i--) if(up[a][i]!=-1&&f(up[a][i])==1) a=up[a][i];
return a;
}
};
vector<int> tree(4*N,0);
void update(int idx,int l,int r,int pos,int x)
{
if(l==r) tree[idx]+=x;
else
{
int m=(l+r)/2;
if(pos<=m) update(2*idx,l,m,pos,x);
else update(2*idx+1,m+1,r,pos,x);
tree[idx]=tree[2*idx]+tree[2*idx+1];
}
}
int query(int idx,int l,int r,int ql,int qr)
{
if(ql>qr) return 0;
if(l==ql&&r==qr) return tree[idx];
int m=(l+r)/2;
return query(2*idx,l,m,ql,min(qr,m))+query(2*idx+1,m+1,r,max(ql,m+1),qr);
}
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();
int q=s.size();
vector<int> v[n];
for(int i=0;i<m;i++)
{
v[x[i]].push_back(y[i]);
v[y[i]].push_back(x[i]);
}
DSU one(n,0);
for(int i=n-1;i>=0;i--)
{
for(int to:v[i]) if(to>i) one.merge_sets(i,to);
}
DSU two(n,n-1);
for(int i=0;i<n;i++)
{
for(int to:v[i]) if(to<i) two.merge_sets(i,to);
}
vector<array<int,2>> points(n);
for(int i=0;i<n;i++) points[i]={one.tin[i],two.tin[i]};
vector<int> add[n];
for(int i=0;i<n;i++) add[points[i][0]].push_back(points[i][1]);
vector<int> res(q,0);
vector<array<int,4>> queries[n]; //l,r,id,d
for(int i=0;i<q;i++)
{
int u=one.find_up(s[i],[&](int a)->bool{return (a>=l[i]);});
int lone=one.tin[u];
int rone=one.tout[u];
u=two.find_up(e[i],[&](int a)->bool{return (a<=r[i]);});
int ltwo=two.tin[u];
int rtwo=two.tout[u];
if(lone>0) queries[lone-1].push_back({ltwo,rtwo,i,-1});
queries[rone].push_back({ltwo,rtwo,i,1});
}
for(int i=0;i<n;i++)
{
for(int a:add[i]) update(1,0,n-1,a,1);
for(auto [a,b,id,d]:queries[i]) res[id]+=(d*query(1,0,n-1,a,b));
}
for(int i=0;i<q;i++) res[i]=(res[i]>0);
return res;
}
//int main()
//{
//
// return 0;
//}
