#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
vector<int>graf[maxn];
int father1[maxn], father2[maxn], ojciec1[maxn], ojciec2[maxn];
int find1(int x){
if(father1[x] == x)return x;
return father1[x] = find1(father1[x]);
}
int find2(int x){
if(father2[x] == x)return x;
return father2[x] = find2(father2[x]);
}
int pre[maxn], post[maxn], preit = -1;
vector<int>graf2[maxn], graf1[maxn];
void dfs(int x){
pre[x] = ++preit;
for(auto j: graf1[x])
dfs(j);
post[x] = preit;
}
int jump1[maxn][19], jump2[maxn][19];
vector<int> A;
int ustawione[maxn];
vector<pair<pair<int,int>, int>>przedzialy[maxn];
const int base = 1<<18;
vector<int>tree[2*base];
void dodaj(int w, int l, int p, int a, int b, int index){
if(l>b || p<a)return;
if(a<=l && p<=b){
tree[w].push_back(index);
return;
}
dodaj(w*2, l, (l+p)/2, a, b, index);
dodaj(w*2+1, (l+p)/2+1, p, a, b, index);
}
void usun(int x){
x+=base;
while(x>0){
while(tree[x].size()){
if(ustawione[tree[x].back()]==1)tree[x].pop_back();
else{
A[tree[x].back()] = 1;
ustawione[tree[x].back()] = 1;
tree[x].pop_back();
}
}
x/=2;
}
}
void dfs2(int x){
for(auto j: przedzialy[x]){
dodaj(1, 0, base-1, j.first.first, j.first.second, j.second);
}
usun(pre[x]);
for(auto j: graf2[x])
dfs2(j);
for(auto j: przedzialy[x]){
ustawione[j.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) {
int i;
for(i=0;i<(int)X.size();i++){
graf[Y[i]].push_back(X[i]);
graf[X[i]].push_back(Y[i]);
}
for(i=0;i<n;i++)
ojciec1[i] = n, ojciec2[i] = -1, father1[i] = father2[i] = i;
for(i=0;i<n;i++){
for(auto j: graf[i])
if(j<i){
if(find1(j) != i)ojciec1[find1(j)] = i;
father1[find1(j)] = i;
}
}
for(i=n-1;i>=0;i--)
for(auto j: graf[i])
if(j>i){
if(find2(j) != i)ojciec2[find2(j)] = i;
father2[find2(j)] = i;
}
for(i=0;i<n;i++){
graf1[ojciec1[i]].push_back(i);
graf2[ojciec2[i]].push_back(i);
}
// for(i=0;i<n;i++)printf("%d ", ojciec1[i]);printf("\n");
// for(i=0;i<n;i++)printf("%d ", ojciec2[i]);printf("\n");
// return {};
for(i=0;i<n;i++){
jump1[i][0] = ojciec1[i];
if(jump1[i][0] == n)jump1[i][0] = i;
}
for(i=0;i<n;i++){
jump2[i][0] = ojciec2[i];
if(jump2[i][0] == -1)jump2[i][0] = i;
}
for(int j=1;j<18;j++)
for(int i=0;i<n;i++){
jump1[i][j] = jump1[jump1[i][j-1]][j-1];
jump2[i][j] = jump2[jump2[i][j-1]][j-1];
}
dfs(n);
// for(i=0;i<n;i++)printf("%d ", pre[i]);printf("\n");
// for(i=0;i<n;i++)printf("%d ", post[i]);printf("\n");
int q = S.size();
A.resize(q, 0);
for (int i = 0; i < q; ++i) {
if(E[i]>R[i] || S[i]<L[i])continue;
int pom1 = E[i], pom2 = S[i];
for(int j = 17;j>=0;j--){
// printf("%d %d\n", pom1, pom2);
if(jump1[pom1][j]<=R[i])
pom1 = jump1[pom1][j];
if(jump2[pom2][j]>=L[i])
pom2 = jump2[pom2][j];
}
// pocz = pre[pom1], kon = post[pom1], it = i;
// dfs2(pom2);
// printf("%d: %d %d %d %d\n", i, pom1, pom2, pocz, kon);
przedzialy[pom2].push_back({{pre[pom1], post[pom1]},i});
}
preit = 0;
for(i=0;i<n;i++)
if(ojciec2[i]==-1)
dfs2(i);
return A;
}
