#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
const int LOGN = 20;
vector<int> adj[MAXN], ans;
pair<bool, int> dp[MAXN][2];
int to, l, r, idx;
int min_table[MAXN][LOGN], max_table[MAXN][LOGN];
int a[MAXN], ptr[MAXN], n = 0;
bool solve(int u, bool stage){
pair<bool, int> &p = dp[u][stage];
if(p.second == idx){
return p.first;
}
if(u == to){
if(stage || (u >= l && u <= r)){
return true;
}
return false;
}
if(!stage && u < l){
return false;
}
if(stage && u > r){
return false;
}
p.second = idx;
p.first = false;
if(!stage && u <= r){
if(solve(u, true)){
p.first = true;
return true;
}
}
for(int v: adj[u]){
if(solve(v, stage)){
p.first = true;
return true;
}
}
return false;
}
void make_a(int i, int pr = -1){
a[n++] = i;
for(int v: adj[i]){
if(v != pr){
make_a(v, i);
}
}
}
void init_table(){
for(int i = 0; i < n; i++){
min_table[i][0] = a[i];
max_table[i][0] = a[i];
}
for(int j = 1; j < LOGN; j++){
for(int i = 0; i < n; i++){
max_table[i][j] = max(max_table[i][j - 1], max_table[min(n - 1, i + 1 << (j - 1))][j - 1]);
min_table[i][j] = max(min_table[i][j - 1], min_table[min(n - 1, i + 1 << (j - 1))][j - 1]);
}
}
}
int calc_min(int from, int to){
int d = to - from + 1, x = 0;
while((1 << x) < d){
x++;
}
x--;
return min(min_table[from][x], min_table[to - (1 << x) + 1][x]);
}
int calc_max(int from, int to){
int d = to - from + 1, x = 0;
while((1 << x) < d){
x++;
}
x--;
return max(max_table[from][x], max_table[to - (1 << x) + 1][x]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
for(int i = 0; i < X.size(); i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
if(N >= 3000){
for(int i = 1; i <= N; i++){
if(adj[i].size() == 1){
make_a(i);
break;
}
}
init_table();
for(int i = 0; i < n; i++){
ptr[a[i]] = i;
}
for(int i = 0; i < (int)E.size(); i++){
int s = ptr[S[i]], e = ptr[E[i]];
if(s > e){
int bl = s, br = e + 1;
while(bl != br){
int mid = (bl + br) / 2;
if(calc_max(s, mid) > r){
br = mid;
}
else{
bl = mid + 1;
}
}
bl = s;
if(calc_max(bl, br) < l){
ans.push_back(false);
continue;
}
int right_end = br;
while(bl != br){
int mid = (bl + br + 1) / 2;
if(calc_max(mid, right_end) < l){
br = mid - 1;
}
else{
bl = mid;
}
}
if(calc_min(e, bl) < l || calc_max(bl, s) > r){
ans.push_back(false);
}
else{
ans.push_back(true);
}
}
else{
int bl = s, br = e + 1;
while(bl != br){
int mid = (bl + br) / 2;
if(calc_min(s, mid) < l){
br = mid;
}
else{
bl = mid + 1;
}
}
bl = s;
if(calc_min(bl, br) > r){
ans.push_back(false);
continue;
}
int right_end = br;
while(bl != br){
int mid = (bl + br + 1) / 2;
if(calc_min(mid, right_end) > r){
br = mid - 1;
}
else{
bl = mid;
}
}
if(calc_min(s, bl) < l || calc_max(bl, e) > r){
ans.push_back(false);
}
else{
ans.push_back(true);
}
}
}
}
for(int i = 0; i < S.size(); i++){
to = E[i];
l = L[i];
r = R[i];
idx = i + 1;
ans.push_back(solve(S[i], false));
}
return ans;
}
