#include "werewolf.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 2e5 + 10;
int n, m, q;
vector<int> V[N], G[N];
int par[N];
int pos[N];
void Merge(int u, int v){
u = par[u]; v = par[v];
if(u == v) return ;
if(V[u].size() > V[v].size()) swap(u, v);
for(auto x : V[u]){
pos[x] = V[v].size();
par[x] = v;
V[v].pb(x);
}
V[u].clear();
}
vector<pii> Q[2][N];
pii res[2][N];
vi arr[2];
void DSU(vi ord, int z){
fill(pos, pos + n, 0);
iota(par, par + n, 0);
for(int i = 0; i < n; i++) V[i] = {i};
vector<int> mk(n, 0);
for(auto u : ord){
mk[u] = 1;
for(auto adj : G[u])
if(mk[adj])
Merge(adj, u);
for(auto [id, v] : Q[z][u]){
res[z][id] = {-pos[v], -pos[v] + ((int) V[par[v]].size())};
}
}
for(auto u : ord)
for(auto [id, v] : Q[z][u])
res[z][id].F += pos[v], res[z][id].S += pos[v];
arr[z] = V[par[0]];
}
typedef array<int, 3> que; // pos fac q_id
int sum[N];
vector<que> tsk[N];
int fen[N];
void AF(int idx, int x){
for(; idx < N; idx += idx & (-idx))
fen[idx] += x;
}
int GF(int idx){
int sm = 0;
for(; idx; idx -= idx & (-idx))
sm += fen[idx];
return sm;
}
void Solve(){
for(int i = 0; i < n; i++){
// cerr << "! " << pos[arr[0][i]] << '\n';
AF(pos[ arr[0][i] ] + 1, +1);
for(auto [ps, fac, q_id] : tsk[i + 1]){
sum[q_id] += fac * GF(ps);
}
}
}
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 < q; i++){
Q[0][R[i]].pb({i, E[i]});
Q[1][L[i]].pb({i, S[i]});
}
for(int i = 0; i < m; i++) G[X[i]].pb(Y[i]), G[Y[i]].pb(X[i]);
vector<int> ord(n, 0); iota(all(ord), 0);
DSU(ord, 0);
reverse(all(ord));
DSU(ord, 1);
// for(int i = 0; i < 2; i++){
// cerr << "! ";
// for(auto x : arr[i]) cerr << x << ' ';
// cerr << '\n';
// }
for(int i = 0; i < q; i++){
auto [l0, r0] = res[0][i];
auto [l1, r1] = res[1][i];
tsk[r0].pb({r1, +1, i});
tsk[r0].pb({l1, -1, i});
tsk[l0].pb({r1, -1, i});
tsk[l0].pb({l1, +1, i});
// cerr << "? [" << l0 << ", " << r0 << ") & [" << l1 << ' ' << r1 << ")\n";
// break;
}
Solve();
vector<int> ans;
for(int i = 0; i < q; i++)
ans.pb(sum[i] ? 1 : 0);
return ans;
}
