#include <bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,q,par[N],sz[N],l[N],st[N],en[N],now[N],nsz[N];
vector<int>adj[N],g[N],event[N];
set<int>node[N];
int Find(int u)
{
if(par[u]==u) return u;
return par[u]=Find(par[u]);
}
void Union(int u,int v,bool type)
{
u=Find(u);
v=Find(v);
if(u==v) return;
if(sz[u]<sz[v]) swap(u,v);
if(!type) g[u].push_back(v);
else for(auto&it:node[v]) node[u].insert(it);
par[v]=u;
sz[u]+=sz[v];
}
void dfs(int u)
{
static int nTime=0;
l[u]=++nTime;
for(auto &v:g[u]) dfs(v);
}
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();
vector<int>res(q,0);
iota(par,par+n,0);
fill(sz,sz+n,1);
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<q;i++) event[L[i]].push_back(i);
for(int i=n-1;i>=0;i--)
{
for(auto&e:adj[i]) if(e>i) Union(e,i,0);
for(auto&id:event[i])
{
int u=Find(S[id]);
now[id]=u;
nsz[id]=sz[u];
}
event[i].clear();
}
for(int i=0;i<n;i++)
{
if(par[i]==i)
{
dfs(i);
break;
}
}
for(int i=0;i<q;i++)
{
st[i]=l[now[i]];
en[i]=l[now[i]]+nsz[i]-1;
event[R[i]].push_back(i);
}
for(int i=0;i<n;i++) node[i].insert(l[i]);
iota(par,par+n,0);
fill(sz,sz+n,1);
for(int i=0;i<n;i++)
{
for(auto&j:adj[i]) if(j<i) Union(i,j,1);
for(auto&id:event[i])
{
int u=Find(E[id]);
auto it=node[u].lower_bound(st[id]);
if(it!=node[u].end()&&*(it)<=en[id]) res[id]=1;
}
}
return res;
}
