#include "werewolf.h"
#include <bits/stdc++.h>
#include <random>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 3e5+10;
const int LOG = 19;
const ll INF = 6e18+10;
int n, q;
int ans[MAXN], a[MAXN], idx[MAXN];
vector <int> adj[MAXN];
int st[MAXN][LOG+5], st2[MAXN][LOG+5];
void dfs(int nw, int par, int dep){
// cout << nw << ' ' << par << " nw\n";
a[dep] = nw;
idx[nw] = dep;
for(auto nx : adj[nw]){
if(nx == par) continue;
dfs(nx, nw, dep+1);
}
}
int MN(int x, int y){
int lg = log2(y-x+1);
return min(st[x][lg], st[y-(1<<lg)+1][lg]);
}
int MX(int x, int y){
int lg = log2(y-x+1);
return max(st2[x][lg], st2[y-(1<<lg)+1][lg]);
}
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; q = S.size();
for(int i=0; i<X.size(); i++){
adj[X[i]+1].pb(Y[i]+1);
adj[Y[i]+1].pb(X[i]+1);
}
for(int i=1; i<=n; i++){
if(adj[i].size() == 1){
dfs(i, -1, 1); break;
}
}
for(int i=1; i<=n; i++){
st[i][0] = a[i]; st2[i][0] = a[i];
}
for(int i=1; i<LOG; i++){
for(int j=1; j<=n; j++){
if((j+(1<<(i-1))) > n) st[j][i] = st[j][i-1];
else st[j][i] = min(st[j][i-1], st[j+(1<<(i-1))][i-1]);
if((j+(1<<(i-1))) > n) st2[j][i] = st2[j][i-1];
else st2[j][i] = max(st2[j][i-1], st2[j+(1<<(i-1))][i-1]);
}
}
// for(int i=1; i<=n; i++) cout << a[i] << " \n"[i==n];
// cout << " arr\n";
// cout << MN(1, 5) << ' ' << MX(1, 5) << " mx\n";
for(int i=0; i<q; i++){
int sta = S[i]+1, en = E[i]+1, le = L[i]+1, ri = R[i]+1;
if(idx[sta] <= idx[en]){
// cout << idx[sta] << ' ' << idx[en] << " sa\n";
int l=idx[sta], r=idx[en], mid=0, cnt=-1;
while(l<=r){
mid = md;
if(MN(idx[sta], mid) >= le){ // masi valid
l = mid+1; cnt = mid;
} else r = mid-1;
}
l=idx[sta]; r=idx[en]; mid=0; int cnt2=-1;
while(l<=r){
mid = md;
if(MX(mid, idx[en]) <= ri){ // masi valid
r = mid-1; cnt2 = mid;
} else l = mid+1;
}
// cout << cnt << ' ' << cnt2 << " cntpp\n";
if(cnt==-1 || cnt2==-1 || cnt<cnt2) ans[i] = 0;
else ans[i] = 1;
} else {
int l=idx[en], r=idx[sta], mid=0, cnt=-1;
while(l<=r){
mid = md;
if(MN(mid, idx[sta]) >= le){ // masi valid
r = mid-1; cnt = mid;
} else l = mid+1;
}
l=idx[en]; r=idx[sta]; mid=0; int cnt2=-1;
while(l<=r){
mid = md;
if(MX(idx[en], mid) <= ri){ // masi valid
l = mid+1; cnt2 = mid;
} else r = mid-1;
}
// cout << cnt << ' ' << cnt2 << " cnt\n";
if(cnt==-1 || cnt2==-1 || cnt>cnt2) ans[i] = 0;
else ans[i] = 1;
}
}
vector<int> ANS(q);
for(int i = 0; i < q; ++i) ANS[i] = ans[i];
return ANS;
}
