#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
#define N 500050
int n;
int bit[N];
void upd(int x, int v){
x+=5;
assert(x>0);
for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}
int query(int x){
x+=5;
assert(x>0);
int sum = 0;
for(int i = x; i > 0; i -=(i&-i)) sum += bit[i];
return sum;
}
struct kruskal_tree{
vector<int>grafo[N];
int pai[N], nivel[N], anc[N][20],cnt, v[N];
int ini[N], fim[N], tempo;
void init(){
for(int i=0;i< N;i++)pai[i]=i,nivel[i]=v[i]=0;
tempo =0;cnt=n;
}
int find(int x){
if(x==pai[x])return x;
return pai[x]=find(pai[x]);
}
void join(int a, int b, int cost){
a=find(a);b=find(b);
if(a==b) return;
++cnt;
pai[cnt]=cnt;
grafo[cnt].pb(a);
grafo[cnt].pb(b);
pai[a]=cnt;pai[b]=cnt;
v[cnt] = cost;
}
void dfs(int x, int p){
ini[x]=++tempo;
nivel[x]=nivel[p]+1;
anc[x][0]=p;
for(auto v:grafo[x]){
if(v==p)continue;
dfs(v,x);
}
fim[x]=tempo;
}
void get_anc(){
memset(anc,-1,sizeof anc);
for(int i = cnt;i>=1;i--){
if(!nivel[i]) dfs(i,i);
}
for(int j=1;j<20;j++)
for(int i=1;i<=cnt;i++)
anc[i][j]=anc[anc[i][j-1]][j-1];
}
} mn,mx;
struct line{
int x, yl, yr, id, tipo; //0=ponto,-1 =close, +1 = open
};
vector<line> lines;
vector<int> check_validity(int nn, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n=nn;
mn.init();mx.init();
int m = sz(X),q=sz(S);
vector<array<int,3>> ed[2];
//criar max mst com arestas = min(a, b)
//criar min mst com arestas = max(a, b)
for(int i = 0; i < m;i++){
int a = X[i]+1, b = Y[i]+1, c1 = min(a,b),c2=max(a,b);
ed[0].pb({c1,a,b});ed[1].pb({c2,a,b});
}
sort(all(ed[0]), [&](auto a, auto b){
return a[0] > b[0];
});
sort(all(ed[1]));
for(auto w: ed[0]) mx.join(w[1],w[2],w[0]);
for(auto w: ed[1]) mn.join(w[1],w[2],w[0]);
mx.get_anc();
mn.get_anc();
vector<int> ans(q);
for(int i =0;i<q; i++){
int st = S[i]+1, en = E[i]+1, l = L[i]+1, r = R[i]+1;
int u=st,v=en;
for(int j = 19; j >= 0; j--)
if(mx.anc[u][j] != -1 and mx.v[mx.anc[u][j]] >= l)
u = mx.anc[u][j];
for(int j = 19; j>=0;j--)
if(mn.anc[v][j] != -1 and mn.v[mn.anc[v][j]] <= r)
v = mn.anc[v][j];
if(st < l or en > r) continue;
lines.pb({mn.ini[v], mx.ini[u], mx.fim[u], i, -1});
lines.pb({mn.fim[v], mx.ini[u], mx.fim[u], i, 1});
}
for(int i = 1; i <= n; i++){
lines.pb({mn.ini[i], mx.ini[i], mx.ini[i], i, 0});
}
sort(all(lines), [&](auto a, auto b){
if(a.x != b.x) return a.x<b.x;
return a.tipo < b.tipo;
});
for(int i = 0; i < sz(lines); i++){
if(lines[i].tipo == -1){
ans[lines[i].id] -= query(lines[i].yr);
ans[lines[i].id] += query(lines[i].yl - 1);
}
else if(lines[i].tipo == 1){
ans[lines[i].id] += query(lines[i].yr);
ans[lines[i].id] -= query(lines[i].yl -1);
}
else upd(lines[i].yl,1);
}
for(int i=0;i<q;i++)ans[i]=min(ans[i],1);
return ans;
}
