//#include "combo.h"
//#include "one.h"
//#include "werewolf.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 1e9;
const ll mod2 = 1e9+7;
const ll base=67;
int n,m,s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r,last;
int kk;
int el = 19;
struct ic
{
int a,b,c;
};
struct ib
{
int a, b;
};
struct id
{
int a,b,c,d;
};
int t[1600001], ain[400001], aou[400001], bin[400001], bou[400001], st[19][400001];
vector<int> v[400001],ans;
vector<id> ask[400001];
int cost[400001], pos[400001];
vector<ib>edge;
struct dsuconcu
{
ic dsu[200001];
void reset()
{
for(int i=1; i<=n; i++)
dsu[i]= {1,i,i};
for(int i=1; i<=dem; i++)
v[i].clear();
dem=n;
}
int get(int x)
{
if(x!=dsu[x].b) dsu[x].b=get(dsu[x].b);
return dsu[x].b;
}
void noi(int x,int y,int xx)
{
x=get(x);
y=get(y);
if(x==y) return;
if(dsu[x].a<dsu[y].a)swap(x,y);
dsu[x].a+=dsu[y].a;
dsu[y].b=x;
dem++;
cost[dem]=xx;
/// cout<<x<<" "<<y<<" "<<xx,debug
v[dem].pb(dsu[x].c);
v[dem].pb(dsu[y].c);
dsu[x].c=dem;
}
} dsu;
void upd(int node,int l,int r,int l1,int x)
{
if(l>l1||r<l1) return;
if(l==r)
{
t[node]=x;
return;
}
int mid=l+r>>1;
upd(node<<1,l,mid,l1,x);
upd(node<<1|1,mid+1,r,l1,x);
t[node]=max(t[node<<1],t[node<<1|1]);
}
int get(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1) return 0;
if(l>=l1&&r<=r1){
return t[node];}
int mid=l+r>>1;
return max(get(node << 1, l, mid, l1, r1 ),get(node << 1 | 1,mid + 1, r, l1, r1));
}
void dfs(int x,bool d)
{
if(!d)ain[x]=++dem2,pos[dem2]=x;
else bin[x]=++dem2;
for(auto f:v[x])
{
st[0][f]=x;
dfs(f,d);
}
if(!d)aou[x]=dem2;
else bou[x]=dem2;
}
void build(int xx)
{
dsu.reset();
for(int i=0; i<m; i++)
{
int x=edge[i].a+1;
int y=edge[i].b+1;
if(xx==0)dsu.noi(x,y,max(x,y));
else dsu.noi(x,y,min(x,y));
}
cost[0]=inf;
dfs(dem,xx);
for(int i=1; i<19; i++)
for(int j=1; j<=dem; j++)
st[i][j]=st[i-1][st[i-1][j]];
}
bool cmp(ib a,ib b)
{
return max(a.a,a.b)<max(b.a,b.b);
}
bool cmp2(ib a,ib b)
{
return min(a.a,a.b)>min(b.a,b.b);
}
vector<int> check_validity(int N,vector<int>X,vector<int>Y,vector<int> start,
vector<int> target,vector<int>L,vector<int>R)
{
n=N;
m=X.size();
for(int i=0; i<X.size(); i++)
{
edge.pb({X[i],Y[i]});
}
sort(edge.begin(),edge.end(),cmp);
build(0);
int q=start.size();
ans.resize(q);
for(int i=0; i<q; i++)
{
int x=target[i]+1;
for(int j=18; j>=0; --j)
if(cost[st[j][x]]<=R[i]+1)
x=st[j][x];
target[i]=x;
}
sort(edge.begin(),edge.end(),cmp2);
dem2=0;
build(1);
cost[0]=-inf;
for(int i=0; i<q; i++)
{
int x=start[i]+1;
for(int j=18; j>=0; --j)
if(cost[st[j][x]]>=L[i]+1)
x=st[j][x];
ask[aou[target[i]]].pb({ain[target[i]],bin[x],bou[x],i});
}
for(int i=1; i<=2*n; i++)
{
if(pos[i]<=n)
upd(1,1,2*n,bin[pos[i]],i);
for(auto x:ask[i])
{
s2=get(1,1,n*2,x.b,x.c);
if(s2>=x.a)ans[x.d]=1;
}
}
return ans;
}
/*
int main(){
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int N, M, Q; cin >> N >> M >> Q;
vector <int> X(M), Y(M);
for (int i = 0; i < M; ++ i)
cin >> X[i] >> Y[i];
vector <int> S(Q), E(Q), L(Q), R(Q);
for (int i = 0; i < Q; ++ i)
cin >> S[i] >> E[i] >> L[i] >> R[i];
vector <int> ans = check_validity(N, X, Y, S, E, L, R);
for (int A : ans)
cout << A << "\n";
return 0;
}
*/
