#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int const MAX = 2e5 + 5;
vector<int> sons[2 * MAX];
set<int> nodes[MAX];
int n;
vector<int> qL[MAX], qR[MAX];
vector<int> G[MAX];
int nod_inter[MAX];
int st[2 * MAX], dr[2 * MAX];
struct UFD
{
int tata[2 * MAX];
int id;
void init()
{
int i;
for (i = 0; i < 2 * n; ++i)
tata[i] = i;
id = n - 1;
}
int root(int nod)
{
if (tata[nod] == nod)
return nod;
return tata[nod] = root(tata[nod]);
}
void uneste1(int u, int v)
{
u = root(u);
v = root(v);
if (u != v)
{
++id;
sons[id].push_back(u);
sons[id].push_back(v);
tata[u] = id;
tata[v] = id;
}
}
void uneste2(int u, int v)
{
u = root(u);
v = root(v);
if (u != v)
{
if (nodes[u].size() < nodes[v].size())
swap(u, v);
tata[v] = u;
for (auto elem : nodes[v])
nodes[u].insert(elem);
nodes[v].clear();
}
}
} ufd;
void dfs(int nod)
{
static int time = 0;
st[nod] = time;
for (auto fiu : sons[nod])
dfs(fiu);
if (sons[nod].empty())
++time;
dr[nod] = time - 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)
{
int q = S.size();
int m = X.size();
n = N;
int i;
for (i = 0; i < q; ++i)
{
qL[L[i]].push_back(i);
qR[R[i]].push_back(i);
}
for (i = 0; i < m; ++i)
{
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
ufd.init();
for (i = n - 1; i >= 0; --i)
{
for (auto vec : G[i])
if (vec > i)
ufd.uneste1(i, vec);
for (auto qry : qL[i])
nod_inter[qry] = ufd.root(S[qry]);
}
dfs(ufd.id);
ufd.init();
for (i = 0; i < n; ++i)
nodes[i].insert(st[i]);
vector<int> ans(q);
for (i = 0; i < n; ++i)
{
for (auto vec : G[i])
if (vec < i)
ufd.uneste2(vec, i);
for (auto qry : qR[i])
{
int pos = E[qry];
int rt = ufd.root(pos);
int intv = nod_inter[qry];
auto it = nodes[rt].lower_bound(st[intv]);
if (it != nodes[rt].end() && *it <= dr[intv])
ans[qry] = 1;
else
ans[qry] = 0;
}
}
return ans;
}
