#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
const int N = 2e5 + 5;
vector<int> edges[N];
int c[N];
struct ST{
int mn[N << 2], mx[N << 2];
void set(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx) { mn[x] = mx[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);
mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
int get_f(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return -1;
if(lx >= l && rx <= r){
if(mn[x] >= v) return -1;
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(mn[x << 1] < v) return get_f(l, r, v, lx, m, x << 1);
else return get_f(l, r, v, m + 1, rx, x << 1 | 1);
} int m = (lx + rx) >> 1;
int res = get_f(l, r, v, lx, m, x << 1);
if(~res) return res;
return get_f(l, r, v, m + 1, rx, x << 1 | 1);
}
int get_l(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return -1;
if(lx >= l && rx <= r){
if(mn[x] >= v) return -1;
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(mn[x << 1 | 1] < v) return get_l(l, r, v, m + 1, rx, x << 1 | 1);
else return get_l(l, r, v, lx, m, x << 1);
} int m = (lx + rx) >> 1;
int res = get_l(l, r, v, m + 1, rx, x << 1 | 1);
if(~res) return res;
return get_l(l, r, v, lx, m, x << 1);
}
int get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return mx[x];
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
}tree;
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();
for(int i=0;i<m;i++){
edges[X[i]].push_back(Y[i]);
edges[Y[i]].push_back(X[i]);
}
int q = S.size();
vector<int> a(q);
if(n <= 3000 && m <= 6000 && q <= 3000){
for(int i=0;i<q;i++){
int s = S[i], e = E[i], vl = L[i], vr = R[i];
for(int i=0;i<n;i++){
if(i < vl) c[i] = 0;
if(vr < i) c[i] = 1;
if(vl <= i && i <= vr) c[i] = 2;
}
vector<int> used(n);
int t = 1;
function<void(int)> dfs = [&](int u){
used[u] = 1;
for(auto x : edges[u]){
if(used[x]) continue;
if(c[x] == t || c[x] == 2){
dfs(x);
}
}
};
dfs(s);
vector<int> tmp = used; fill(used.begin(), used.end(), 0);
t = 0;
dfs(e);
for(int j=0;j<n;j++){
if(used[j] && tmp[j]){
a[i] = 1;
}
}
}
return a;
}
int r = 0;
for(int i=0;i<n;i++){
if((int)edges[i].size() == 1) { r = i; break; }
}
vector<int> pos(n), val(n + 1);
function<void(int, int)> dfs = [&](int u, int p){
for(auto x : edges[u]){
if(x == p) continue;
pos[x] = pos[u] + 1;
dfs(x, u);
}
};
pos[r] = 1;
dfs(r, r);
for(int i=0;i<n;i++){
val[pos[i]] = i;
tree.set(pos[i], i);
}
for(int i=0;i<q;i++){
int s = S[i], e = E[i], vl = L[i], vr = R[i];
if(s == e) a[i] = 1;
if(pos[s] < pos[e]){
int p = tree.get_f(pos[s], N, vl);
p = min(p, pos[e] + 1);
if(vl <= val[p - 1] && val[p - 1] <= vr && (p <= pos[e] ? tree.get(p, pos[e]) <= vr : true)){
a[i] = 1;
}
} if(pos[s] > pos[e]) {
int p = tree.get_l(0, pos[s], vl);
p = max(p, pos[e] - 1);
if(vl <= val[p + 1] && val[p + 1] <= vr && (pos[e] <= p ? tree.get(pos[e], p) <= vr : true)){
a[i] = 1;
}
}
}
return a;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
6 5 3
0 3
3 2
2 1
1 5
5 4
1 2
*/
