#include "werewolf.h"
#include <vector>
#include <set>
#include <iostream>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//#define int long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
const int SZ = 3e3 + 7;
const int R = 2e5 + 7;
const int LOG = 19;
vector<int> g[R];
int ver[R],pos[R];
int timer = 0;
vector<vector<int>> sp(R,vector<int> (LOG,2e9));
vector<vector<int>> sg(R,vector<int> (LOG,-2e9));
int mn[SZ][SZ];
int mx[SZ][SZ];
void dfs(int v,int p) {
ver[timer] = v;
pos[v] = timer;
timer += 1;
for(int u : g[v]) {
if(u == p) continue;
dfs(u,v);
}
}
int get_min(int l,int r) {
int k = __lg(r - l + 1);
return min(sp[l][k],sp[r - (1 << k) + 1][k]);
}
int get_max(int l,int r) {
int k = __lg(r - l + 1);
return max(sg[l][k],sg[r - (1 << k) + 1][k]);
}
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(),Q = L.size();
for(int i = 0; i < M; ++i) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
bool ok = (N - 1 == M);
int cnt = 0;
for(int i = 0; i < N; ++i) {
if(g[i].size() == 1) {
cnt += 1;
}
}
ok &= (cnt == 2);
if(!ok) {
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
mn[i][j] = 2e9;
mx[i][j] = -2e9;
}
}
set<pair<int,int>> st;
for(int i = 0; i < N; ++i) {
st.insert({0,i});
mn[i][i] = i;
while(st.size()) {
pair<int,int> p = *st.begin();
int v = p.ss;
st.erase(st.begin());
for(int u : g[v]) {
if(mn[i][u] > max(mn[i][v],u)) {
st.erase({mn[i][u],u});
mn[i][u] = max(mn[i][v],u);
st.insert({mn[i][u],u});
}
}
}
st.insert({i,i});
mx[i][i] = i;
while(st.size()) {
pair<int,int> p = *(--st.end());
int v = p.ss;
st.erase(--st.end());
for(int u : g[v]) {
if(mx[i][u] < min(mx[i][v],u)) {
st.erase({mn[i][u],u});
mx[i][u] = min(mx[i][v],u);
st.insert({mx[i][u],u});
}
}
}
}
vector<int> ans(Q);
for(int i = 0; i < Q; ++i) {
int s = S[i],e = E[i];
for(int v = 0; v < N; ++v) {
if(mx[s][v] >= L[i] && mn[v][e] <= R[i]) {
ans[i] = 1;
break;
}
}
}
return ans;
}
int kor = 0;
for(int i = 0; i < N; ++i) {
if(g[i].size() == 1) {
kor = i;
break;
}
}
dfs(kor,-1);
for(int i = 0; i < timer; ++i) {
sp[i][0] = ver[i];
sg[i][0] = ver[i];
}
for(int log = 1; log < LOG; ++log) {
for(int i = 0; i + (1 << (log - 1)) < timer; ++i) {
sp[i][log] = min(sp[i][log - 1],sp[i + (1 << (log - 1))][log - 1]);
sg[i][log] = max(sg[i][log - 1],sg[i + (1 << (log - 1))][log - 1]);
}
}
vector<int> ans(Q);
for(int i = 0; i < Q; ++i) {
int s = S[i],e = E[i];
if(pos[s] <= pos[e]) {
int v = pos[s];
for(int log = LOG - 1; log >= 0; --log) {
if(log != 0) {
while(v + (1 << log) - 1 <= pos[e] && sp[v][log] >= L[i]) {
v = v + (1 << log) - 1;
}
} else {
if(v + (1 << log) - 1 <= pos[e] && sp[v][log] >= L[i]) {
v = v + (1 << log) - 1;
}
}
}
if(get_max(v,pos[e]) <= R[i]) {
ans[i] = 1;
}
} else {
int v = pos[e];
for(int log = LOG - 1; log >= 0; --log) {
if(log != 0) {
while(v + (1 << log) - 1 <= pos[s] && sg[v][log] <= R[i]) {
v = v + (1 << log) - 1;
}
} else {
if(v + (1 << log) - 1 <= pos[s] && sg[v][log] <= R[i]) {
v = v + (1 << log) - 1;
}
}
}
if(get_min(v,pos[s]) >= L[i]) {
ans[i] = 1;
}
}
}
return ans;
}
