#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"
using namespace std ;
const int MAX = 2e5 + 10 ;
int n , m , q ;
int par[MAX] ;
int par2[MAX] ;
int P[MAX][20] , P2[MAX][20] ;
vector< vector<int> >adj(MAX) , adj1(MAX) , adj2(MAX) ;
void init()
{
for(int i = 1 ; i <= n ; ++i)
par[i] = par2[i] = i ;
}
int root(int node)
{
if(par[node] == node)
return node ;
return (par[node] = root(par[node])) ;
}
void Union(int x , int y)
{
int a = root(x) ;
int b = root(y) ;
if(a < b)
swap(a , b) ;
par[b] = a , P[b][0] = a ;
adj1[a].push_back(b) ;
}
int root2(int node)
{
if(par2[node] == node)
return node ;
return (par2[node] = root2(par2[node])) ;
}
void Union2(int x , int y)
{
int a = root2(x) ;
int b = root2(y) ;
if(a > b)
swap(a , b) ;
par2[b] = a , P2[b][0] = a ;
adj2[a].push_back(b) ;
}
int in[MAX] , out[MAX] ;
int tim = 0 ;
void dfs1(int node)
{
in[node] = ++tim ;
for(int j = 1 ; j < 18 ; ++j)
P[node][j] = P[P[node][j-1]][j-1] ;
for(auto &child : adj1[node])
dfs1(child) ;
out[node] = tim ;
}
int sz[MAX] ;
void dfs2(int node)
{
for(int j = 1 ; j < 18 ; ++j)
P2[node][j] = P2[P2[node][j-1]][j-1] ;
sz[node] = 1 ;
for(auto &child : adj2[node])
{
dfs2(child) ;
sz[node] += sz[child] ;
}
}
void preprocess()
{
init() ;
for(int i = 0 ; i < n ; ++i)
{
for(auto &child : adj[i])
{
if(child < i && root(child) != root(i))
Union(child , i) ;
}
}
for(int i = n-1 ; i >= 0 ; --i)
{
for(auto &child : adj[i])
{
if(child > i && root2(child) != root2(i))
Union2(child , i) ;
}
}
P[n-1][0] = n-1 ;
dfs1(n-1) ;
dfs2(0) ;
}
int get(int node , int node2)
{
for(int j = 17 ; j >= 0 ; --j)
{
if(P[node][j] <= node2)
node = P[node][j] ;
}
return node ;
}
int get2(int node , int node2)
{
for(int j = 17 ; j >= 0 ; --j)
{
if(P2[node][j] >= node2)
node = P2[node][j] ;
}
return node ;
}
set<int>s[MAX] ;
vector< pair<int , int> >queries[MAX] ;
vector<int>ans ;
void dfs3(int node)
{
int big = -1 , bigchild = -1 ;
for(auto &child : adj2[node])
{
if(sz[child] > big)
big = sz[child] , bigchild = child ;
}
for(auto &child : adj2[node])
dfs3(child) ;
if(bigchild != -1)
swap(s[node] , s[bigchild]) ;
s[node].insert(in[node]) ;
for(auto &child : adj2[node])
{
if(child == bigchild)
continue ;
for(auto &i : s[child])
s[node].insert(i) ;
s[child].clear() ;
}
for(auto &p : queries[node])
{
int l = in[p.first] , r = out[p.first] ;
auto it = s[node].lower_bound(l) ;
if(it == s[node].end())
ans[p.second] = 0 ;
else if((*it) > r)
ans[p.second] = 0 ;
else
ans[p.second] = 1 ;
}
}
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)
{
n = N , m = X.size() , q = S.size() ;
for(int i = 0 ; i < m ; ++i)
adj[X[i]].push_back(Y[i]) , adj[Y[i]].push_back(X[i]) ;
preprocess() ;
for(int i = 0 ; i < q ; ++i)
queries[get2(S[i] , L[i])].emplace_back(get(E[i] , R[i]) , i) ;
ans = vector<int>(q) ;
dfs3(0) ;
return ans ;
}
