#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;
const int lim=2e5+100;
vector<int>v[lim];
int parent[lim],sz[lim],tin[lim];
void init(){
for(int i=0;i<lim;i++){
parent[i]=i;
sz[i]=1;
tin[i]=INT_MAX;
}
}
int find(int i){
if(i==parent[i])return i;
return find(parent[i]);
}
void merge(int x,int y,int tt){
x=find(x),y=find(y);
if(x==y)return;
if(sz[y]<sz[x])swap(x,y);
parent[x]=y;
tin[x]=tt;
sz[y]+=sz[x];
}
int query(int i,int j){
int ans=0;
while(i!=j){
if(tin[j]<tin[i])swap(i,j);
ans=max(ans,tin[i]);
i=parent[i];
}
return ans;
}
int N;
void coolmerge(int i,int j){
vector<pair<int,pii>>todo;
todo.pb(pair<int,pii>{0,pii{i,j}});
int x=i,y=j;
int k=0;
while(x!=y){
if(tin[y]<tin[x])swap(x,y);
int par=parent[x];
todo.pb(pair<int,pii>{tin[x],pii{x,par}});
x=par;
}
int par=parent[x];
todo.pb(pair<int,pii>{tin[x],pii{x,par}});
for(int i=1;i<todo.size();i++){
int guy=todo[i].second.first,par=todo[i].second.second;
sz[par]-=sz[guy];
parent[guy]=guy;
tin[guy]=INT_MAX;
}
sort(todo.begin(),todo.end());
for(auto[tt,guys]:todo){
merge(guys.first,guys.second,tt);
}
}
vector<int>check_validity(int n,vector<int>X,vector<int>Y,vector<int>s,vector<int>e,vector<int>L,vector<int>R){
init();
N=n;
int m=X.size();
int q=s.size();
for(int i=0;i<m;i++){
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
for(int i=0;i<n;i++){
for(int j:v[i]){
if(j<i){
merge(i,j,i);
}
}
}
vector<int>ans(q);
vector<int>toask[n];
for(int i=0;i<q;i++){
toask[L[i]].pb(i);
}
for(int i=n-1;0<=i;i--){
for(int j:v[i]){
if(i<j){
coolmerge(i,j);
}
}
for(int id:toask[i]){
int res=query(s[id],e[id]);
ans[id]=(res<=R[id]);
}
}
return ans;
}
// 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 = S.size();
// std::vector<int> A(Q);
// for (int i = 0; i < Q; ++i) {
// A[i] = 0;
// }
// return A;
// }
