#include"werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
struct dsutree
{
int sp[MAXN][20],dis[MAXN],dsu[MAXN];
vector<int> ds[MAXN];
int root(int i)
{
if(!dsu[i]) return i;
return dsu[i]=root(dsu[i]);
}
void merge(int i,int j,bool ck)
{
i++,j++;
if((i=root(i))==(j=root(j))) return ;
if((i>j)^(!ck)) swap(i,j);
dsu[j]=i,ds[i-1].push_back(j-1);
}
void dfs(int i,int pre)
{
sp[i][0]=pre;
for(int j=1;j<=18;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
for(auto v:ds[i])
{
dis[v]=dis[i]+1;
dfs(v,i);
}
}
int lca(int a,int b)
{
int x=dis[a],y=dis[b],m=min(x,y);
for(int i=18;i+1;i--)
{
if((x-m)&(1<<i)) a=sp[a][i];
if((y-m)&(1<<i)) b=sp[b][i];
}
if(a==b) return a;
for(int i=18;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
return sp[a][0];
}
};
dsutree a,b;
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();
vector< vector<int> > ds(n);
for(int i=0;i<m;i++)
{
if(X[i]>Y[i]) swap(X[i],Y[i]);
ds[Y[i]].push_back(X[i]);
}
for(int i=0;i<n;i++)
{
for(auto v:ds[i]) a.merge(i,v,false);
ds[i].clear();
}
a.dfs(n-1,n-1);
for(int i=0;i<m;i++) ds[X[i]].push_back(Y[i]);
for(int i=n-1;i+1;i--) for(auto v:ds[i]) b.merge(i,v,true);
b.dfs(0,0);
vector<int> ans;
for(int i=0;i<q;i++) if(a.lca(S[i],E[i])>R[i]&&b.lca(S[i],E[i])<L[i]) ans.push_back(0);
else ans.push_back(1);
return ans;
}
