#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;
int n, m, q;
vector<int>g[maxn];
vector<pair<int, int> > queries[maxn];
int result[maxn];
class dsu {
public:
int usize[maxn], uparent[maxn], parent[maxn];
vector<int>tree_g[maxn];
int sparse[maxn][20], euler[maxn], intime[maxn];
int sbtsize[maxn];
int br;
void init() {
br = 1;
for(int i=0;i<=n;i++) {
usize[i] = 1;
uparent[i] = i;
parent[i] = i;
}
memset(sparse,-1,sizeof(sparse));
}
int ufind(int x) {
while(x != uparent[x]) x = uparent[x];
return x;
}
void add_edge(int i, int j) {
tree_g[i].pb(j);
tree_g[j].pb(i);
}
void unite(int x, int y, int d) {
x = ufind(x);
y = ufind(y);
if(x == y) return;
add_edge(parent[x], parent[y]);
//cout<<"Mering "<<x<<" "<<y<<" -> "<<parent[y]<<"\n";
if(usize[x] > usize[y]) {
uparent[y] = x;
parent[x] = d;
usize[x] += usize[y];
}
else {
uparent[x] = y;
parent[y] = d;
usize[y] += usize[x];
}
}
void dfs(int node, int p = -1) {
//cout<<node<<"\n";
sparse[node][0] = p;
for(int i=1;i<20;i++) {
if(sparse[node][i-1] != -1) {
sparse[node][i] = sparse[sparse[node][i-1]][i-1];
}
}
euler[br] = node;
intime[node] = br;
br++;
sbtsize[node] = 1;
for(int i:tree_g[node]) {
if(i != p) {
dfs(i, node);
sbtsize[node] += sbtsize[i];
}
}
}
}x, y;
int tree[4*maxn];
void update(int x, int val, int li = 0, int ri = n, int index=1) {
if(li == ri) tree[index] += val;
else {
int mid = (li + ri) / 2;
if(x <= mid) update(x, val, li, mid, 2*index);
else update(x, val, mid+1, ri, 2*index+1);
tree[index] = tree[2*index] + tree[2*index+1];
}
}
int query(int ql, int qr, int li=0, int ri = n, int index = 1) {
if(li > qr || ri < ql) return 0;
else if(li >= ql && ri <= qr) return tree[index];
else {
int mid = (li + ri) / 2;
return query(ql, qr, li, mid, 2*index) + query(ql, qr, mid+1, ri, 2*index+1);
}
}
void dfs_x(int node = n - 1, int parent = -1, bool keep = true) {
int big_size = -1;
int big_ind = -1;
for(int i:x.tree_g[node]) {
if(i != parent) {
if(x.sbtsize[i] > big_size) {
big_size = x.sbtsize[i];
big_ind = i;
}
}
}
for(int i:x.tree_g[node]) {
if(i != parent && i != big_ind) {
dfs_x(i, node, false);
}
}
if(big_ind != -1) {
dfs_x(big_ind, node, true);
}
for(int i:x.tree_g[node]){
if(i == parent || i == big_ind) continue;
for(int j=x.intime[i];j<x.intime[i] + x.sbtsize[i];j++) {
update(y.intime[x.euler[j]], 1);
}
}
update(y.intime[node], 1);
for(auto i:queries[node]) {
//cout<<"Find intersection between "<<node<<" and "<<i.first<<"\n";
result[i.second] = query(y.intime[i.first], y.intime[i.first] + y.sbtsize[i.first] - 1);
}
if(!keep) {
for(int i=x.intime[node];i<x.intime[node] + x.sbtsize[node];i++) {
update(y.intime[x.euler[i]], -1);
}
}
}
void precalculate(vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
x.init();
for(int i=0;i<n;i++) {
for(int j:g[i]) {
if(i > j) {
x.unite(i, j, x.parent[x.ufind(i)]);
}
}
}
y.init();
for(int i=n-1;i>=0;i--) {
for(int j:g[i]) {
if(i < j) {
y.unite(i, j, y.parent[y.ufind(i)]);
}
}
}
x.dfs(n-1);
//cout<<"--->\n";
y.dfs(0);
//cout<<"Done printing trees\n";
for(int i=0;i<q;i++) {
int curr = S[i];
for(int j=19;j>=0;j--) {
if(y.sparse[curr][j] >= L[i]) curr = y.sparse[curr][j];
}
//cout<<"Query: "<<i<<"\n";
//cout<<S[i]<<" - "<<curr<<"\n";
int curr_2 = E[i];
for(int j=19;j>=0;j--) {
//cout<<j<<": "<<curr_2<<", "<<x.sparse[curr_2][j]<<"\n";
if(x.sparse[curr_2][j] <= R[i] && x.sparse[curr_2][j] != -1) curr_2 = x.sparse[curr_2][j];
}
//cout<<E[i]<<" - "<<curr_2<<"\n";
queries[curr_2].pb(mp(curr, i));
}
dfs_x();
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N;
m = X.size();
q = S.size();
for(int i=0;i<m;i++) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
precalculate(S,E,L,R);
vector<int>v(q, 0);
for(int i=0;i<q;i++) {
v[i] = result[i];
if(v[i] > 0) v[i] = 1;
}
return v;
}
