#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;
const int MAXN = 2e5 + 5, MAXQ = 2e5 + 5, MAXLGN = 20;
int UF[2][MAXN], PAR[2][MAXLGN][MAXN], PRE[2][MAXN], POST[2][MAXN], VERT[2][MAXN], BIT[MAXN], ANS[MAXQ], cur;
vector<int> ADJ[MAXN], TR[2][MAXN];
vector<pii> ADD[MAXN], SUB[MAXN];
int find(int i, int v) {
return UF[i][v] < 0 ? v : UF[i][v] = find(i, UF[i][v]);
}
void join(int i, int v, int w) {
v = find(i, v);
w = find(i, w);
if (v == w) return;
UF[i][w] = v;
TR[i][v].pb(w);
PAR[i][0][w] = v;
}
void dfs(int i, int v) {
VERT[i][PRE[i][v] = ++cur] = v;
FORE(w, TR[i][v]) dfs(i, w);
POST[i][v] = cur;
}
void update(int i, int v) {
for (; i < MAXN; i += i & -i) BIT[i] += v;
}
int rsq(int i) {
int ret = 0;
for (; i > 0; i -= i & -i) ret += BIT[i];
return ret;
}
int rsq(int a, int b) {
return rsq(b) - rsq(a - 1);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
FOR(i, sz(X)) {
ADJ[X[i]].pb(Y[i]);
ADJ[Y[i]].pb(X[i]);
}
FOR(i, 2) fill(UF[i], UF[i] + MAXN, -1);
PAR[0][0][0] = 0;
REV(i, N - 1) FORE(j, ADJ[i]) if (i < j) join(0, i, j);
PAR[1][0][N - 1] = N - 1;
FOR(i, N) FORE(j, ADJ[i]) if (i > j) join(1, i, j);
cur = 0;
dfs(0, 0);
cur = 0;
dfs(1, N - 1);
FOR(i, 2) For(j, 1, MAXLGN) FOR(k, N) PAR[i][j][k] = PAR[i][j - 1][PAR[i][j - 1][k]];
FOR(i, sz(S)) {
int s = S[i], e = E[i];
REV(j, MAXLGN - 1) {
if (PAR[0][j][s] >= L[i]) s = PAR[0][j][s];
if (PAR[1][j][e] <= R[i]) e = PAR[1][j][e];
}
ADD[POST[1][e]].eb(s, i);
SUB[PRE[1][e] - 1].eb(s, i);
}
fill(BIT, BIT + MAXN, 0);
fill(ANS, ANS + MAXQ, 0);
For(i, 1, N + 1) {
update(PRE[0][VERT[1][i]], 1);
FORE(q, ADD[i]) ANS[q.s] += rsq(PRE[0][q.f], POST[0][q.f]);
FORE(q, SUB[i]) ANS[q.s] -= rsq(PRE[0][q.f], POST[0][q.f]);
}
vector<int> ret;
FOR(i, sz(S)) ret.pb(ANS[i] > 0);
return ret;
}
