#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
vector<vector<int>> g;
vector<int> ln;
vector<pair<pair<int,int>,int>> q,q2;
vector<int> ord;
vector<bool> is1, is2;
vector<pair<int,int>> rng1,rng2;
void makeline(int v, int par)
{
ord[v]=int(ln.size());
ln.pb(v);
for(int x:g[v])
if(x!=par) makeline(x,v);
}
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
vector<int> ret;
int m=X.size(), Q=S.size();
g.resize(n);
ord.resize(n);
unordered_set<int> elim;
for(int i=0;i<n;++i) is1.pb(0), is2.pb(0), elim.insert(i);
for(int i=0;i<m;i++)
{
int x=X[i], y=Y[i];
g[x].pb(y);
g[y].pb(x);
if(g[x].size()==2) elim.erase(x);
if(g[y].size()==2) elim.erase(y);
}
makeline(*elim.begin(),-1);
for(int i=0;i<Q;i++)
{
rng1.pb({-1,-1}), rng2.pb({-1,-1});
int s=S[i], e=E[i], l=L[i], r=R[i];
q.pb({{r,e},i});
q2.pb({{l,s},i});
}
sort(q.begin(),q.end());
sort(q2.begin(),q2.end(),greater<pair<pair<int,int>,int>>());
int k=0;
for(int i=0;i<n;i++)
{
int j=ord[i];
is1[j]=1;
while(k<Q && q[k].x.x==i)
{
int id=ord[q[k].x.y];
int lft=id;
while(lft>0)
{
if(is1[lft-1]) lft--;
else break;
}
int rgt=id;
while(rgt<n-1)
{
if(is1[rgt+1]) rgt++;
else break;
}
rng1[q[k].y]={lft,rgt};
k++;
}
}
k=0;
for(int i=n-1;i>=0;i--)
{
int j=ord[i];
is2[j]=1;
while(k<Q && q2[k].x.x==i)
{
int id=ord[q[k].x.y];
int lft=id;
while(lft>0)
{
if(is2[lft-1]) lft--;
else break;
}
int rgt=id;
while(rgt<n-1)
{
if(is2[rgt+1]) rgt++;
else break;
}
rng2[q2[k].y]={lft,rgt};
k++;
}
}
for(int i=0;i<Q;i++)
{
int l1=rng1[i].x, r1=rng1[i].y, l2=rng2[i].x, r2=rng2[i].y;
if(l2>r1 || l1>r2) ret.pb(0);
else
{ret.pb(1);}
}
return ret;
}
/*
int main()
{
vector<int> ans=check_validity(5,{0,1,2,3},{3,4,4,2},{},{},{},{});
for(int x:ans) cout<<x<<" ";
}
*/
