#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long ll;
const int N=200005;
int n,q;
vector<int> v[N];
vector<int> solve_small(vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
vector<int> res(q,0);
for(int o=0;o<q;o++)
{
int s=ns[o];
int e=ne[o];
int l=nl[o];
int r=nr[o];
vector<array<int,2>> dp(n,{0,0});
queue<array<int,2>> b;
auto add=[&](int a,int t)
{
if(dp[a][t]==0)
{
dp[a][t]=1;
b.push({a,t});
}
};
add(s,0);
while(!b.empty())
{
auto [a,t]=b.front();
b.pop();
if(l<=a&&a<=r&&t==0) add(a,1);
for(int to:v[a])
{
if(t==0&&to>=l) add(to,0);
if(t==1&&to<=r) add(to,1);
}
}
res[o]=dp[e][1];
}
return res;
}
struct ST
{
vector<int> tree;
ST()
{
tree.assign(4*(n+5),0);
}
void update(int idx,int l,int r,int pos,int val)
{
if(l==r) tree[idx]=val;
else
{
int m=(l+r)/2;
if(pos<=m) update(2*idx,l,m,pos,val);
else update(2*idx+1,m+1,r,pos,val);
tree[idx]=tree[2*idx]+tree[2*idx+1];
}
}
void upd(int pos,int val){update(1,0,n-1,pos,val);}
int descend(int idx,int l,int r,int ql,int qr,int t) //0-l,1-r
{
if(ql>qr||tree[idx]==0) return -1;
if(l==r) return l;
int m=(l+r)/2;
if(t==0)
{
int x=descend(2*idx,l,m,ql,min(qr,m),t);
if(x!=-1) return x;
else return descend(2*idx+1,m+1,r,max(ql,m+1),qr,t);
}
else
{
int x=descend(2*idx+1,m+1,r,max(ql,m+1),qr,t);
if(x!=-1) return x;
else return descend(2*idx,l,m,ql,min(qr,m),t);
}
}
int dsn(int ql,int qr,int t){return descend(1,0,n-1,ql,qr,t);}
};
vector<int> tmpini(N,0);
vector<set<int>> tree(4*N);
void build(int idx,int l,int r)
{
if(l==r) tree[idx]={tmpini[l]};
else
{
int m=(l+r)/2;
build(2*idx,l,m);
build(2*idx+1,m+1,r);
tree[idx]=tree[2*idx];
for(int x:tree[2*idx+1]) tree[idx].insert(x);
}
}
bool query(int idx,int l,int r,int ql,int qr,int one,int two)
{
if(ql>qr) return 0;
if(l==ql&&r==qr)
{
auto it=tree[idx].lower_bound(one);
return (it!=tree[idx].end()&&(*it)<=r);
}
int m=(l+r)/2;
return (query(2*idx,l,m,ql,min(qr,m),one,two)||query(2*idx+1,m+1,r,max(ql,m+1),qr,one,two));
}
vector<int> solve_line(vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
vector<int> pos(n,-1);
int src=-1;
for(int i=0;i<n;i++) if(v[i].size()==1) src=i;
int p=0;
vector<int> h(n,-1);
while(pos[src]==-1)
{
// cerr << src << " ";
h[p]=src;
pos[src]=p++;
for(int to:v[src])
{
if(pos[to]==-1)
{
src=to;
break;
}
}
}
// cerr << endl;
tmpini=h;
build(1,0,n-1);
vector<int> badhuman(n,-1);
vector<int> badwolf(n,-1);
vector<int> ord[n];
for(int i=0;i<q;i++)
{
int l=nl[i];
ord[l].push_back(i);
}
ST one;
for(int i=0;i<n;i++)
{
for(int a:ord[i])
{
int s=ns[a];
int e=ne[a];
if(pos[s]<pos[e]) badhuman[a]=one.dsn(pos[s],pos[e],0);
else badhuman[a]=one.dsn(pos[e],pos[s],1);
}
one.upd(pos[i],1);
}
for(int i=0;i<n;i++) ord[i].clear();
for(int i=0;i<q;i++)
{
int r=nr[i];
ord[r].push_back(i);
}
ST two;
for(int i=n-1;i>=0;i--)
{
for(int a:ord[i])
{
int s=ns[a];
int e=ne[a];
if(pos[s]<pos[e]) badwolf[a]=two.dsn(pos[s],pos[e],1);
else badwolf[a]=two.dsn(pos[e],pos[s],0);
}
two.upd(pos[i],1);
}
vector<int> res(q,0);
for(int i=0;i<q;i++)
{
// cerr << i << ": " << badhuman[i] << " " << badwolf[i] << endl;
int l=nl[i];
int r=nr[i];
int s=ns[i];
int e=ne[i];
if(badhuman[i]==-1||badwolf[i]==-1) res[i]=1;
else if(pos[s]<pos[e]) res[i]=(badwolf[i]<badhuman[i]&&query(1,0,n-1,badwolf[i]+1,badhuman[i]-1,l,r)==1);
else res[i]=(badhuman[i]<badwolf[i]&&query(1,0,n-1,badhuman[i]+1,badwolf[i]-1,l,r)==1);
}
return res;
}
void ini(int nn,vector<int> nx,vector<int> ny,vector<int> ns)
{
n=nn;
int m=nx.size();
q=ns.size();
for(int i=0;i<m;i++)
{
v[nx[i]].push_back(ny[i]);
v[ny[i]].push_back(nx[i]);
}
}
void clean()
{
for(int i=0;i<n;i++) v[i].clear();
}
vector<int> check_validity(int nn,vector<int> nx,vector<int> ny,vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
ini(nn,nx,ny,ns);
int m=nx.size();
if(n<=3000&&m<=6000&&q<=3000) return solve_small(ns,ne,nl,nr);
else return solve_line(ns,ne,nl,nr);
}
//int main()
//{
// mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
// auto rng=[&](int l,int r)->int{return uniform_int_distribution<int>(l,r)(gen);};
// auto rng_shuffle=[&](auto &t){shuffle(t.begin(),t.end(),gen);};
// while(1)
// {
// n=rng(2,4);
// int m=n-1;
// q=1;
// vector<int> x(m);
// vector<int> y(m);
// vector<int> ord(n);
// for(int i=0;i<n;i++) ord[i]=i;
// rng_shuffle(ord);
// for(int i=0;i<n-1;i++)
// {
// x[i]=ord[i];
// y[i]=ord[i+1];
// }
// vector<int> s(q);
// vector<int> e(q);
// vector<int> l(q);
// vector<int> r(q);
// for(int i=0;i<q;i++)
// {
// s[i]=rng(0,n-2);
// e[i]=rng(s[i]+1,n-1);
// l[i]=rng(0,s[i]);
// r[i]=rng(e[i],n-1);
// }
// ini(n,x,y,s);
// vector<int> one=solve_small(s,e,l,r);
// vector<int> two=solve_line(s,e,l,r);
// if(one!=two)
// {
// cout << "WA" << endl;
// cout << n << " " << m << " " << q << endl;
// for(int i=0;i<m;i++) cout << x[i] << " " << y[i] << endl;
// for(int i=0;i<q;i++) cout << s[i] << " " << e[i] << " " << l[i] << " " << r[i] << endl;
// cout << "|Received| ";
// for(int i=0;i<q;i++) cout << two[i];
// cout << endl;
// cout << "|Expected| ";
// for(int i=0;i<q;i++) cout << one[i];
// cout << endl;
// break;
// }
// else cout << "OK" << endl;
// clean();
// }
// return 0;
//}
