#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXA = 1000005;
const int MAXV = 400005;
int a,b;
pair<int,int> edge[MAXA];
vector<int> z[MAXV][2];
bool cmp(pair<int,int> A,pair<int,int> B){
return max(A.first,A.second) < max(B.first,B.second);
}
bool cmp1(pair<int,int> A,pair<int,int> B){
return min(A.first,A.second) > min(B.first,B.second);
}
int root1, root2;
int rev[MAXV][2];
struct dsu{
int par[MAXV];
int root;
void init(int n){
for (int i=1;i<=n;i++) par[i]=i;
root = 0;
}
int find(int u){
if (par[u]==u) return u;
return par[u]=find(par[u]);
}
void join(int x,int y,int t){
x=find(x);
y=find(y);
if (x==y) return;
z[x][t].push_back(y);
root = x;
par[y]=x;
}
};
dsu d;
int parA[MAXV][21][2];
int sta[MAXV][2];
int finA[MAXV][2];
int tour;
void dfs(int i,int t){
if (i==0) return;
tour++;
sta[i][t]=tour;
rev[tour][t]=i;
for (auto p: z[i][t]){
parA[p][0][t]=i;
dfs(p,t);
}
finA[i][t]=tour;
}
struct node{
int l,r,base,id;
};
vector<node> pos[MAXV];
int resArr[MAXV];
int bit[MAXV];
void update(int i,int val){
while (i < MAXV){
bit[i] += val;
i += i & -i;
}
}
int query(int i){
int res=0;
while (i>0){
res += bit[i];
i -= i & -i;
}
return res;
}
vector<int> ans;
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 q = (int)L.size();
ans.assign(q, 0);
a = N;
b = (int)X.size();
for (int i=0;i<=a+5 && i<MAXV;i++){
z[i][0].clear();
z[i][1].clear();
pos[i].clear();
resArr[i]=0;
sta[i][0]=sta[i][1]=0;
finA[i][0]=finA[i][1]=0;
for (int j=0;j<21;j++){
parA[i][j][0]=parA[i][j][1]=0;
}
rev[i][0]=rev[i][1]=0;
bit[i]=0;
}
for (int i=0;i<b;i++){
X[i]++; Y[i]++;
}
for (int i=0;i<q;i++){
L[i]++; R[i]++; S[i]++; E[i]++;
}
for (int i=0;i<b;i++){
edge[i] = {X[i], Y[i]};
}
sort(edge, edge + b, cmp);
d.init(a);
for (int i=0;i<b;i++){
int u = max(edge[i].first, edge[i].second);
int v = min(edge[i].first, edge[i].second);
d.join(u, v, 0);
}
root1 = d.root;
sort(edge, edge + b, cmp1);
d.init(a);
for (int i=0;i<b;i++){
int u = min(edge[i].first, edge[i].second);
int v = max(edge[i].first, edge[i].second);
d.join(u, v, 1);
}
root2 = d.root;
tour = 0;
if (root2 != 0) dfs(root2, 1);
tour = 0;
if (root1 != 0) dfs(root1, 0);
for (int j=1;j<=20;j++){
for (int i=1;i<=a;i++){
int up0 = parA[i][j-1][0];
int up1 = parA[i][j-1][1];
parA[i][j][0] = (up0>0 ? parA[up0][j-1][0] : 0);
parA[i][j][1] = (up1>0 ? parA[up1][j-1][1] : 0);
}
}
for (int i=0;i<q;i++){
int x = S[i];
int y = E[i];
int l = L[i];
int r = R[i];
for (int j=20;j>=0;j--){
if (parA[x][j][1] >= l && parA[x][j][1] != 0) x = parA[x][j][1];
if (parA[y][j][0] != 0 && parA[y][j][0] <= r) y = parA[y][j][0];
}
if (sta[x][1] == 0 || sta[y][0] == 0) continue;
pos[sta[x][1]-1].push_back({sta[y][0], finA[y][0], -1, i});
pos[finA[x][1]].push_back({sta[y][0], finA[y][0], 1, i});
}
int maxTour1 = 0;
for (int i=1;i<=a;i++) if (sta[i][1] > maxTour1) maxTour1 = sta[i][1];
for (int i=0;i<=maxTour1;i++){
if (rev[i][1] != 0 && sta[rev[i][1]][0] != 0){
update(sta[rev[i][1]][0], 1);
}
for (auto &p: pos[i]){
int add = query(p.r) - query(p.l - 1);
resArr[p.id] += p.base * add;
}
}
for (int i=0;i<q;i++){
ans[i] = (resArr[i] > 0);
}
return ans;
}
