#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
const int nmax = 200005;
int Q, m, n, par[nmax], perm1[nmax], perm2[nmax], overlap[nmax], pos[nmax], aib[2*nmax], first1[nmax], last1[nmax], first2[nmax], last2[nmax];
vector<int>nod[nmax], nod1[nmax];
vector<int>euler1, euler2;
vector<pair<int,int>>Query[nmax];
struct item{
int coeff, indx, where;
};
vector<item>Query2[2*nmax];
void update(int pos, int val){
for(int i=pos;i<=2*n;i+=i&-i){
aib[i] += val;
}
}
int qry(int pos){
if(pos == 0) return 0;
int rs = 0;
for(int i=pos;i>=1;i-=i&-i){
rs += aib[i];
}
return rs;
}
int findpar(int x){
if(par[x] != x){
par[x] = findpar(par[x]);
}
return par[x];
}
void dfs(int s, vector<int>&euler, set<pair<int,int>>&st, int caz, int pr = 0){
euler.push_back(s);
for(auto it : nod1[s]){
dfs(it, euler, st, caz, s);
}
for(auto it : Query[s]){
st.insert({it.sc, it.fr});
}
if(caz == 1){
auto it = st.end();
while(it != st.begin()){
--it;
if(pr == 0){
perm1[it->sc] = s;
}
else{
if(it->fr > pr){
perm1[it->sc] = s;
auto it1 = it;
it++;
st.erase(it1);
}
else{
break;
}
}
}
}
else{
auto it = st.begin();
while(it != st.end()){
if(pr == 0){
perm2[it->sc] = s;
++it;
}
else{
if(it->fr < pr){
perm2[it->sc] = s;
auto it1 = it;
it++;
st.erase(it1);
}
else{
break;
}
}
}
}
euler.push_back(s);
}
void construct1(int caz, vector<int>&euler){
for(int i=1;i<=n;i++) par[i] = i;
if(caz == 1){
for(int i=n;i>=1;i--){
for(auto it : nod[i]){
if(it > i){
int curr = findpar(it);
if(curr != i){
nod1[i].push_back(curr);
par[curr] = i;
}
}
}
}
}
else{
for(int i=1;i<=n;i++){
for(auto it : nod[i]){
if(it < i){
int curr = findpar(it);
if(curr != i){
nod1[i].push_back(curr);
par[curr] = i;
}
}
}
}
}
if(caz == 1){
set<pair<int,int>>s;
dfs(1, euler, s, 1);
}
else{
set<pair<int,int>>s;
dfs(n, euler, s, 2);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
Q = S.size();
n = N;
m = X.size();
vector<int> A(Q);
for(int i=0;i<m;i++) X[i]++, Y[i]++;
for(int i=0;i<Q;i++) S[i]++, E[i]++, L[i]++, R[i]++;
for(int i=0;i<m;i++){
nod[X[i]].push_back(Y[i]);
nod[Y[i]].push_back(X[i]);
}
for(int i=0;i<Q;i++){
Query[S[i]].push_back({i, L[i]});
}
construct1(1, euler1);
for(int i=0;i<=n;i++){
nod1[i].clear();
}
for(int i=1;i<=n;i++){
Query[i].clear();
}
for(int i=0;i<Q;i++){
Query[E[i]].push_back({i, R[i]});
}
construct1(2, euler2);
for(int i=0;i<(int)euler1.size();i++){
if(first1[euler1[i]] == 0) first1[euler1[i]] = (i + 1);
else{
last1[euler1[i]] = (i + 1);
}
}
for(int i=0;i<(int)euler2.size();i++){
if(first2[euler2[i]] == 0) first2[euler2[i]] = (i + 1);
else{
last2[euler2[i]] = (i + 1);
}
}
for(int i=0;i<Q;i++){
Query2[first1[perm1[i]] - 1].push_back({1, i, first2[perm2[i]]});
Query2[first1[perm1[i]] - 1].push_back({-1, i, last2[perm2[i]]});
Query2[last1[perm1[i]]].push_back({1, i, last2[perm2[i]]});
Query2[last1[perm1[i]]].push_back({-1, i, first2[perm2[i]]});
}
for(int i=0;i<(int)euler1.size();i++){
update(first2[euler1[i]], 1);
update(last2[euler1[i]], 1);
for(auto it : Query2[i+1]){
overlap[it.indx] += it.coeff * qry(it.where);
}
}
for(int i=0;i<Q;i++){
if(overlap[i]){
A[i] = 1;
}
}
return A;
}
