#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int p[2][200005][20];
int tp[2][200005];
int d[2][200005][20];
vector<int> adj[200005];
vector<int> child[2][200005];
int n ;
int find(int i, int id){
if(i == tp[id][i]){
return i;
}
return tp[id][i] = find(tp[id][i], id);
}
void build(int i, int id){
for(int x : adj[i]){
if((id == 0) ^ (x > i) == 1){
x = find(x, id);
if(x == i) continue;
p[id][x][0] = i;
tp[id][x] = i;
}
}
}
int cnt = 0;
int l[2][200005], r[2][200005];
int arr[2][200005];
void dfs(int v, int id){
if((id == 1 && v == 0) || (id == 0 && v == n - 1)){
} else {
d[id][v][0] = id == 0 ? max(v, p[id][v][0]) : min(v, p[id][v][0]);
for(int j = 1; j < 20; j++){
if(p[id][v][j - 1] == -1) break;
p[id][v][j] = p[id][p[id][v][j - 1]][j - 1];
d[id][v][j] = id == 0 ? max(d[id][v][j - 1], d[id][p[id][v][j - 1]][j - 1]) : min(d[id][v][j - 1], d[id][p[id][v][j - 1]][j - 1]);
}
}
l[id][v] = ++cnt;
arr[id][cnt] = v;
for(int x :child[id][v]){
dfs(x, id);
}
r[id][v] = cnt;
}
bool answer(int s, int e, int L, int R){
for(int i = 19; i >= 0; i--){
if(p[1][s][i] != -1 && d[1][s][i] >= L)
s = p[1][s][i];
if(p[0][e][i] != -1 && d[0][e][i] <= R)
e = p[0][e][i];
}
for(int i = l[1][s]; i <= r[1][s]; i++){
for(int j = l[0][e]; j <= r[0][e]; j++){
if(arr[1][i] == arr[0][j]) return 1;
}
}
return 0;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
memset(p, -1, sizeof p);
for(int i = 0; i < N; i++){
tp[0][i] = tp[1][i] = i;
}
n = N;
for(int i = X.size() - 1; i >= 0; i--){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; i++)
build(i, 0);
for(int i = N - 1; i >= 0; i--)
build(i, 1);
for(int i = 1; i < N; i++)
child[1][p[1][i][0]].push_back(i);
for(int i = N - 2; i >= 0; i--)
child[0][p[0][i][0]].push_back(i);
cnt = 0; dfs(0, 1);
cnt = 0; dfs(N - 1, 0);
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = answer(S[i], E[i], L[i], R[i]);
}
return A;
}
