#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
#ifndef ARTHUR_LOCAL
#include "werewolf.h"
#endif
using namespace std;
using vi = vector<int>;
#define REP(i,a,b) \
for(int i=int(a); i<=int(b); i++)
#define REPb(i,a,b) \
for(int i=int(a); i>=int(b); i--)
#define pb push_back
// ALL THE STUFF FROM ST1 and ST2
const int MAXN = int(2e5)+1;
bool human_vis[MAXN];
bool wolf_vis[MAXN];
vi adj[MAXN];
bool works=false;
int l=-1;
int r=-1;
int arr[MAXN];
int inv[MAXN];
int st[2][524288];
const int p2=262144;
const int INF=int(1e9);
void human_dfs(int u)
{
// cout << "HUMAN DFS AT " << u << endl;
human_vis[u]=1;
for(auto v:adj[u])
{
if(human_vis[v] || v < l) continue;
human_dfs(v);
}
}
void wolf_dfs(int u)
{
wolf_vis[u]=1;
if(works || human_vis[u])
{
works=1;
return;
}
for(auto v:adj[u])
{
if(wolf_vis[v] || v > r) continue;
wolf_dfs(v);
}
}
void build(int n)
{
REP(i,0,n-1)
{
st[0][i+p2]=arr[i];
st[1][i+p2]=arr[i];
}
REP(i,n,p2-1)
{
st[0][i+p2]=INF;
}
REPb(i,p2-1,1)
{
st[0][i]=min(st[0][2*i],st[0][i+i+1]);
st[1][i]=max(st[1][i+i],st[1][i+i+1]);
}
}
int query(bool b, int l, int r)
{
l+=p2;
r+=p2;
int ans=0;
if(!b) ans=int(1e9);
while(l<=r)
{
if(l%2 == 1)
{
if(b) ans=max(ans,st[b][l++]);
else ans=min(ans,st[b][l++]);
}
if(r%2 == 0)
{
if(b) ans=max(ans,st[b][r--]);
else ans=min(ans,st[b][r--]);
}
l/=2;
r/=2;
}
return ans;
}
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R)
{
int M = X.size();
int Q = S.size();
#ifdef ARTHUR_LOCAL
M=100000;
#endif
if(n<=3000 && M<=6000 && Q<=3000)
{
REP(i,0,M-1)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vi ans;
REP(q,0,Q-1)
{
REP(i,0,MAXN-1)
{
human_vis[i]=0;
wolf_vis[i]=0;
}
// cout << "DONE" << endl;
works=0;
l=L[q];
r=R[q];
human_dfs(S[q]);
wolf_dfs(E[q]);
if(works) ans.pb(1);
else ans.pb(0);
}
return ans;
}
REP(i,0,n-2)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
// cout << X[i] << " " << Y[i] << endl;
}
REP(i,0,n-1)
{
if(adj[i].size()==1)
{
arr[0]=i;
arr[1]=adj[i][0];
break;
}
}
REP(i,2,n-1)
{
if(adj[arr[i-1]][0] != arr[i-2]) arr[i]=adj[arr[i-1]][0];
else arr[i]=adj[arr[i-1]][1];
}
REP(i,0,n-1)
{
inv[arr[i]]=i;
}
build(n);
// cout << query(0,0,5) << endl; // looks like query does what it says on the tin
vi ans;
REP(q,0,Q-1)
{
int start = inv[S[q]];
int end = inv[E[q]];
l=L[q];
r=R[q];
// cout << start << " " << end << " " << l << " " << r << endl;
// cout << arr[end] << " " << r << endl;
if(arr[start]<l || arr[end]>r)
{
ans.pb(0);
continue;
}
if(start==end)
{
if(l<=arr[start] && r>=arr[start]) ans.pb(1);
else ans.pb(0);
continue;
}
if(start<end)
{
// bin search forwards from start
int lo=start;
int hi=end;
while(lo<hi)
{
int mid=(lo+hi)/2;
if(query(0,start,mid)>=l)
{
if(hi==lo+1) // stops infinite loop thing
{
if(query(0,start,hi)>=l) lo=hi;
else hi=lo;
}
else lo=mid;
}
else
{
hi=mid-1;
}
}
int max_travel_human = lo;
// bin search backwards from end
lo=start;
hi=end;
while(lo<hi)
{
int mid=(lo+hi)/2;
if(query(1,mid,end)<=r)
{
if(hi==lo+1)
{
if(query(1,hi,end)<=r) hi=lo;
else lo=hi;
}
else hi=mid;
}
else
{
lo=mid+1;
}
}
int min_travel_werewolf = lo;
// cout << min_travel_werewolf << " " << max_travel_human << endl;
if(min_travel_werewolf <= max_travel_human) ans.pb(1);
else ans.pb(0);
}
else // end < start
{
// reverse human and werewolf parts here
// cout << "HERE" << endl;
int lo=end;
int hi=start;
while(lo<hi)
{
// cout << lo << " " << hi << endl;
int mid=(lo+hi)/2;
if(query(1,end,mid)<=r)
{
if(hi==lo+1) // stops infinite loop thing
{
if(query(1,end,hi)<=r) lo=hi;
else hi=lo;
}
else lo=mid;
}
else
{
hi=mid-1;
}
}
int max_travel_wolf = lo;
// bin search backwards from end
lo=end;
hi=start;
while(lo<hi)
{
int mid=(lo+hi)/2;
if(query(0,mid,start)>=l)
{
if(hi==lo+1)
{
if(query(0,hi,start)>=l) hi=lo;
else lo=hi;
}
else hi=mid;
}
else
{
lo=mid+1;
}
}
int min_travel_human = lo;
// cout << min_travel_human << " " << max_travel_wolf << endl;
if(min_travel_human <= max_travel_wolf) ans.pb(1);
else ans.pb(0);
}
}
return ans;
}
// int main()
// {
// vi ans = check_validity(6,{4,3,0,2,1},{2,1,4,3,5},{4,4,5},{1,2,4},{2,2,3},{3,2,4});
// for(auto a:ans)
// {
// cout << a << " ";
// }
// cout << endl;
// }
