#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 2e5 + 20;
const int maxb = 20;
vector<int> adj[maxn] , tree[2][maxn] , query[maxn];
int px[maxn] , par[2][maxn][maxb] , st[2][maxn] , ft[2][maxn] , id , rst[2][maxn];
int l1[maxn] , r1[maxn] , l2[maxn] , r2[maxn];
int root(int v)
{
return px[v] < 0? v : px[v] = root(px[v]);
}
void dfs(int v , int b , int p = -1)
{
if(p == -1)
{
for(int i = 0; i < maxb; i++)
par[b][v][i] = v;
id = -1;
}
st[b][v] = ++id;
rst[b][id] = v;
for(auto u : tree[b][v])
{
par[b][u][0] = v;
for(int i = 1; i < maxb; i++)
par[b][u][i] = par[b][par[b][u][i - 1]][i - 1];
dfs(u , b , v);
}
ft[b][v] = id;
}
int n , mx[maxn * 4];
void upd(int p , int val , int s = 0 , int e = n , int v = 1)
{
if(e - s < 2)
{
mx[v] = val;
return;
}
int m = (s + e) / 2;
if(p < m)
upd(p , val , s , m , 2 * v);
else
upd(p , val , m , e , 2 * v + 1);
mx[v] = max(mx[2 * v] , mx[2 * v + 1]);
}
int get(int l , int r , int s = 0 , int e = n , int v = 1)
{
if(l <= s && e <= r)
return mx[v];
if(r <= s || e <= l)
return -1;
int m = (s + e) / 2;
return max(get(l , r , s , m , 2 * v) , get(l , r , m , e , 2 * v + 1));
}
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;
for(int i = 0; i < (int)X.size(); i++)
{
int a = X[i] , b = Y[i];
adj[a].pb(b);
adj[b].pb(a);
}
memset(px , -1 , sizeof px);
for(int v = 0; v < n; v++)
for(auto u : adj[v])
if(u < v)
{
u = root(u);
if(u != v)
tree[0][v].pb(u) , px[u] = v;
}
memset(px , -1 , sizeof px);
for(int v = n - 1; v >= 0; v--)
for(auto u : adj[v])
if(u > v)
{
u = root(u);
if(u != v)
tree[1][v].pb(u) , px[u] = v;
}
dfs(n - 1 , 0) , dfs(0 , 1);
int q = S.size();
for(int i = 0; i < q; i++)
{
int s = S[i] , e = E[i];
for(int j = maxb - 1; j >= 0; j--)
if(par[0][e][j] <= R[i])
e = par[0][e][j];
for(int j = maxb - 1; j >= 0; j--)
if(par[1][s][j] >= L[i])
s = par[1][s][j];
l1[i] = st[0][e] , r1[i] = ft[0][e];
l2[i] = st[1][s] , r2[i] = ft[1][s];
query[r1[i]].pb(i);
}
memset(mx , -1 , sizeof mx);
vector<int> ans(q);
for(int i = 0; i < n; i++)
{
int v = rst[0][i];
upd(st[1][v] , i);
for(auto ind : query[i])
ans[ind] = get(l2[ind] , r2[ind] + 1) >= l1[ind];
}
return ans;
}
