#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 400005;
int n, m, qq;
vector<int> g[N];
void dfs00(int x, int ul, int ur, vector<bool>& c)
{
if (!(ul <= x && x <= ur))
return;
if (c[x])
return;
c[x] = true;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
dfs00(h, ul, ur, c);
}
}
vector<int> solv0(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)
{
vector<int> ans;
for (int i = 0; i < qq; ++i)
{
vector<bool> cs, ce;
cs.assign(n, false);
ce.assign(n, false);
dfs00(S[i], L[i], n - 1, cs);
dfs00(E[i], 0, R[i], ce);
for (int x = 0; x < n; ++x)
{
if (cs[x] && ce[x])
{
ans.push_back(1);
break;
}
}
if (sz(ans) != (i + 1))
ans.push_back(0);
}
return ans;
}
int p0[N];
int fi(int x)
{
if (x == p0[x])
return x;
return p0[x] = fi(p0[x]);
}
vector<vector<int> > g1, g2;
int tin1[N], tout1[N], ti1;
int tin2[N], tout2[N], ti2;
const int k = 20;
int p1[N][k], p2[N][k];
void dfs0(int x, int p0, vector<vector<int> >& g, int tin[], int tout[], int& ti, int p[][k])
{
tin[x] = ++ti;
p[x][0] = p0;
for (int i = 1; i < k; ++i)
p[x][i] = p[p[x][i - 1]][i - 1];
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
dfs0(h, x, g, tin, tout, ti, p);
}
tout[x] = ti;
}
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)
{
n = N_;
m = sz(X);
qq = sz(S);
for (int i = 0; i < m; ++i)
{
int x = X[i];
int y = Y[i];
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> ans;
g1.resize(n);
g2.resize(n);
for (int x = 0; x < n; ++x)
p0[x] = x;
vector<pair<int, int> > v;
for (int i = 0; i < m; ++i)
{
if (X[i] > Y[i])
swap(X[i], Y[i]);
v.push_back(m_p(X[i], Y[i]));
}
sort(all(v));
reverse(all(v));
for (int i = 0; i < m; ++i)
{
int x = v[i].fi;
int y = v[i].se;
x = fi(x);
y = fi(y);
if (x == y)
continue;
g1[x].push_back(y);
p0[y] = x;
}
for (int x = 0; x < n; ++x)
p0[x] = x;
v.clear();
for (int i = 0; i < m; ++i)
{
swap(X[i], Y[i]);
v.push_back(m_p(X[i], Y[i]));
}
sort(all(v));
for (int i = 0; i < m; ++i)
{
int x = v[i].fi;
int y = v[i].se;
x = fi(x);
y = fi(y);
if (x == y)
continue;
g2[x].push_back(y);
p0[y] = x;
}
dfs0(0, 0, g1, tin1, tout1, ti1, p1);
dfs0(n - 1, n - 1, g2, tin2, tout2, ti2, p2);
for (int ii = 0; ii < qq; ++ii)
{
int x = S[ii];
int y = E[ii];
int l = L[ii];
int r = R[ii];
while (x != 0 && p1[x][0] >= l)
x = p1[x][0];
while (y != n - 1 && p2[y][0] <= r)
y = p2[y][0];
for (int u = 0; u < n; ++u)
{
if (tin1[x] <= tin1[u] && tin1[u] <= tout1[x])
{
if (tin2[y] <= tin2[u] && tin2[u] <= tout2[y])
{
ans.push_back(1);
break;
}
}
}
if (sz(ans) == ii)
ans.push_back(0);
}
//if (ans != solv0(N_, X, Y, S, E, L, R))
// printf("WA\n");
return ans;
}
