#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define dl double long
const int maxn = 200200;
int n,m,q;
int tim;
int tin1[maxn];
int tout1[maxn];
int tin2[maxn];
int tout2[maxn];
int p[maxn];
int o1[maxn];
int o2[maxn];
int d1[maxn][25];
int d2[maxn][25];
vector < int > g[maxn];
vector < int > v[maxn],t[4 * maxn];
vector < pair < int , int > > gg[maxn];
void build( int x , int l , int r )
{
if( l == r ){
t[x].push_back( tin1[o2[l]] );
return;
}
int m = (l + r) / 2;
build( x + x , l , m );
build( x + x + 1 , m + 1 , r );
int i = 0 , j = 0;
while( i < (int)t[x + x].size() && j < (int)t[x + x + 1].size() ){
if( t[x + x][i] < t[x + x + 1][j] ){
t[x].push_back(t[x + x][i++]);
}else t[x].push_back(t[x + x + 1][j++]);
}
while( j < (int)t[x + x + 1].size() ){
t[x].push_back(t[x + x + 1][j++]);
}
while( i < (int)t[x + x].size() ){
t[x].push_back(t[x + x][i++]);
}
}
int get1( int x , int l , int r , int tl , int tr , int tl1 , int tr1 )
{
if( tl > tr )return 0;
if( l == tl && r == tr ){
int y = (int)(lower_bound( t[x].begin() , t[x].end() , tl1 ) - t[x].begin());
if( y != (int)t[x].size() && t[x][y] <= tr1 )return 1;
return 0;
}
int m = (l + r) / 2;
return ( get1( x + x , l , m , tl , min( tr , m ) , tl1 , tr1 ) |
get1( x + x + 1 , m + 1 , r , max( tl , m + 1 ) , tr , tl1 , tr1 ) );
}
int get( int x )
{
return (p[x] == x ? x : p[x] = get(p[x]));
}
void meg( int x , int y )
{
int px = get(x);
int py = get(y);
if( px == py )return;
p[px] = py;
g[py].push_back(px);
g[px].push_back(py);
}
void dfs( int x , int p )
{
d1[x][0] = p;
for( int i = 1; i < 25; i++ ){
d1[x][i] = d1[d1[x][i - 1]][i - 1];
}
tin1[x] = ++tim;
o1[tim] = x;
for( auto y : g[x] ){
if( y == p )continue;
dfs( y , x );
}
tout1[x] = tim;
}
int ff( int x , int y )
{
for( int i = 24; i >= 0; i-- ){
if( d2[x][i] <= y ){
x = d2[x][i];
}
}
return x;
}
int ff1( int x , int y )
{
for( int i = 24; i >= 0; i-- ){
if( d1[x][i] >= y ){
x = d1[x][i];
}
}
return x;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,
vector<int> L, vector<int> R)
{
n = N;
m = (int)X.size();
q = (int)S.size();
for( int i = 1; i <= n; i++ ){
p[i] = i;
}
for( int i = 0; i < m; i++ ){
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
for( int i = 0; i < n; i++ ){
for( auto x : v[i] ){
if( x > i )continue;
meg( x , i );
}
}
dfs( n - 1 , n - 1 );
for( int i = 0; i <= n; i++ ){
tin2[i] = tin1[i];
tout2[i] = tout1[i];
o2[i] = o1[i];
g[i].clear();
p[i] = i;
for( int j = 0; j < 25; j++ ){
d2[i][j] = d1[i][j];
}
}
tim = 0;
for( int i = n - 1; i >= 0; i-- ){
for( auto x : v[i] ){
if( x < i )continue;
meg( x , i );
}
}
dfs( 0 , 0 );
for( int i = 0; i < q; i++ ){
gg[R[i]].push_back({L[i] , i});
}
build( 1 , 1 , n );
vector < int > ans(q , -1);
for( int i = 0; i < n; i++ ){
for( auto x : gg[i] ){
int yy = ff( E[x.se] , i );
int y = ff1( S[x.se] , x.fi );
ans[x.se] = get1( 1 , 1 , n , tin2[yy] , tout2[yy] , tin1[y] , tout1[y] );
}
}
return ans;
}
