#include "werewolf.h"
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const lgmax = 20;
class Dsu{
public:
std::vector<int> mult;
Dsu(int n) {
mult.resize(n);
for(int i = 0; i < n; i++)
mult[i] = i;
}
int jump(int gala) {
if(mult[gala] != gala)
mult[gala] = jump(mult[gala]);
return mult[gala];
}
void unite(int gala, int galb) {
gala = jump(gala);
galb = jump(galb);
mult[galb] = gala;
}
};
class SegmentTree{
private:
std::vector<std::vector<int>> aint;
public:
SegmentTree(int n) {
aint.resize(1 + 4 * n);
}
void build(int node, int from, int to, std::vector<int> &aux) {
if(from < to) {
int mid = (from + to) / 2;
build(node * 2, from, mid, aux);
build(node * 2 + 1, mid + 1, to, aux);
aint[node].resize(to - from + 1);
std::merge(aint[node * 2].begin(), aint[node * 2].end(),
aint[node * 2 + 1].begin(), aint[node * 2 + 1].end(),
aint[node].begin());
} else
aint[node].push_back(aux[from]);
}
bool check_node(int node, int l, int r) {
std::vector<int>::iterator it = std::lower_bound(aint[node].begin(), aint[node].end(), l);
if(it == aint[node].end() || r < *it)
return false;
return true;
}
bool check(int node, int from, int to, int x, int y, int l, int r) {
if(from == x && to == y)
return check_node(node, l, r);
else {
int mid = (from + to) / 2;
if(x <= mid && y <= mid)
return check(node * 2, from, mid, x, y, l, r);
else if(mid + 1 <= x && mid + 1 <= y)
return check(node * 2 + 1, mid + 1, to, x, y, l, r);
else
return (check(node * 2, from, mid, x, mid, l, r) |
check(node * 2 + 1, mid + 1, to, mid + 1, y, l, r));
}
}
};
std::vector<std::vector<int>> g1, g2;
void dfs(int node, std::vector<std::vector<int>> &g, std::vector<std::vector<int>> &far,
std::vector<int> &start, std::vector<int> &stop, std::vector<int> &level, int &ptr) {
start[node] = ptr++;
for(int h = 0; h < g[node].size();h++) {
int to = g[node][h];
far[0][to] = node;
level[to] = level[node] + 1;
dfs(to, g, far, start, stop, level, ptr);
}
stop[node] = ptr - 1;
}
void computefar(std::vector<std::vector<int>> &far, int n) {
for(int i = 1;i < far.size(); i++) {
far[i].resize(n);
for(int j = 0; j < n; j++)
far[i][j] = far[i - 1][far[i - 1][j]];
}
}
std::vector<std::vector<int>> far, far2;
int expand(int node, std::vector<int> level, std::vector<std::vector<int>> &far, int l, int r) {
for(int h = far.size() - 1; 0 <= h; h--)
if((1 << h) <= level[node]) {
if(l <= far[h][node] && far[h][node] <= r)
node = far[h][node];
}
return node;
}
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) {
std::vector<std::vector<int>> g(N);
for(int i = 0; i < X.size(); i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
Dsu dsu(N);
g1.resize(N);
g2.resize(N);
for(int i = 0; i < N; i++) {
for(int h = 0; h < g[i].size(); h++) {
int to = dsu.jump(g[i][h]);
if(to < i) {
g1[i].push_back(to);
dsu.unite(i, to);
}
}
}
dsu = Dsu(N);
for(int i = N - 1; 0 <= i; i--) {
for(int h = 0; h < g[i].size(); h++) {
int to = dsu.jump(g[i][h]);
if(i < to) {
g2[i].push_back(to);
dsu.unite(i, to);
}
}
}
int n = N;
far.resize(1 + lgmax);
far2.resize(1 + lgmax);
far[0].resize(n);
far2[0].resize(n);
std::vector<int> start(n), stop(n), start2(n), stop2(n), level(n), level2(n);
int ptr = 0;
dfs(0, g2, far2, start2, stop2, level2, ptr);
ptr = 0;
dfs(N - 1, g1, far, start, stop, level, ptr);
computefar(far, n);
computefar(far2, n);
std::vector<int> aux(N);
for(int i = 0; i < N; i++)
aux[start[i]] = start2[i];
SegmentTree aint(N);
aint.build(1, 0, N - 1, aux);
std::vector<int> sol(S.size());
for(int h = 0; h < S.size(); h++) {
int f2 = expand(S[h], level2, far2, L[h], N - 1);
int f1 = expand(E[h], level, far, 0, R[h]);
sol[h] = aint.check(1, 0, N - 1, start[f1], stop[f1], start2[f2], stop2[f2]);
}
return sol;
}
