#pragma GCC optimize("O3")
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
#define INF (int)(1e9)
vector<vector<int> > vec;
int A[200005],idx=0,to_id[200005];
ii st[800005];
bool vis[200005];
void build(int node,int l,int r){
if(l==r){
st[node]=ii(A[l],A[l]);
return ;
}
int med=((l+r)>>1);
build(node<<1,l,med),build((node<<1)+1,med+1,r);
st[node].fi=min(st[node<<1].fi,st[(node<<1)+1].fi);
st[node].se=max(st[node<<1].se,st[(node<<1)+1].se);
}
ii query(int node,int l,int r,int i,int j){
if(l>j||r<i)
return ii(INF,-1);
if(l>=i&&r<=j)
return st[node];
int med=((l+r)>>1);
ii q1=query(node<<1,l,med,i,j),q2=query((node<<1)+1,med+1,r,i,j);
return ii(min(q1.fi,q2.fi),max(q1.se,q2.se));
}
int D,LE,RE;
int vis_dfs[5001],v=1;
int dp[3001][2][2];
int dfs(int node,int changed,int trans){
//cerr<<node<<" "<<changed<<" "<<trans<<"\n";
if(node==D&&!changed&&trans)return 1;
if(node==D)return changed;
if(dp[node][changed][trans]!=-1)
return dp[node][changed][trans];
vis_dfs[node]=1;
int ans=0;
for(auto child:vec[node]){
if(vis_dfs[child]==1)continue;
if(child<LE&&!changed){
if(trans)ans|=dfs(child,1,0);
else continue;
}
if(child>RE&&changed)continue;
if(child<=RE&&changed)ans|=dfs(child,1,0);
if(child>=LE&&!changed)ans|=dfs(child,0,((child>=LE&&child<=RE)));
if(trans&&child<=RE&&!changed)ans|=dfs(child,1,0);
if(ans){vis_dfs[node]=0; return dp[node][changed][trans]=1;}
}
vis_dfs[node]=0;
return dp[node][changed][trans]=0;
}
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();
vec.resize(N);
for (int i = 0; i < X.size(); ++i)
{
vec[X[i]].pb(Y[i]);
vec[Y[i]].pb(X[i]);
}
if(N<=3000||M<=6000||Q<=3000){
vector<int> res(Q);
for (int i =0; i < Q; ++i)
{
memset(dp,-1,sizeof dp);
D=E[i];
LE=L[i],RE=R[i];
//cerr<<S[i]<<","<<E[i]<<"\n";
//cerr<<L[i]<<","<<R[i]<<"\n";
if(S[i]<LE||E[i]>RE)res[i]=0;
else res[i]=dfs(S[i],0,(S[i]>=L[i]&&S[i]<=R[i]));
}
return res;
}
int start=0;
for (int i = 0; i < N; ++i)
if(vec[i].size()==1){
start=i;
break;
}
queue<int> AA;
AA.push(start);
vis[start]=1;
while(!AA.empty()){
int front=AA.front();
A[idx]=front;
to_id[front]=idx++;
AA.pop();
for(auto child:vec[front])
if(!vis[child])
vis[child]=1,AA.push(child);
}
build(1,0,idx);
vector<int> res(Q);
fill(res.begin(),res.end(),0);
for (int i = 0; i < Q; ++i) {
if(S[i]==E[i]){
if(S[i]<=R[i]&&S[i]>=L[i])res[i]=1;
else res[i]=0;
continue;
}
if(S[i]<L[i]||E[i]>R[i]){res[i]=0;continue;}
if(to_id[S[i]]<to_id[E[i]]){
int l=to_id[S[i]],r=to_id[E[i]];
while(l<=r){
int med=((l+r)>>1);
if(med!=to_id[S[i]]){
ii q=query(1,0,idx,to_id[S[i]],med-1);
if(q.fi<L[i]){r=med-1;continue;}
}
if(med!=to_id[E[i]]){
ii q=query(1,0,idx,med+1,to_id[E[i]]);
if(q.se>R[i]){l=med+1;continue;}
}
if(A[med]<=R[i]&&A[med]>=L[i])res[i]=1;
else if(A[med]>=L[i]){
if(A[med]==(E[i]))res[i]=0;
else if(A[med+1]<=R[i]&&A[med+1]>=L[i])res[i]=1;
else res[i]=0;
}
else if(A[med]<=R[i]){
if(A[med]==S[i])res[i]=0;
else if(A[med-1]<=R[i]&&A[med-1]>=L[i])res[i]=1;
else res[i]=0;
}
break;
}
}
else{
int l=to_id[E[i]],r=to_id[S[i]];
while(l<=r){
int med=((l+r)>>1);
if(med!=to_id[E[i]]){
ii q=query(1,0,idx,to_id[E[i]],med-1);
if(q.se>R[i]){r=med-1;continue;}
}
if(med!=to_id[S[i]]){
ii q=query(1,0,idx,med+1,to_id[S[i]]);
if(q.fi<L[i]){l=med+1;continue;}
}
if(A[med]<=R[i]&&A[med]>=L[i])res[i]=1;
else if(A[med]<=R[i]){
if(A[med]==(S[i]))res[i]=0;
else if(A[med+1]<=R[i]&&A[med+1]>=L[i])res[i]=1;
else res[i]=0;
}
else if(A[med]>=L[i]){
if(A[med]==E[i])res[i]=0;
else if(A[med-1]<=R[i]&&A[med-1]>=L[i])res[i]=1;
else res[i]=0;
}
break;
}
}}
return res;
}
