#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int N = 2e5+10;
int n, m, q;
int st[2][N], ft[2][N], p[2][18][N], posIn1[N];
vi UU[N], DD[N], t[2][N], eul[2];
int dsu[N];
void init() {
for(int i = 0; i < n; i++)
dsu[i] = i;
}
int find(int x) {
if(dsu[x] == x) return x;
return dsu[x] = find(dsu[x]);
}
void dfs(int u, int id) {
st[id][u] = eul[id].size();
eul[id].push_back(u);
for(int v : t[id][u])
dfs(v, id);
ft[id][u] = eul[id].size()-1;
}
struct EpicDataStructureToSolveThisProblem{
struct event{
int x, y1, y2, type, QID;
// type 0 = [, type 1 = point, type 2 = ]
bool operator<(event o) const {
if(x != o.x) return x < o.x;
return type < o.type;
}
};
vector<event> e;
int ans[N], bit[N];
void upd(int pos, int x) { while(pos < N) bit[pos] += x, pos += pos&-pos; }
int get(int pos, int ret = 0) { while(pos > 0) ret += bit[pos], pos -= pos&-pos; return ret; }
int rng(int l, int r) { return get(r) - get(l-1); }
void add_point(int x, int y) { x++, y++; e.push_back({x, y, -1, 1, -1}); }
void add_query(int x1, int x2, int y1, int y2, int id) {
x1++, y1++, x2++, y2++;
e.push_back({x1, y1, y2, 0, id});
e.push_back({x2, y1, y2, 2, id});
}
void LineSweep() {
sort(e.begin(),e.end());
for(auto it : e) {
if(it.type == 0) ans[it.QID] = -rng(it.y1, it.y2);
else if(it.type == 1) upd(it.y1, +1);
else ans[it.QID] += rng(it.y1, it.y2);
}
}
}ds;
vi ans;
vi check_validity(int _n, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = _n;
m = X.size();
q = S.size();
for(int i = 0; i < m; i++) {
if(X[i] > Y[i]) swap(X[i], Y[i]);
UU[X[i]].push_back(Y[i]);
DD[Y[i]].push_back(X[i]);
}
memset(p,-1,sizeof p);
init();
for(int i = 0; i < n; i++) {
for(int v : DD[i]) {
int par = find(v);
if(par == i) continue;
t[1][i].push_back(par);
p[1][0][par] = i;
dsu[par] = i;
}
}
init();
for(int i = n-1; i >= 0; i--) {
for(int v : UU[i]) {
int par = find(v);
if(par == i) continue;
t[0][i].push_back(par);
p[0][0][par] = i;
dsu[par] = i;
}
}
dfs(0,0);
dfs(n-1,1);
for(int i = 0; i < n; i++)
posIn1[eul[1][i]] = i;
for(int i = 0; i < n; i++)
ds.add_point(i, posIn1[eul[0][i]]);
for(int id : {0,1})
for(int j = 1; j < 18; j++)
for(int i = 0; i < n; i++)
if(p[id][j-1][i] != -1)
p[id][j][i] = p[id][j-1][p[id][j-1][i]];
for(int Q = 0; Q < q; Q++) {
int U = S[Q], V = E[Q];
for(int j = 17; j >= 0; j--) {
if(p[0][j][U] != -1 && L[Q] <= p[0][j][U]) U = p[0][j][U];
if(p[1][j][V] != -1 && p[1][j][V] <= R[Q]) V = p[1][j][V];
}
ds.add_query(st[0][U], ft[0][U], st[1][V], ft[1][V], Q);
}
ds.LineSweep();
for(int i = 0; i < q; i++)
ans.push_back(ds.ans[i] > 0);
return ans;
}
