#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
int n, m;
//1 이 N->1, 2가 1->N순서
vector<int> tree1[200010], tree2[200010], gr[200010];
pii rn1[200010], rn2[200010];
int mi[20][200010], ma[20][200010], par1[20][200010], par2[20][200010];
int anc[200010], ord;
int nh[200010], root[200010];
int findanc(int x){
if(x==anc[x]) return x;
return anc[x]=findanc(anc[x]);
}
void dfs1(int x, int par){
//printf("dfs1(%d %d)\n", x, par);
mi[0][x] = par;
par1[0][x]=par;
rn1[x].fi = ++ord;
for(auto i:tree1[x]) if(i!=par){
dfs1(i,x);
}
rn1[x].se = ord;
}
void dfs2(int x, int par){
//printf("dfs2(%d %d)\n", x, par);
ma[0][x] = par;
par2[0][x]=par;
rn2[x].fi = ++ord;
nh[rn1[x].fi] = ord;
for(auto i:tree2[x]) if(i!=par){
dfs2(i,x);
}
rn2[x].se = ord;
}
struct Node{
int sum, l, r;
Node(){l=r=sum=0;}
};
vector<Node> pst;
void gang(int bef, int cur, int l, int r, int i){
pst[cur] = pst[bef];
pst[cur].sum++;
if(l==r) return ;
int m = (l+r)/2;
if(i<=m){
pst[cur].l = pst.size();
pst.push_back(Node());
gang(pst[bef].l, pst[cur].l, l, m, i);
}
else{
pst[cur].r = pst.size();
pst.push_back(Node());
gang(pst[bef].r,pst[cur].r, m+1, r, i);
}
}
int get(int bef, int cur, int l, int r, int s, int e){
if(r<s||e<l||s>e) return 0;
if(s<=l&&r<=e) return pst[cur].sum - pst[bef].sum;
return get(pst[bef].l, pst[cur].l, l, (l+r)/2, s, e)
+ get(pst[bef].r, pst[cur].r, (l+r)/2+1, r, s, e);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
n = N;
m = X.size();
for(int i=0;i<m;i++){
int a = X[i], b = Y[i]; a++;b++;
gr[a].push_back(b);
gr[b].push_back(a);
}
for(int i=1;i<=n;i++) anc[i]=i;
for(int i=n;i>=1;i--){
for(auto j:gr[i]){
if(j<i) continue;
int a = findanc(j), b = findanc(i);
if(a==b) continue;
anc[a]=b;
tree1[a].push_back(b);
tree1[b].push_back(a);
}
}
for(int i=1;i<=n;i++) anc[i]=i;
for(int i=1;i<=n;i++){
for(auto j:gr[i]){
if(j>i) continue;
int a = findanc(j), b = findanc(i);
if(a==b) continue;
anc[a]=b;
tree2[a].push_back(b);
tree2[b].push_back(a);
}
}
ord=0;dfs1(1, 0);
ord=0;dfs2(n, 0);
ma[0][n] = 2*n;
//cout<<"phase1"<<endl;
pst.push_back(Node());
//for(int i=1;i<=n;i++) printf("nh[%d]=%d\n", i, nh[i]);
for(int i=1;i<=n;i++){
root[i]=pst.size();
pst.push_back(Node());
gang(root[i-1], root[i], 1, n, nh[i]);
}
//cout<<"phase2"<<endl;
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
par1[i][j] = par1[i-1][par1[i-1][j]];
par2[i][j] = par2[i-1][par2[i-1][j]];
mi[i][j] = min(mi[i-1][j], mi[i-1][par1[i-1][j]]);
ma[i][j] = max(ma[i-1][j], ma[i-1][par2[i-1][j]]);
}
}
//for(int i=1;i<=n;i++) printf("i=%d (%d %d)\n", i, rn1[i].fi, rn2[i].fi);
int Q = S.size();
std::vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
S[i]++;E[i]++;L[i]++;R[i]++;
int x = S[i], y = E[i];
for(int j=19;j>=0;j--){
if(mi[j][x]>=L[i]) x = par1[j][x];
if(ma[j][y]<=R[i]) y = par2[j][y];
}
//printf("x = %d y = %d\n", x, y);
int sum = get(root[rn1[x].fi-1], root[rn1[x].se], 1, n, rn2[y].fi, rn2[y].se);
if(sum) A[i]=1;
else A[i]=0;
}
return A;
}
