#include "werewolf.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define vvii vector<vii>
#define x first
#define y second
#define all(a) a.begin(),a.end()
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;
struct DSU{
int n;
vi p, sz;
DSU(int n=0): n(n), p(n,-1), sz(n,1){}
void init(int nn){
n = nn;
p.clear(); sz.clear();
p.resize(n,-1); sz.resize(n,1);
}
int find(int c){
if (p[c]==-1) return c;
return p[c] = find(p[c]);
}
bool uni(int a, int b){
a = find(a), b = find(b);
if (a==b) return 0;
//if (sz[a]>sz[b]) swap(a,b);
p[a] = b;
sz[b] += sz[a];
return 1;
}
};
const int INF = 1e9;
struct BINARY{
int n, log;
vvii g;
vvi anc, mine;
vi order, pos;
vi in, out;
int t = 0;
BINARY(vvii& _g, int s=0): g(_g), n(_g.size()){
for(log=1; (1<<log)<n;log++);
anc.resize(n, vi(log, -1));
mine.resize(n, vi(log, -INF));
in.resize(n); out.resize(n);
dfs(s);
pos.resize(n);
loop(i,0,n) pos[order[i]] = i;
}
void dfs(int cur, int p=-1, int pw=-INF){
order.pb(cur); in[cur] = t++;
anc[cur][0] = p; mine[cur][0] = pw;
loop(i,1,log){
if (anc[cur][i-1]==-1) break;
anc[cur][i] = anc[anc[cur][i-1]][i-1];
mine[cur][i] = min(mine[cur][i-1], mine[anc[cur][i-1]][i-1]);
}
for(auto nei:g[cur]) if(nei.x!=p){
dfs(nei.x, cur, nei.y);
}
out[cur] = t-1;
}
int lift(int cur, int L){
loopr(i,0,log){
if (mine[cur][i]>=L){
cur = anc[cur][i];
}
}
return cur;
}
};
struct Qur{
int x, l, r;
int ind; bool in;
bool operator<(const Qur& a){
return x < a.x;
}
};
struct SEG{
int sz;
vi a;
SEG(int n){
for(sz=1;sz<n;sz*=2);
a.resize(2*sz);
}
void update(int i, int x){
a[i+=sz]=x;
for(i/=2;i;i/=2) a[i] = a[2*i] + a[2*i+1];
}
int query(int l, int r){
int ans = 0;
for(l+=sz, r+=sz; l<=r; l/=2, r/=2){
if (l%2) ans+=a[l++];
if (r%2==0) ans+=a[r--];
}
return ans;
}
};
vi check_validity(int N, vi u, vi v, vi S, vi E, vi L, vi R) {
int n = N, m = u.size(), q=S.size();
vvi g(n);
loop(i,0,m){
int a = u[i], b = v[i];
g[a].pb(b);
g[b].pb(a);
}
vector<ii> mine, maxe;
DSU dsu(n);
loopr(i,0,n){
for(auto j:g[i]){
if (j<i) continue;
int x = dsu.find(j);
if (x!=i){
mine.pb({x,i});
dsu.p[x] = i;
}
}
}
dsu.init(n);
loop(i,0,n){
for(auto j:g[i]){
if (j>i) continue;
int x = dsu.find(j);
if (x!=i){
maxe.pb({x,i});
dsu.p[x] = i;
}
}
}
vvii gs(n), ge(n);
for(auto e:mine){
gs[e.x].pb({e.y, min(e.x, e.y)});
gs[e.y].pb({e.x, min(e.x, e.y)});
}
for(auto e:maxe){
//cout<<e.x<<" "<<e.y<<endl;
ge[e.x].pb({e.y, -max(e.x, e.y)});
ge[e.y].pb({e.x, -max(e.x, e.y)});
}
BINARY bins(gs, 0), bine(ge, n-1);
//loop(i,0,n) cout<<bine.order[i]<<" "; cout<<endl;
vector<Qur> eve;
loop(i,0,q){
int a = bins.lift(S[i], L[i]), b = bine.lift(E[i], -R[i]);
eve.pb({bins.in[a]-1, bine.in[b], bine.out[b], i, 1});
eve.pb({bins.out[a], bine.in[b], bine.out[b], i, 0});
//cout<<"AB: "<<a<<" "<<b<<endl;
//cout<<bine.in[b]<< " " << bine.out[b] << endl;
//cout<<bins.in[a]<< " " << bins.out[a] << endl;
}
sort(all(eve));
SEG seg(n);
vi ans(q); int ind = 0;
for(auto &e:eve){
while(ind<=e.x){
seg.update(bine.pos[bins.order[ind]], 1);
ind++;
}
int v = seg.query(e.l, e.r);
//cout<<"V: "<<v<<endl;
ans[e.ind]+=(e.in?-v:v);
}
loop(i,0,q) if(ans[i]>0) ans[i]=1;
return ans;
}
/*
clear
g++ werewolf.cpp grader.cpp -o a ; ./a
10 9 1
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
8 9 3 9
*/
