#include "werewolf.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(b);i>=(a);--i)
#define siz(x) ((ll)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
using namespace std; using ll = long long; using vi = vector<ll>; using ii = pair<ll,ll>;
const int N = 2e5 + 3;
int n, m, q;
vector<int> adj[N];
struct KRT {
int p[2*N], t;
vector<int> C[2*N];
int find(int x) {
if(x == p[x]) return x;
return p[x] = find(p[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
p[x] = p[y] = ++t;
C[t].pb(x), C[t].pb(y);
}
int L[2*N], R[2*N];
void dfs(int s) {
L[s] = ++t;
for(int u: C[s]) dfs(u);
R[s] = t;
}
void init(int n) {
iota(p, p+2*N, 0); t = n-1;
}
void construct(int n) {
t = 0;
dfs(2*n-2);
}
};
template<const int N>
struct SegTree {
int t[2*N]{};
void update(int k, int x) {
for(k+=N; k>=1; k/=2) t[k] = max(t[k], x);
}
int query(int l, int r) {
int res=0;
for(l+=N, r+=N; l<=r; ++l/=2, --r/=2) {
if(l&1) res=max(res, t[l]);
if(~r&1) res=max(res, t[r]);
}
return res;
}
};
SegTree<2*N> SEG;
KRT GL, GR;
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 = siz(X), q = siz(S);
for(int i=0; i<m; ++i) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
GL.init(n), GR.init(n);
vector<int> cs[N], ce[N];
for(int i=0; i<q; ++i) {
cs[L[i]].pb(i);
ce[R[i]].pb(i);
}
for(int l=n-1; l>=0; --l) {
for(int u: adj[l]) {
if(u>l) GL.merge(u, l);
}
for(int i: cs[l]) {
S[i] = GL.find(S[i]);
}
}
for(int r=0; r<n; ++r) {
for(int u: adj[r]) {
if(u<r) GR.merge(u, r);
}
for(int i: ce[r]) {
E[i] = GR.find(E[i]);
}
}
GL.construct(n);
GR.construct(n);
vector<int> ys[2*N], qs[2*N];
for(int i=0; i<n; ++i) {
int x = GL.L[i], y = GR.L[i];
ys[x].pb(y);
}
for(int i=0; i<q; ++i) {
int x = GL.R[S[i]];
qs[x].pb(i);
}
vector<int> ans(q);
for(int x=0; x<2*n; ++x) {
for(int y: ys[x]) {
SEG.update(y, x);
}
for(int i: qs[x]) {
int ymin = GR.L[E[i]];
int ymax = GR.R[E[i]];
int xmin = GL.L[S[i]];
// fprintf(stderr, "[%d,%d] x [%d,%d]\n", xmin, x, ymin, ymax);
if (SEG.query(ymin, ymax) >= xmin) {
ans[i] = 1;
}
}
}
return ans;
}
