#include "werewolf.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef vector<int> vi;
const LL llinf=987654321987654321;
const int inf=987654321;
int n, q;
struct query{
int l, r;
int s, e;
int stx, finx, sty, finy;
int num;
}qu[200010];
bool operator < (const query &a, const query &b){
if(a.l!=b.l)return a.l<b.l;
if(a.r!=b.r)return a.r<b.r;
if(a.s!=b.s)return a.s<b.s;
if(a.e!=b.e)return a.e<b.e;
}
bool cmp1(query a, query b){
if(a.l!=b.l)return a.l<b.l;
return a<b;
}
bool cmp2(query a, query b){
if(a.r!=b.r)return a.r>b.r;
return !(a<b);
}
bool cmp3(query a, query b){
if(a.finx!=b.finx)return a.finx<b.finx;
return a<b;
}
vi link[200010];
struct Union_Find{
int par[200010];
void init(){for(int i=1; i<=200000; i++)par[i]=i;}
int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
void mergepar(int a, int b){
a=findpar(a);
b=findpar(b);
par[a]=b;
}
bool chk(int a, int b){return findpar(a)==findpar(b);}
}tl;
struct Treenode{
int maxx, et;
int fr, re;
int l, r;
}treel[400010], treer[400010];
int treelrev[200010], treerrev[200010];
int lrv[200010], rrv[200010];
pii point[200010];
int tmp;
void eulerl(int num){
if(treel[num].l==-1){
++tmp;
treel[num].fr=tmp;
treel[num].re=tmp;
treel[num].et=tmp;
treelrev[treel[num].maxx]=tmp;
lrv[treel[num].maxx]=num;
return;
}
eulerl(treel[num].l);
eulerl(treel[num].r);
treel[num].fr=treel[treel[num].l].fr;
treel[num].re=treel[treel[num].r].re;
}
void eulerr(int num){
if(treer[num].l==-1){
++tmp;
treer[num].fr=tmp;
treer[num].re=tmp;
treer[num].et=tmp;
treerrev[treer[num].maxx]=tmp;
rrv[treer[num].maxx]=num;
return;
}
eulerr(treer[num].l);
eulerr(treer[num].r);
treer[num].fr=treer[treer[num].l].fr;
treer[num].re=treer[treer[num].r].re;
}
void makeltree(){
sort(qu+1, qu+q+1, cmp1);
int x=0;
tl.init();
for(int i=1; i<=n; i++){
x++;
treel[x].maxx=i;
treel[x].l=-1;
treel[x].r=-1;
lrv[i]=x;
for(int j=0; j<link[i].size(); j++){
if(link[i][j]>i||tl.chk(i, link[i][j]))continue;
int temp=tl.findpar(link[i][j]);
x++;
treel[x].maxx=i;
treel[x].l=lrv[temp];
treel[x].r=x-1;
lrv[i]=x;
tl.mergepar(temp, i);
}
}
eulerl(x);
x=0;
tl.init();
int pv=1;
for(int i=1; i<=n; i++){
x++;
for(int j=0; j<link[i].size(); j++){
if(link[i][j]>i||tl.chk(i, link[i][j]))continue;
lrv[i]=++x;
tl.mergepar(link[i][j], i);
}
for(; pv<=q; pv++){
if(qu[pv].l>i)break;
int t=lrv[tl.findpar(qu[pv].s)];
qu[pv].stx=treel[t].fr;
qu[pv].finx=treel[t].re;
}
}
}
void makertree(){
sort(qu+1, qu+q+1, cmp2);
int x=0;
tl.init();
for(int i=n; i>=1; i--){
x++;
treer[x].maxx=i;
treer[x].l=-1;
treer[x].r=-1;
rrv[i]=x;
for(int j=0; j<link[i].size(); j++){
if(link[i][j]<i||tl.chk(i, link[i][j]))continue;
int temp=tl.findpar(link[i][j]);
x++;
treer[x].maxx=i;
treer[x].r=rrv[temp];
treer[x].l=x-1;
rrv[i]=x;
tl.mergepar(temp, i);
}
}
tmp=0;
eulerr(x);
x=0;
tl.init();
int pv=1;
for(int i=n; i>=1; i--){
x++;
for(int j=0; j<link[i].size(); j++){
if(link[i][j]<i||tl.chk(i, link[i][j]))continue;
rrv[i]=++x;
tl.mergepar(link[i][j], i);
}
for(; pv<=q; pv++){
if(qu[pv].r<i)break;
int t=rrv[tl.findpar(qu[pv].e)];
qu[pv].sty=treer[t].fr;
qu[pv].finy=treer[t].re;
}
}
}
struct SEGMENT_TREE {
struct NODE {
int st, fin;
int q;
}tree[800010];
int x;
const int inf=987654321;
int f(int a, int b){return max(a, b);}
void maketree(int point, int num) {
if(num==1)tree[point].st=tree[point].fin=++x;
if(num<=1)return;
maketree(point*2, num-num/2);
maketree(point*2+1, num/2);
tree[point].st=tree[point*2].st;
tree[point].fin=tree[point*2+1].fin;
}
int query(int a, int b, int point) {
if(tree[point].st>=a&&tree[point].fin<=b)
return tree[point].q;
if(tree[point].st>b||tree[point].fin<a)
return 0;
return f(query(a, b, point*2), query(a, b, point*2+1));
}
void updaterange(int point, int num, int p) {
if(tree[point].st==tree[point].fin) {
tree[point].q=p;
return;
}
if(num<=tree[point*2].fin)updaterange(point*2, num, p);
else updaterange(point*2+1, num, p);
tree[point].q=f(tree[point*2].q, tree[point*2+1].q);
}
void init(int n) {
maketree(1, n);
}
int get_query(int a, int b) {
return query(a, b, 1);
}
void update(int a, int num) {
updaterange(1, a, num);
}
}seg;
vi check_validity(int N, vi X, vi Y, vi E, vi S, vi R, vi L){
n=N;
q=S.size();
for(int i=0; i<q; i++){
qu[i+1].l=L[i]+1;
qu[i+1].r=R[i]+1;
qu[i+1].s=S[i]+1;
qu[i+1].e=E[i]+1;
qu[i+1].num=i;
}
for(int i=0; i<X.size(); i++){
link[X[i]+1].pb(Y[i]+1);
link[Y[i]+1].pb(X[i]+1);
}
makeltree();
makertree();
for(int i=1; i<=n; i++){
point[i].F=treelrev[i];
point[i].S=treerrev[i];
}
sort(point+1, point+n+1);
sort(qu+1, qu+q+1, cmp3);
seg.init(n);
vi ans(q);
int pv=1;
for(int i=1; i<=n; i++){
seg.update(point[i].S, i);
for(; pv<=q; pv++){
if(i<qu[pv].finx)break;
int t=seg.get_query(qu[pv].sty, qu[pv].finy);
if(t>=qu[pv].stx)ans[qu[pv].num]=1;
}
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
