#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
vector <vector <int> > g, g1, g2;
int dsu[2][N], fenw[N], n;
int tin[2][N], tout[2][N], tiktak, up[2][20][N], pos[N];
int dsu_get(int pr, int v){
if (v == dsu[pr][v])
return v;
return dsu[pr][v] = dsu_get(pr, dsu[pr][v]);
}
void upd(int v){
for (int i = v; i <= n; i += (i & (-i))){
++fenw[i];
}
}
int get(int v){
int ans = 0;
for (int i = v; i >= 1; i -= (i & (-i))){
ans += fenw[i];
}
return ans;
}
void dfs(vector <vector <int> > &g, int cur, int v, int p){
tin[cur][v] = ++tiktak;
up[cur][0][v] = p;
for (int i = 1; i < 20; i++){
up[cur][i][v] = up[cur][i-1][up[cur][i-1][v]];
}
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i];
dfs(g, cur, to, v);
}
tout[cur][v] = tiktak;
}
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;
g.resize(n);
g1.resize(n);
g2.resize(n);
for (int i = 0; i <= n; i++){
dsu[0][i] = dsu[1][i] = i;
fenw[i] = 0;
}
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < X.size(); i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int i = n-1; i >= 0; i--){
for (int j = 0; j < g[i].size(); j++){
int to = g[i][j];
if (to < i)
continue;
int a = dsu_get(0, i);
int b = dsu_get(0, to);
if (a == b)
continue;
dsu[0][b] = a;
g1[a].push_back(b);
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < g[i].size(); j++){
int to = g[i][j];
if (i < to)
continue;
int a = dsu_get(1, i);
int b = dsu_get(1, to);
if (a == b)
continue;
dsu[1][b] = a;
g2[a].push_back(b);
}
}
tiktak = 0;
dfs(g1, 0, dsu_get(0, 0), dsu_get(0, 0));
tiktak = 0;
dfs(g2, 1, dsu_get(1, 0), dsu_get(1, 0));
vector <pair<int, pair<int, int> > > zapr;
for (int i = 0; i < Q; i++){
int s = S[i], e = E[i], l = L[i], r = R[i];
for (int i = 19; i >= 0; i--){
if (up[0][i][s] >= l)
s = up[0][i][s];
if (up[1][i][e] <= r)
e = up[1][i][e];
}
zapr.push_back({tin[0][s]-1, {-(i+1), e} });
zapr.push_back({tout[0][s], {(i+1), e}});
}
for (int i = 0; i < n; i++){
pos[tin[0][i]-1] = tin[1][i];
}
sort(zapr.begin(), zapr.end());
int ptr = 0;
for (int i = 0; i < zapr.size(); i++){
int tim = zapr[i].first, id = zapr[i].second.first, v = zapr[i].second.second;
while(ptr < tim){
upd(pos[ptr]);
++ptr;
}
if (id < 0)
A[abs(id)-1] -= (get(tout[1][v])-get(tin[1][v]-1)); else
A[abs(id)-1] += (get(tout[1][v])-get(tin[1][v]-1));
}
for (int i = 0; i < Q; i++){
A[i] = (A[i] > 0);
}
return A;
}
