#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
const int mxN = 2e5+5;
const int lgN = 17;
const int mxM = 4e5+5;
const int mxQ = 2e5+5;
int N, M, Q;
struct Edge { int X, Y, W; } edge[mxM];
struct Query { int S, E, L, R, id; } query[mxQ];
struct SegmentTree {
multiset<int> d[4*mxN];
int n;
SegmentTree(int n): n(n) {}
void update(int x, int u, int v, int s, int e, int p) {
auto it = d[p].find(u);
if (it != d[p].end()) d[p].erase(it);
d[p].insert(v);
if (s != e) {
int m = (s+e)/2;
if (x <= m) update(x,u,v,s,m,p*2);
else update(x,u,v,m+1,e,p*2+1);
}
}
inline void update(int x, int u, int v) { update(x,u,v,0,n-1,1); }
bool query(int x, int y, int v, int s, int e, int p) {
if (s == x && e == y) {
return d[p].lower_bound(v) != d[p].upper_bound(v);
} else {
int m = (s+e)/2;
if (y <= m) return query(x,y,v,s,m,p*2);
if (x > m) return query(x,y,v,m+1,e,p*2+1);
return query(x,m,v,s,m,p*2) || query(m+1,y,v,m+1,e,p*2+1);
}
}
inline bool query(int x, int y, int v) { return query(x,y,v,0,n-1,1); }
} *ST;
struct KruskalTree {
static const int mxV = 2*mxN;
int pa[mxV], v[mxV];
vector<int> al[mxV];
int cnt, fa[mxV][lgN+1], pre[mxV], pst[mxV], dfsT;
KruskalTree(int n) {
FOR(i,0,n-1){
pa[i] = i;
v[i] = -1;
}
cnt = n;
memset(fa,-1,sizeof fa);
}
int finds(int i) { return (pa[i] == i) ? i : (pa[i] = finds(pa[i])); }
bool unions(int i, int j, int w) {
int x = finds(i), y = finds(j);
if (x != y) {
pa[cnt] = cnt;
v[cnt] = w;
al[cnt].push_back(x);
al[cnt].push_back(y);
fa[x][0] = cnt;
fa[y][0] = cnt;
pa[x] = pa[y] = cnt;
++cnt;
return true;
} return false;
}
void dfs(int u) {
pre[u] = dfsT++;
FOR(k,1,lgN){
if (fa[u][k-1] == -1) fa[u][k] = -1;
else fa[u][k] = fa[fa[u][k-1]][k-1];
}
for (int v : al[u]) { dfs(v); }
pst[u] = dfsT-1;
//TRACE(u _ v[u] _ pre[u] _ pst[u]);
}
void init() {
dfsT = 0;
dfs(cnt-1);
}
int findFaGE(int u, int val) {
RFOR(k,lgN,0){
if (fa[u][k] != -1 && v[fa[u][k]] >= val) u = fa[u][k];
}
return u;
}
} *KT;
struct UnionFind {
int pa[mxN];
set<int> child[mxN];
UnionFind(int n) {
FOR(i,0,n-1){
pa[i] = i;
child[i].insert(i);
ST->update(KT->pre[i],-1,i);
}
}
int finds(int i) { return (pa[i] == i) ? i : (pa[i] = finds(pa[i])); }
bool unions(int i, int j) {
int x = finds(i), y = finds(j);
if (x != y) {
if (SZ(child[x]) < SZ(child[y])) swap(x,y);
for (auto& u : child[y]) {
assert(pa[u] == y);
pa[u] = x;
ST->update(KT->pre[u],y,x);
child[x].insert(u);
}
child[y].clear();
return true;
} return false;
}
} *UF;
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 = SZ(X), Q = SZ(S);
FOR(i,0,M-1){
edge[i] = (Edge){ X[i], Y[i], min(X[i],Y[i]) };
}
FOR(i,0,Q-1){
query[i] = (Query){ S[i], E[i], L[i], R[i], i };
}
sort(edge,edge+M,[](Edge a, Edge b){
if (a.W == b.W) return (a.X == b.X ? a.Y < b.Y : a.X < b.X);
return a.W > b.W;
});
sort(query,query+Q,[](Query a, Query b){
if (a.R == b.R) return a.id < b.id;
return a.R < b.R;
});
KT = new KruskalTree(N);
FOR(i,0,M-1){
KT->unions(edge[i].X,edge[i].Y,edge[i].W);
}
KT->init();
FOR(i,0,M-1) edge[i].W = max(edge[i].X,edge[i].Y);
sort(edge,edge+M,[](Edge a, Edge b){
if (a.W == b.W) return (a.X == b.X ? a.Y < b.Y : a.X < b.X);
return a.W < b.W;
});
ST = new SegmentTree(2*N);
UF = new UnionFind(N);
vector<int> ans(Q);
int ei = 0;
FOR(i,0,Q-1){
while (ei < M && edge[ei].W <= query[i].R) {
UF->unions(edge[ei].X,edge[ei].Y);
++ei;
}
int ep = UF->finds(query[i].E);
int sp = KT->findFaGE(query[i].S,query[i].L);
//TRACE(ep _ sp);
ans[query[i].id] = ST->query(KT->pre[sp],KT->pst[sp],ep);
}
return ans;
}
