#include "werewolf.h"
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#define vi vector<int>
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define ppt pair<ppp, int>
#define fst first
#define snd second
using namespace std;
const int LG = 18;
int N, M, Q, par[200001], lf[200001], rg[200001], t = 0;
ppt A[200001];
vi adj[200001], tr[200001];
set<int> dt[200001];
int sps[200001][LG];
int find(int x) {return par[x] = (par[x] == x) ? x : find(par[x]);}
inline void join(int a, int b, int t)
{
//cerr << "J: " << a << " " << b << "\n";
a = find(a), b = find(b);
if (a != b)
{
if (t)
{
if (dt[a].size() < dt[b].size()) swap(a, b);
par[b] = a;
while (dt[b].size())
{
dt[a].insert(*dt[b].begin());
dt[b].erase(dt[b].begin());
}
}
else
{
par[b] = a;
//cerr << a << " -> " << b << "\n";
tr[a].push_back(b);
}
}
}
void DFS(int u, int p)
{
sps[u][0] = p;
//cerr << u << " " << p << "\n";
for (int i = 1; i < LG; i++)
{
if (sps[u][i - 1] == -1) sps[u][i] = -1;
else sps[u][i] = sps[sps[u][i - 1]][i - 1];
}
lf[u] = t++;
for (const auto &v : tr[u]) DFS(v, u);
rg[u] = t - 1;
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R)
{
::N = N; M = X.size(); Q = S.size();
vi ret(Q, 0);
for (int i = 0; i < N; i++) par[i] = i;
for (int i = 0; i < M; i++)
{
if (X[i] > Y[i]) swap(X[i], Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int u = 1; u < N; u++)
{
for (const auto &v : adj[u]) join(u, v, 0);
}
for (int u = 0; u < N; u++)
{
if (par[u] == u) DFS(u, -1);
adj[u].clear();
}
for (int i = 0; i < M; i++) {adj[X[i]].push_back(Y[i]);}
for (int i = 0; i < Q; i++)
{
A[i].fst.fst = {L[i], R[i]}; A[i].fst.snd = {S[i], E[i]};
A[i].snd = i;
}
sort(A, A + Q);
int j = Q - 1;
for (int i = N - 1; i >= 0; i--)
{
dt[i].insert(lf[i]); par[i] = i;
for (const auto &v : adj[i])
{
//cerr << "J1: " << i << " " << v << "\n";
join(i, v, 1);
}
for (; j >= 0 && A[j].fst.fst.fst >= i; j--)
{
int r = A[j].fst.fst.snd, s = A[j].fst.snd.fst, e = A[j].fst.snd.snd, id = A[j].snd;
for (int k = LG - 1; k >= 0; k--)
{
if (sps[e][k] == -1) continue;
else if (sps[e][k] <= r) {e = sps[e][k];}
}
s = find(s);
auto it = dt[s].lower_bound(lf[e]);
ret[id] = (it != dt[s].end() && *it <= rg[e]);
}
}
return ret;
}
