#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int nax = 2e5 + 10;
vector<int>a[nax], b[nax];
bool vis[nax];
vector<int>stk;
void dfs(int v) {
vis[v] = 1;
stk.push_back(v);
for(int u : a[v]) if(!vis[u]) {
dfs(u);
}
}
vector<int>ord;
template<const int type> struct SparseTable {
int sp[nax][18];
int N;
int F(int a, int b) {
if(type==1) return max(a, b);
else return min(a, b);
}
void build(vector<int>init) {
N = init.size();
for(int i=0; i<N; ++i) {
sp[i][0] = init[i];
}
for(int j=1; j<18; ++j) {
for(int i=0; i+(1<<(j-1))-1<N; ++i) {
sp[i][j] = F(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
}
}
}
pair<int,int>get(int pos, int lim) {
int l = pos, r = pos;
for(int j=17; j>=0; --j) {
int new_pos = l - (1<<j);
if(new_pos<0) continue;
if(sp[new_pos][j]<lim && type==2) continue;
if(sp[new_pos][j]>lim && type==1) continue;
l = new_pos;
}
for(int j=17; j>=0; --j) {
int new_pos = r + (1<<j);
if(new_pos>=N) continue;
if(sp[r][j]<lim && type==2) continue;
if(sp[r][j]>lim && type==1) continue;
// if(type==1) {
// cerr<<r<<' '<<new_pos<<'\n';
// }
r = new_pos;
}
if(sp[l][0]<lim && type==2) ++l;
else if(sp[l][0]>lim && type==1) ++l;
if(sp[r][0]<lim && type==2) --r;
else if(sp[r][0]>lim && type==1) --r;
return make_pair(l, r);
}
};
SparseTable<1>big;
SparseTable<2>small;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int q = S.size();
int m = X.size();
vector<int>ans(q);
for(int i=0; i<m; ++i) {
a[X[i]].push_back(Y[i]);
a[Y[i]].push_back(X[i]);
}
memset(vis, 0, sizeof vis);
for(int i=0; i<N; ++i) if(a[i].size()==1) {
dfs(i);
ord = stk;
break;
}
//for(int x : ord) cerr<<x<<' '; cerr<<'\n';
vector<int>invord(N);
for(int i=0; i<N; ++i) {
invord[ord[i]] = i;
}
big.build(ord), small.build(ord);
for(int i=0; i<q; ++i) {
auto [l1, r1] = small.get(invord[S[i]], L[i]);
auto [l2, r2] = big.get(invord[E[i]], R[i]);
//cerr<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<'\n';
if(l1>=l2 && l1<=r2) ans[i] = 1;
else if(l2>=l1 && l2<=r1) ans[i] = 1;
}
return ans;
}
