#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=200005,LOG=18;
vector<int> adj[MAXN],nx[MAXN];
bool vis[MAXN];
int pre[MAXN],pos[MAXN],dep[MAXN];
int pa[2][MAXN][LOG];
int ldr[2][MAXN];
int _ptr;
int f(int x,int k){ return x==ldr[k][x]?x:ldr[k][x]=f(ldr[k][x],k); }
void merge(int a,int b,int k){
a=f(a,k),b=f(b,k);
if(a==b) return;
pa[k][b][0]=a,ldr[k][b]=a;
}
/*
void dfs(int i,int k){
if(k) sort(adj[i].begin(),adj[i].end(),greater<int>());
else sort(adj[i].begin(),adj[i].end());
v[k][i][0]=i,vis[i]=1;
for(auto&x:adj[i]){
if(vis[x]) continue;
pa[k][x][0]=i,dep[k][x]=dep[k][i]+1;
dfs(x,k);
}
}
*/
void dfs(int i){
pre[i]=_ptr;
for(auto&x:nx[i]){
dep[x]=dep[i]+1;
dfs(x);
}
pos[i]=++_ptr;
}
vector<int> check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
int M=X.size(),Q=S.size();
for(int i=0;i<M;++i){
adj[X[i]].emplace_back(Y[i]);
adj[Y[i]].emplace_back(X[i]);
}
for(int i=0;i<N;++i) pa[0][i][0]=i,pa[1][i][0]=i,ldr[0][i]=i,ldr[1][i]=i;
for(int i=N-1;i>=0;--i) for(auto&x:adj[i]) if(x>i) merge(i,x,0);
for(int i=0;i<N;++i) for(auto&x:adj[i]) if(x<i) merge(i,x,1);
/*
dfs(0,0); // min
memset(vis,0,sizeof vis);
pa[1][N-1][0]=N-1;
dfs(N-1,1); // max
*/
for(int j=0;j<LOG-1;++j) for(int i=0;i<N;++i)
pa[0][i][j+1]=pa[0][pa[0][i][j]][j],
pa[1][i][j+1]=pa[1][pa[1][i][j]][j];
for(int i=0;i<N;++i) if(pa[1][i][0]!=i)
nx[pa[1][i][0]].emplace_back(i);
dfs(pa[1][0][LOG-1]);
/*
for(int i=0;i<N;++i)
cout<<dep[1][i]<<" ";
cout<<'\n';
*/
vector<int> A(Q,0);
for(int i=0;i<Q;++i){
int a=S[i];
for(int j=LOG-1;j>=0;--j)if(pa[0][a][j]>=L[i])
a=pa[0][a][j];
int t=a,b=E[i];
if(a>R[i]) continue;
if(dep[a]<dep[b]) swap(a,b);
for(int j=LOG-1;j>=0;--j) if(dep[pa[1][a][j]]>=dep[b])
a=pa[1][a][j];
if(a==b) A[i]=1;
else{
for(int j=LOG-1;j>=0;--j) if(pa[1][a][j]!=pa[1][b][j])
a=pa[1][a][j],b=pa[1][b][j];
int c=pa[1][a][0];
cout<<c<<'\n';
if(c<=R[i]) A[i]=1;
}
/*
if(dep[1][a]<dep[1][b]) swap(a,b);
int maxi=0;
cout<<a<<" "<<b<<" "<<'\n';
for(int j=LOG-1;j>=0;--j)if(dep[1][pa[1][a][j]]>=dep[1][b])
maxi=max(maxi,v[1][a][j]),a=pa[1][a][j];
cout<<a<<" "<<b<<" "<<maxi<<'\n';
if(maxi<=R[i]) A[i]=1;
else A[i]=0;
*/
}
return A;
}
