#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int a,b;
vector<pair<int,int>> edge;
vector<vector<vector<int>>> z;
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);
}
vector<array<int,2>> val;
const int LOG = 20;
vector<vector<array<int,2>>> up;
int root1,root2,tour1,tour2;
vector<array<int,2>> rev;
struct dsu{
vector<int> par;
vector<int> sz;
int cur;
void init(int _a, int sadge){
cur = _a - 1;
par.assign(sadge,0);
for (int i=0;i<sadge;i++){
par[i]=i;
}
}
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;
}
cur++;
val[cur][t]=val[x][t];
z[cur][t].push_back(x);
z[cur][t].push_back(y);
par[y]=cur;
par[x]=cur;
up[x][0][t]=cur;
up[y][0][t]=cur;
}
};
dsu d;
vector<array<int,2>> sta;
vector<array<int,2>> fin;
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]){
dfs(p,t);
}
fin[i][t]=tour;
}
struct node{
int l,r,base,id;
};
vector<vector<node>> pos;
vector<int> res;
vector<int> bit;
int BITN;
void update(int i,int valx){
i++;
while (i<=BITN){
bit[i]+=valx;
i+=i&-i;
}
}
int query(int i){
if (i < 0) return 0;
i++;
int resq=0;
while (i>0){
resq+=bit[i];
i-=i&-i;
}
return resq;
}
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 = S.size();
vector<int> A(q);
for (int i = 0; i < q; ++i) {
A[i] = 0;
}
a=N;
b=X.size();
edge.assign(b, {0,0});
for (int i=0;i<b;i++){
edge[i]={X[i],Y[i]};
}
int sadge = a + b + 5;
if (sadge < a+5) sadge = a + 5;
z.assign(sadge, vector<vector<int>>(2));
val.assign(sadge, {0,0});
up.assign(sadge, vector<array<int,2>>(LOG));
sta.assign(sadge, {0,0});
fin.assign(sadge, {0,0});
rev.assign(sadge, {0,0});
for (int i=0;i<a;i++){
val[i][0]=val[i][1]=i;
}
for (int i=0;i<sadge;i++){
for (int j=0;j<LOG;j++){
up[i][j][0]=up[i][j][1]=0;
}
}
sort(edge.begin(),edge.end(),cmp);
d.init(a, sadge);
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.cur;
sort(edge.begin(),edge.end(),cmp1);
d.init(a, sadge);
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.cur;
if (root1 >= 0) up[root1][0][0] = root1;
if (root2 >= 0) up[root2][0][1] = root2;
int maxNodeIndex = max(root1, root2);
if (maxNodeIndex < a-1) maxNodeIndex = a-1;
for (int i=0;i<=maxNodeIndex;i++){
if (up[i][0][0] == 0 && i != root1) up[i][0][0] = i;
if (up[i][0][1] == 0 && i != root2) up[i][0][1] = i;
}
for (int j=1;j<LOG;j++){
for (int i=0;i<=maxNodeIndex;i++){
int mid0 = up[i][j-1][0];
up[i][j][0] = up[mid0][j-1][0];
int mid1 = up[i][j-1][1];
up[i][j][1] = up[mid1][j-1][1];
}
}
tour = 0;
dfs(root1,0);
tour1 = tour;
tour = 0;
dfs(root2,1);
tour2 = tour;
pos.assign(tour2 + 2, vector<node>());
res.assign(q, 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=LOG-1;j>=0;j--){
int nx = up[x][j][1];
if (nx >= 0 && val[nx][1] >= l){
x = nx;
}
}
for (int j=LOG-1;j>=0;j--){
int ny = up[y][j][0];
if (ny >= 0 && val[ny][0] <= r){
y = ny;
}
}
int idx_add = sta[x][1] - 1;
int idx_rem = fin[x][1];
int Lpos = sta[y][0];
int Rpos = fin[y][0];
if (idx_add >= 0 && idx_add <= tour2) pos[idx_add].push_back({Lpos,Rpos,-1,i});
if (idx_rem >= 0 && idx_rem <= tour2) pos[idx_rem].push_back({Lpos,Rpos,1,i});
}
BITN = max(1, tour1 + 2);
bit.assign(BITN+5, 0);
for (int i=0;i<=tour2;i++){
if (i){
int node = rev[i][1];
if (node >= 0 && node < (int)sta.size()){
int pos0 = sta[node][0];
if (pos0 > 0 && pos0 <= tour1) update(pos0-1, 1);
else if (pos0 >= 0 && pos0 <= tour1) update(pos0, 1);
}
}
for (auto &p:pos[i]){
int cnt = query(p.r) - query(p.l-1);
res[p.id]+= p.base * cnt;
}
}
for (int i=0;i<q;i++){
A[i]=(res[i]>0);
}
return A;
}
