#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
vector<int> g[200005], g2[200005], g3[200005];
int par2[19][200005], par3[19][200005];
int p[200005];
int mapp[200005];
int sz[200005];
int root(int a){
return p[a] == a?a:(p[a]=root(p[a]));
}
void merge(int a, int b, int t){
a = root(a), b = root(b);
if(a != b){
p[a] = b;
if(t == 0) sz[b] = min(sz[b], sz[a]);
else sz[b] = max(sz[b], sz[a]);
}
}
int arr2[200005], arr3[200005], j = 1;
int s2[200005], e2[200005], s3[200005], e3[200005];
void dfs2(int u, int p){
arr2[j++] = u;
par2[0][u] = p;
s2[u] = j-1;
for(int i=0;i<g2[u].size();i++){
int v = g2[u][i];
dfs2(v, u);
}
e2[u] = j-1;
}
void dfs3(int u, int p){
arr3[j++] = u;
par3[0][u] = p;
s3[u] = j-1;
for(int i=0;i<g3[u].size();i++){
int v = g3[u][i];
dfs3(v, u);
}
e3[u] = j-1;
}
set<int> dp[200005];
set<int>::iterator its;
vector<pipii> cur[200005];
vector<int> ans;
void dfs(int u, int p){
dp[u].insert(mapp[u]);
for(int i=0;i<g3[u].size();i++){
int v = g3[u][i];
dfs(v, u);
if(dp[u].size() < dp[v].size()) swap(dp[u], dp[v]);
for(its = dp[v].begin();its != dp[v].end();its++) dp[u].insert(*its);
}
for(int i=0;i<cur[u].size();i++){
int j = cur[u][i].first;
int l = cur[u][i].second.first, r = cur[u][i].second.second;
its = dp[u].lower_bound(l);
if(l <= *its && *its <= r) ans[j] = 1;
else ans[j] = 0;
}
}
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){
int n = N;
int m = X.size();
int q = S.size();
ans.resize(q);
for(int i=0;i<m;i++){
int a, b;
a = X[i]+1, b = Y[i]+1;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=1;i<=n;i++) p[i] = i, sz[i] = i;
for(int i=n;i>=1;i--){
for(int j=0;j<g[i].size();j++){
int v = g[i][j];
if(v >= i){
if(root(i) != root(v)){
int r = root(v);
g2[i].push_back(sz[r]);
}
merge(i, v, 0);
}
}
}
for(int i=1;i<=n;i++) p[i] = i, sz[i] = i;
for(int i=1;i<=n;i++){
for(int j=0;j<g[i].size();j++){
int v = g[i][j];
if(v <= i){
if(root(i) != root(v)){
int r = root(v);
g3[i].push_back(sz[r]);
}
merge(i, v, 1);
}
}
}
j = 1;
dfs2(1, 0); // human
j = 1;
dfs3(n, 0); // wolf
j--;
for(int i=1;i<=n;i++){
mapp[arr2[i]] = i;
}
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++){
if(par2[j-1][i] != 0) par2[j][i] = par2[j-1][par2[j-1][i]];
if(par3[j-1][i] != 0) par3[j][i] = par3[j-1][par3[j-1][i]];
}
}
for(int i=0;i<q;i++){
int s, e, l, r;
s = S[i]+1, e = E[i]+1, l = L[i]+1, r = R[i]+1;
for(int j=18;j>=0;j--){
if(par2[j][s] != 0 && par2[j][s] >= l) s = par2[j][s];
if(par3[j][e] != 0 && par3[j][e] <= r) e = par3[j][e];
}
int ll = s2[s], rr = e2[s];
cur[e].push_back(pipii(i, pii(ll, rr)));
}
dfs(n, 0);
return ans;
}
