#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef int64_t ll;
typedef int32_t ii;
//~ #define int ll
struct ST{
vector<int> Min, Max;
int N;
ST(int N): N(N){
Min.resize(N << 2);
Max.resize(N << 2);
}
void set(int i, int v, int lx, int rx, int x){
if(lx == rx) { Min[x] = Max[x] = v; return; }
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
int first_less(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return -1;
if(lx >= l && rx <= r){
if(Min[x] >= v) return -1;
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(Min[x << 1] < v) return first_less(l, r, v, lx, m, x << 1);
else return first_less(l, r, v, m + 1, rx, x << 1 | 1);
}
int m = (lx + rx) >> 1;
int res = first_less(l, r, v, lx, m, x << 1);
if(res == -1) res = first_less(l, r, v, m + 1, rx, x << 1 | 1);
return res;
}
int first_less(int l, int r, int v){
return first_less(l, r, v, 0, N, 1);
}
int last_less(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return -1;
if(lx >= l && rx <= r){
if(Min[x] >= v) return -1;
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(Min[x << 1 | 1] < v) return last_less(l, r, v, m + 1, rx, x << 1 | 1);
else return last_less(l, r, v, lx, m, x << 1);
}
int m = (lx + rx) >> 1;
int res = last_less(l, r, v, m + 1, rx, x << 1 | 1);
if(res == -1) res = last_less(l, r, v, lx, m, x << 1);
return res;
}
int last_less(int l, int r, int v){
return last_less(l, r, v, 0, N, 1);
}
int get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return Max[x];
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
int get(int l, int r){
return get(l, r, 0, N, 1);
}
int first_big(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return -1;
if(lx >= l && rx <= r){
if(Max[x] <= v) return -1;
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(Max[x << 1] > v) return first_big(l, r, v, lx, m, x << 1);
else return first_big(l, r, v, m + 1, rx, x << 1 | 1);
}
int m = (lx + rx) >> 1;
int res = first_big(l, r, v, lx, m, x << 1);
if(res == -1) res = first_big(l, r, v, m + 1, rx, x << 1 | 1);
return res;
}
int first_big(int l, int r, int v){
return first_big(l, r, v, 0, N, 1);
}
int last_big(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return -1;
if(lx >= l && rx <= r){
if(Max[x] <= v) return -1;
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(Max[x << 1 | 1] > v) return last_big(l, r, v, m + 1, rx, x << 1 | 1);
else return last_big(l, r, v, lx, m, x << 1);
}
int m = (lx + rx) >> 1;
int res = last_big(l, r, v, m + 1, rx, x << 1 | 1);
if(res == -1) res = last_big(l, r, v, lx, m, x << 1);
return res;
}
int last_big(int l, int r, int v){
return last_big(l, r, v, 0, N, 1);
}
};
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 m = x.size();
int q = s.size();
vector<vector<int>> edges(n);
for(int i=0;i<m;i++){
edges[x[i]].push_back(y[i]);
edges[y[i]].push_back(x[i]);
}
if(n <= 3000 && m <= 6000 && q <= 3000){
vector<int> used_s(n), used_e(n);
function<void(vector<int>&, int, int, int)> dfs = [&](vector<int>& used, int u, int l, int r){
used[u] = 1;
for(auto x : edges[u]){
if(!used[x] && l <= x && x <= r){
dfs(used, x, l, r);
}
}
};
vector<int> ans(q);
for(int i=0;i<q;i++){
fill(used_s.begin(), used_s.end(), 0);
fill(used_e.begin(), used_e.end(), 0);
dfs(used_s, s[i], l[i], n);
dfs(used_e, e[i], 0, r[i]);
for(int j=0;j<n;j++){
if(used_s[j] && used_e[j]){
ans[i] = 1;
break;
}
}
}
return ans;
}
ST tree(n);
int root = -1;
for(int i=0;i<n;i++){
if((int)edges[i].size() == 1){
root = i;
break;
}
}
assert(~root);
vector<int> pos(n);
int last = 0;
function<void(int, int)> dfs = [&](int u, int p){
pos[u] = last++;
for(auto x : edges[u]){
if(x == p) continue;
dfs(x, u);
}
};
dfs(root, root);
vector<int> a(n);
for(int i=0;i<n;i++){
a[pos[i]] = i;
tree.set(pos[i], i);
}
vector<int> ans(q);
for(int j=0;j<q;j++){
int l_= pos[s[j]], r_ = pos[e[j]];
if(l_ < r_){
int L = tree.last_big(l_, r_, r[j]);
int R = tree.first_less(l_, r_, l[j]);
if(L == -1 || R == -1 || L + 1 < R){
ans[j] = 1;
}
//~ int p = tree.first_less(l_, r_, l[j]);
//~ assert(p == -1 || l_ < p);
//~ if(p == -1 || (l[j] <= a[p - 1] && a[p - 1] <= r[j] && tree.get(p, r_) <= r[j])){
//~ ans[j] = 1;
//~ }
} else {
int R = tree.first_big(r_, l_, r[j]);
int L = tree.last_less(r_, l_, l[j]);
if(L == -1 || R == -1 || L + 1 < R){
ans[j] = 1;
}
//~ int p = tree.last_less(r_, l_, l[j]);
//~ assert(p == -1 || p < l_);
//~ if(p == -1 || (l[j] <= a[p + 1] && a[p + 1] <= r[j] && tree.get(r_, p) <= r[j])){
//~ ans[j] = 1;
//~ }
}
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
2 5
4 2 1 2
4 2 2 2
5 4 3 4
5 4 4
4 1
1 0
0 3
3 2
4 0 1 1
4 3 1 3
2 0 1 1
3 1 3 3
*/
