#include "werewolf.h"
//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugp(x,y) cerr<<#x<<' '<<#y<<" is "<<x<<' '<<y<<endl;
#define debugl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p<<" ";cerr<<endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<" , ";cerr<<endl;
//#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define rdint(x,y) rnd()%(y-x+1)+x
//const int inf=4e18+5;
const int mod=1e9+7;
const int mod2=998244353;
const int mod3=1e9+9;
const int maxn=2e5+5;
vi adj[maxn];
int p[maxn][22][2];//going each way
int pmin[maxn][22][2];
int pmax[maxn][22][2];
int d[maxn][2];
int n;
void dfs(int x,int pr,int dir){
//debug(x)
p[x][0][dir]=pr;
pmin[x][0][dir]=x;
pmax[x][0][dir]=x;
d[x][dir]=d[pr][dir]+1;
for(auto i:adj[x]){
if(i==pr)continue;
dfs(i,x,dir);
}
}
void dcmp(){
for(int k=2;k<22;k++){
for(int i=1;i<=n;i++){
p[i][k][0]=p[p[i][k-1][0]][k-1][0];
p[i][k][1]=p[p[i][k-1][1]][k-1][1];
pmin[i][k][0]=min(pmin[i][k-1][0],pmin[p[i][k-1][0]][k-1][0]);
pmin[i][k][1]=min(pmin[i][k-1][1],pmin[p[i][k-1][1]][k-1][1]);
pmax[i][k][0]=max(pmax[i][k-1][0],pmax[p[i][k-1][0]][k-1][0]);
pmax[i][k][1]=max(pmax[i][k-1][1],pmax[p[i][k-1][1]][k-1][1]);
}
}
}
bool bsta(int x,int t,int l,int r,int dr){
//debug(x)
int w=x;
for(int k=21;k>=0;k--){
if(d[p[w][k][dr]][dr]<=d[t][dr])continue;
if(pmin[w][k][dr]>=l){
w=p[w][k][dr];
//debug(w)
}
}
w=p[w][0][dr];
int h=t;
for(int k=21;k>=0;k--){
if(d[p[h][k][1-dr]][1-dr]<=d[x][1-dr])continue;
if(pmax[h][k][1-dr]<=r){
h=p[h][k][1-dr];
//debug(h)
}
}
h=p[h][0][1-dr];
//debugp(w,h)
return (d[h][dr]<d[w][dr]);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int q=sz(S);
vi ans;
n=N;
//vi adj[N];
set<int> ep;
for(int i=0;i<sz(X);i++){
X[i]++,Y[i]++;
if(ep.find(X[i])!=ep.end())ep.erase(X[i]);
else ep.insert(X[i]);
if(ep.find(Y[i])!=ep.end())ep.erase(Y[i]);
else ep.insert(Y[i]);
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
dfs(*ep.begin(),0,0);
dfs(*(++ep.begin()),0,1);
dcmp();
for(int i=0;i<q;i++){
L[q]++,R[q]++;
E[q]++,S[q]++;
//debug(S[i])
if(d[E[i]][0]<d[S[i]][0])ans.pb(bsta(S[i],E[i],L[i],R[i],0));
else ans.pb(bsta(S[i],E[i],L[i],R[i],1));
}
//debugp(p[3][0][0],p[3][0][1])
//debugp(p[5][0][0],p[5][0][1])
return ans;
}
