#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj1[3005];
vector<int>adj2[3005];
vector<int>adj3[200001];
bool b=false;
bool vis1[3005];
bool vis2[3005];
bool vis3[200001];
int cnt[200001];
vector<int>v;
int rv[200001];
int st1[200001][19];
int st2[200001][19];
void dfs1(int cur,int par){
vis1[cur]=1;
for(int i:adj1[cur]){
if(i!=par&&!vis1[i]){
dfs1(i,cur);
}
}
}
void dfs2(int cur,int par){
vis2[cur]=1;
if(vis1[cur]){
b=true;
return;
}
for(int i:adj2[cur]){
if(i!=par&&!vis2[i]){
dfs2(i,cur);
}
}
}
void dfs3(int cur,int par){
vis3[cur]=1;
for(int i:adj3[cur]){
if(i!=par&&!vis3[i]){
v.push_back(i);
rv[i]=v.size()-1;
dfs3(i,cur);
}
}
}
void build1(int N){
for(int i=0;i<N;i++){
st1[i][0]=i;
}
for(int j=1;j<=(int)log2(N);j++){
for(int i=0;i<N+1-(1<<j);i++){
if(v[st1[i][j-1]]<v[st1[i+(1<<(j-1))][j-1]]){
st1[i][j]=st1[i][j-1];
}
else{
st1[i][j]=st1[i+(1<<(j-1))][j-1];
}
}
}
}
void build2(int N){
for(int i=0;i<N;i++){
st2[i][0]=i;
}
for(int j=1;j<=(int)log2(N);j++){
for(int i=0;i<N+1-(1<<j);i++){
if(v[st2[i][j-1]]>v[st2[i+(1<<(j-1))][j-1]]){
st2[i][j]=st2[i][j-1];
}
else{
st2[i][j]=st2[i+(1<<(j-1))][j-1];
}
}
}
}
int query1(int L,int R){
int j=(int)log2(R-L+1);
if(v[st1[L][j]]<v[st1[R-(1<<j)+1][j]]){
return st1[L][j];
}
return st1[R-(1<<j)+1][j];
}
int query2(int L,int R){
int j=(int)log2(R-L+1);
if(v[st2[L][j]]>v[st2[R-(1<<j)+1][j]]){
return st2[L][j];
}
return st2[R-(1<<j)+1][j];
}
int bsearch1(int s,int e,int l,bool b){
if(v[query1(s,e)]>=l){
if(b) return e+1;
return e-1;
}
if(b){
//search from left
int m=(s+e)/2;
if(e-s<=1){
if(v[s]<l){
return s;
}
return e;
}
if(v[query1(s,m)]<l){
return bsearch1(s,m,l,b);
}
return bsearch1(m,e,l,b);
}
else{
//search from right
int m=(s+e)/2;
if(s-e<=1){
if(v[s]<l){
return s;
}
return e;
}
if(v[query1(m,s)]<l){
return bsearch1(m,s,l,b);
}
return bsearch1(e,m,l,b);
}
}
int bsearch2(int s,int e,int r,bool b){
if(v[query2(s,e)]<=r){
if(b) return s-1;
return s+1;
}
if(b){
//search from right
int m=(s+e)/2;
if(e-s<=1){
if(v[e]>r){
return e;
}
return s;
}
if(v[query2(m,e)]>r){
return bsearch2(m,e,r,b);
}
return bsearch2(s,m,r,b);
}
else{
//search from left
int m=(s+e)/2;
if(s-e<=1){
if(v[e]>r){
return e;
}
return s;
}
if(v[query2(e,m)]>r){
return bsearch2(e,m,r,b);
}
return bsearch2(m,s,r,b);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
vector<int>ans;
if(N<=3000){
for(int i=0;i<L.size();i++){
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
int l=L[i],r=R[i],s=S[i],e=E[i];
for(int j=0;j<=3000;j++){
adj1[j].clear();
adj2[j].clear();
}
for(int j=0;j<X.size();j++){
if(X[j]>=l&&Y[j]>=l){
adj1[X[j]].push_back(Y[j]);
adj1[Y[j]].push_back(X[j]);
}
if(X[j]<=r&&Y[j]<=r){
adj2[X[j]].push_back(Y[j]);
adj2[Y[j]].push_back(X[j]);
}
}
b=false;
dfs1(s,3003);
dfs2(e,3003);
if(b){
ans.push_back(1);
}
else{
ans.push_back(0);
}
}
}
else{
for(int i=0;i<X.size();i++){
cnt[X[i]]++;
cnt[Y[i]]++;
adj3[X[i]].push_back(Y[i]);
adj3[Y[i]].push_back(X[i]);
}
for(int i=0;i<N;i++){
if(cnt[i]==1){
v.push_back(i);
rv[i]=0;
break;
}
}
dfs3(v[0],200005);
build1(N);
build2(N);
for(int i=0;i<S.size();i++){
int s=rv[S[i]],e=rv[E[i]],l=L[i],r=R[i];
bool b=false;
if(s<e){
b=true;
}
int x=bsearch1(s,e,l,b);
int y=bsearch2(s,e,r,b);
if(b){
x--;
y++;
}
else{
x++;
y--;
}
if(b^(x>=y)){
ans.push_back(0);
}
else{
ans.push_back(1);
}
}
}
return ans;
}
