#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MX=5e5;
int M, Q, N;
vi adj[MX];
vi A, B, SEGMIN, SEGMAX, POSB;
void dfs(int u, int p=-1) {
B[N++] = u;
for(int v:adj[u]) if(v != p) dfs(v, u);
}
void buildSeg(int p=0, int l=0, int r=N-1) {
if(l == r) {
SEGMIN[p] = B[l];
SEGMAX[p] = B[l];
return;
}
int m=(l+r)/2;
buildSeg(p*2+1,l,m);
buildSeg(p*2+2,m+1,r);
SEGMIN[p] = min(SEGMIN[p*2+1], SEGMIN[p*2+2]);
SEGMAX[p] = min(SEGMAX[p*2+1], SEGMAX[p*2+2]);
}
int getMin(int i, int j, int p=0, int l=0, int r=N-1) {
if(j < l || i > r) return INF;
if(i <= l && j >= r) return SEGMIN[p];
int m=(l+r)/2;
int a=getMin(i,j,p*2+1,l,m);
int b=getMin(i,j,p*2+2,m+1,r);
return min(a,b);
}
int getMax(int i, int j, int p=0, int l=0, int r=N-1) {
if(j < l || i > r) return -INF;
if(i <= l && j >= r) return SEGMAX[p];
int m=(l+r)/2;
int a=getMax(i,j,p*2+1,l,m);
int b=getMax(i,j,p*2+2,m+1,r);
return max(a,b);
}
vi check_validity2(vi& X, vi& Y, vi& S, vi& E, vi& L, vi& R) {
int start = 0;
RE(i,N) if(adj[i].size() == 1) start = i;
B.resize(N); N=0;
dfs(start);
POSB.resize(N);
RE(i,N) POSB[B[i]] = i;
SEGMIN.resize(N*4);
SEGMAX.resize(N*4);
buildSeg();
RE(i,Q) {
int s=POSB[S[i]], e=POSB[E[i]];
if(s < e) {
if(getMin(s,e) >= L[i]) {
if(B[e] <= R[i]) A[i] = 1;
else A[i] = 0;
} else {
int lb=s, ub=e;
while(lb != ub) {
int mid=(lb+ub)/2;
if(getMin(s, mid) < L[i]) ub=mid;
else lb=mid+1;
}
if(lb == s) A[i] = 0;
else if(B[lb-1] > R[i]) A[i] = 0;
else if(getMax(lb, e) > R[i]) A[i] = 0;
else A[i] = 1;
}
} else {
if(getMin(e,s) >= L[i]) {
if(B[e] <= R[i]) A[i] = 1;
else A[i] = 0;
} else {
int lb=e, ub=s;
while(lb != ub) {
int mid=(lb+ub+1)/2;
if(getMin(mid, s) < L[i]) lb=mid;
else ub=mid-1;
}
if(ub == s) A[i] = 0;
else if(B[lb+1] > R[i]) A[i] = 0;
else if(getMax(e, lb) > R[i]) A[i] = 0;
else A[i] = 1;
}
}
}
return A;
}
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
N = n;
M = X.size();
Q = S.size();
A.resize(Q);
RE(i,M) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
if(N > 3000) return check_validity2(X, Y, S, E, L, R);
bitset<6000> visited[2];
RE(i,Q) {
RE(j,2) visited[j].reset();
queue<ii> q; q.push({S[i],0}); visited[0][S[i]]=1;
while(!q.empty()) {
ii p = q.front(); q.pop();
int u = p.fi;
int w = p.se;
for(int v : adj[u]) {
if(visited[w][v] ) continue;
if(!w && v < L[i]) continue;
if( w && v > R[i]) continue;
visited[w][v] = 1;
q.push({v,w});
}
if(!visited[1][u] && L[i] <= u && u <= R[i]) {
visited[1][u] = 1;
q.push({u,1});
}
}
A[i] = visited[1][E[i]];
}
return A;
}
