#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define task "sus"
const int MN = 2e5+5,LG = 19;
int n,m,q,fw[MN];
vector<int> adj[MN];
struct query
{
int l,r,sign,id;
};
vector<query> ev[MN];
void upd(int u,int val)
{
for(int x=u; x<MN; x+=x&(-x)) fw[x] += val;
}
int get(int u)
{
int res = 0;
for(int x=u; x; x-=x&(-x)) res += fw[x];
return res;
}
struct KRT
{
int pa[MN][LG],dsu[MN],h[MN],time_dfs,in[MN],out[MN],et[MN];
vector<int> g[MN];
void init()
{
for(int i=0; i<=n; i++) {
for(int j=0; j<LG; j++) pa[i][j] = 0;
dsu[i] = i;
h[i] = 0;
}
}
int papa(int x)
{
if(x==dsu[x]) return x;
return dsu[x] = papa(dsu[x]);
}
void uni_set(int x,int y)
{
int p = papa(y);
dsu[p] = x;
g[x+1].push_back(p+1);
}
void dfs(int x,int p)
{
in[x] = ++time_dfs;
et[time_dfs] = x;
pa[x][0] = p;
h[x] = h[p] + 1;
for(int i=1; i<LG; i++) pa[x][i] = pa[pa[x][i-1]][i-1];
for(auto v:g[x]) dfs(v,x);
out[x] = time_dfs;
}
}a,b;
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 = X.size(), q = S.size();
a.init(); b.init();
for(int i=0; i<m; i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i=0; i<n; i++){
for(auto j:adj[i]){
if(j>i or a.papa(j)==i) continue;
a.uni_set(i,j);
}
}
for(int i=n-1; i>=0; i--){
for(auto j:adj[i]){
if(j<i or b.papa(j)==i) continue;
b.uni_set(i,j);
}
}
a.dfs(n,0); b.dfs(1,0);
//cerr << "TOUR A: "; for(int i=1; i<=n; i++) cerr << a.et[i] << ' '; cerr << endl;
//cerr << "TOUR B: "; for(int i=1; i<=n; i++) cerr << b.et[i] << ' '; cerr << endl;
vector<int> ans;
ans.resize(q,0);
for(int t=0; t<q; t++){
int s,e,l,r;
s = S[t]+1, e = E[t]+1, l = L[t]+1, r = R[t]+1;
//cerr << "PRE: " << s << ' ' << e << ' ' << l << ' ' << r << endl;
for(int i=LG-1; i>=0; i--){
//cerr << "LG: " << i << ' ' << s << ' ' << e << endl;
if(b.pa[s][i]>=l) s = b.pa[s][i];
if(a.pa[e][i]<=r and a.pa[e][i]!=0) e = a.pa[e][i];
}
//cerr << "POST: " << s << ' ' << e << ' ' << l << ' ' << r << endl;
ev[max(b.in[s]-1,0)].push_back({a.in[e],a.out[e],-1,t});
ev[b.out[s]].push_back({a.in[e],a.out[e],1,t});
}
for(int i=1; i<=n; i++){
int u = b.et[i];
upd(a.in[u],1);
for(auto q:ev[i]){
int res = get(q.r) - get(q.l-1);
ans[q.id] += res * q.sign;
}
}
for(int i=0; i<q; i++) ans[i] = (ans[i]>0);
return ans;
}
