#include "werewolf.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 200'010;
const int lg = 18;
const int M = 400'010;
struct {
int par[N];
set<int> ppar[N];
int rt(int v) {return par[v]==-1? v: (par[v] = rt(par[v]));}
void unite(int v, int u)
{
u = rt(u);
assert(v == rt(v));
assert(v >= u);
if (v == u)
return;
par[u] = v;
assert(ppar[u].size() && *ppar[u].begin() == v);
ppar[u].erase(ppar[u].begin());
if (ppar[v].size() < ppar[u].size())
ppar[v].swap(ppar[u]);
for (int x : ppar[u]) {
ppar[v].insert(x);
}
{ set<int> tmp; ppar[u].swap(tmp); }
}
void init()
{
Loop (i,0,N) {
par[i] = -1;
{ set<int> tmp; ppar[i].swap(tmp); }
}
}
void up(int v, int x)
{
assert(v == rt(v));
assert(x > v);
ppar[v].insert(x);
}
} dsul, dsur;
struct {
vector<int> A[N];
int par[N][lg];
int l[N], r[N];
void dfs(int v, int p, vector<int> &ord)
{
l[v] = ord.size();
ord.push_back(v);
par[v][0] = p;
Loop (i,0,lg-1)
par[v][i+1] = par[par[v][i]][i];
for (int u : A[v])
if (u != p)
dfs(u, v, ord);
r[v] = ord.size();
}
int get_anc(int v, int r)
{
LoopR (i,0,lg) {
if (par[v][i] < r)
v = par[v][i];
}
return v;
}
} dfsl, dfsr;
namespace seg
{
struct node {
int l, r;
int x;
} nodes[256'000'000/sizeof(node)];
int next = 1;
int new_node(int l, int r)
{
nodes[next].l = l;
nodes[next].r = r;
nodes[next].x = nodes[l].x + nodes[r].x;
return next++;
}
int new_node(int x)
{
nodes[next].l = nodes[next].r = 0;
nodes[next].x = x;
return next++;
}
int up(int t, int p, int b=0, int e=N)
{
if (e - b == 1)
return new_node(nodes[t].x + 1);
if (p < (b+e)/2)
return new_node(up(nodes[t].l, p, b, (b+e)/2), nodes[t].r);
else
return new_node(nodes[t].l, up(nodes[t].r, p, (b+e)/2, e));
}
int get(int t1, int t2, int l, int r, int b=0, int e=N)
{
//cout << l << ' ' << r << " !" << endl;
//cout << b << ' ' << e << " !" << endl;
//cout << nodes[t2].x - nodes[t1].x << endl;
if (l <= b && e <= r)
return nodes[t2].x - nodes[t1].x;
if (r <= b || e <= l)
return 0;
return get(nodes[t1].l,nodes[t2].l,l,r,b,(b+e)/2)
+ get(nodes[t1].r,nodes[t2].r,l,r,(b+e)/2,e);
}
int init(int b=0, int e=N)
{
if (e-b == 1)
return new_node(1);
return new_node(init(b,(b+e)/2),init((b+e)/2,e));
}
int rt[N];
}
vector<int> A[N];
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 m = x.size();
Loop (i,0,m) {
A[x[i]].push_back(y[i]);
A[y[i]].push_back(x[i]);
}
dsur.init();
Loop (v,0,n) {
for (int u : A[v]) {
if (u < v)
dsur.unite(v, u);
}
for (int u : A[v]) {
if (u > v)
dsur.up(v, u);
}
assert(v == n-1 || dsur.ppar[v].size());
if (dsur.ppar[v].size()) {
dfsr.A[*dsur.ppar[v].begin()].push_back(v);
}
}
dsul.init();
LoopR (v,0,n) {
for (int u : A[v]) {
if (u > v)
dsul.unite(n - v, n - u);
}
for (int u : A[v]) {
if (u < v)
dsul.up(n - v, n - u);
}
assert(v == 0 || dsul.ppar[n - v].size());
if (dsul.ppar[n - v].size()) {
dfsl.A[*dsul.ppar[n - v].begin()].push_back(n - v);
}
}
vector<int> v1, v2, v3(n);
dfsr.dfs(n-1, n-1, v1);
dfsl.dfs(n, n, v2);
//cout << "hi" << endl;
for (int &x : v2) x = n-x;
//Loop (i,0,n) cout << v1[i] << ' '; cout << endl;
//Loop (i,0,n) cout << v2[i] << ' '; cout << endl;
assert(v1.size() == n);
assert(v2.size() == n);
Loop (i,0,n) v3[v1[i]] = i;
Loop (i,0,n) v2[i] = v3[v2[i]];
//Loop (i,0,n) cout << v2[i] << ' '; cout << endl;
//cout << "hi" << endl;
seg::rt[0] = seg::init();
//cout << "hi" << endl;
Loop (i,0,n)
seg::rt[i+1] = seg::up(seg::rt[i], v2[i]);
//cout << "hi" << endl;
vector<int> ans(s.size());
Loop (i,0,s.size()) {
//cout << l[i] << ' ' << r[i] << endl;
//cout << s[i] << ' ' << e[i] << endl;
e[i] = dfsr.get_anc(e[i], r[i]+1);
s[i] = dfsl.get_anc(n-s[i], n-l[i]+1);
//cout << n-s[i] << ' ' << e[i] << endl;
int t1 = dfsl.l[s[i]];
int t2 = dfsl.r[s[i]];
int l = dfsr.l[e[i]];
int r = dfsr.r[e[i]];
//cout << t1 << ' ' << t2 << endl;
//cout << l << ' ' << r << endl;
ans[i] = !!seg::get(seg::rt[t1], seg::rt[t2], l, r);
//cout << "--" << endl;
}
return ans;
}
