#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define eb emplace_back
#define all(v) ((v).begin()),((v).end())
#define fi first
#define se second
#define rb(x) ((x)&(-(x)))
const int MAXN = 200010;
const int MX = 1 << 18;
int N;
struct SEG {
int seg[2 * MX];
void mkseg(int idx, int l, int r, vector<int> &e) {
if(l == r) seg[idx] = e[l];
else {
int m = (l + r) / 2;
mkseg(idx * 2, l, m, e);
mkseg(idx * 2 + 1, m + 1, r, e);
seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
}
}
void init(vector<int> &e) { mkseg(1, 0, e.size() - 1, e); }
int gseg(int idx, int l, int r, int x, int z) {
if(x < l) return l - 1;
//if(idx == 1) printf("gseg(x = %d, z = %d)\n", x, z);
if(seg[idx] >= z) return l - 1;
if(l == r) return l;
int m = (l + r) / 2;
if(x > m) {
int t = gseg(idx * 2 + 1, m + 1, r, x, z);
if(t > m) return t;
}
return gseg(idx * 2, l, m, x, z);
}
};
struct TREE {
vector<pii> ed;
int uni[MAXN];
vector<int> v[MAXN], e[MAXN];
int dn[MAXN];
SEG seg, segr;
int guni(int x) { return uni[x] == x ? x : uni[x] = guni(uni[x]); }
void init(vector<int> &X, vector<int> &Y) {
int M = X.size();
for(int i = 0; i < M; i++) ed.eb(min(X[i], Y[i]), max(X[i], Y[i]));
sort(all(ed), greater<pii>());
for(int i = 0; i < N; i++) {
v[i].push_back(i);
uni[i] = i;
}
//for(auto a : ed) printf("(%d, %d)", a.fi, a.se);
//puts("");
for(auto a : ed) {
int x = guni(a.fi), y = guni(a.se);
//printf("x = %d, y = %d\n", x, y);
if(x == y) continue;
if(v[x].size() < v[y].size()) swap(x, y);
v[x].insert(v[x].end(), all(v[y]));
e[x].push_back(a.fi);
e[x].insert(e[x].end(), all(e[y]));
uni[y] = x;
}
int z = guni(0);
for(int i = 0; i < N; i++) dn[v[z][i]] = i;
/*
for(auto a : v[z]) printf("%d ", a);
puts("");
for(auto a : e[z]) printf("%d ", a);
puts("");
for(int i = 0; i < N; i++) printf("%d ", dn[i]);
puts("");
*/
seg.init(e[z]);
for(int i = 0; i < (N - 1) / 2; i++) swap(e[z][i], e[z][N - i - 2]);
segr.init(e[z]);
}
int glb(int x, int L) { return seg.gseg(1, 0, N - 2, dn[x] - 1, L) + 1; }
int grb(int x, int L) { return N - 2 - segr.gseg(1, 0, N - 2, N - dn[x] - 2, L); }
} hm, ww;
int dot[MAXN];
vector<int> qry[MAXN];
int u[MAXN], d[MAXN];
int bit[MAXN];
void updbit(int x) { for(x += 5; x < MAXN; x += rb(x)) bit[x]++; }
int gbit(int x) {
int ans = 0;
for(x += 5; x; x -= rb(x)) ans += bit[x];
return ans;
}
int gbit(int x, int y) { return gbit(y) - gbit(x - 1); }
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;
int M = X.size(), Q = S.size();
hm.init(X, Y);
for(int i = 0; i < M; i++) {
X[i] = N - 1 - X[i];
Y[i] = N - 1 - Y[i];
}
ww.init(X, Y);
for(int i = 0; i < N; i++) dot[hm.dn[i]] = ww.dn[N - i - 1];
//for(int i = 0; i < Q; i++)
//printf("%d %d %d %d\n", hm.glb(S[i], L[i]), hm.grb(S[i], L[i]), ww.glb(N - E[i] - 1, N - R[i] - 1), ww.grb(N - E[i] - 1, N - R[i] - 1));
for(int i = 0; i < Q; i++) {
int t = hm.glb(S[i], L[i]);
if(t > 0) qry[t - 1].push_back(-i - 1);
qry[hm.grb(S[i], L[i])].push_back(i);
d[i] = ww.glb(N - E[i] - 1, N - R[i] - 1);
u[i] = ww.grb(N - E[i] - 1, N - R[i] - 1);
}
vector<int> ans(Q, 0);
for(int i = 0; i < N; i++) {
updbit(dot[i]);
for(auto a : qry[i]) {
//printf("i = %d, a = %d\n", i, a);
if(a >= 0) ans[a] += gbit(d[a], u[a]);
else ans[-a - 1] -= gbit(d[-a - 1], u[-a - 1]);
}
}
for(auto &a : ans) a = min(a, 1);
return ans;
}
