#include "werewolf.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }
const ll INF = 1e18;
const int LOG = 20;
struct SegTree {
vector<vll> st;
ll n;
SegTree () {}
SegTree (ll n):n(n), st(4*n+4) {}
void build (vll &a) { build(1, 0, n-1, a); }
void build (ll id, ll l, ll r, vll &a) {
fore (i, l, r+1) st[id].pb(a[i]);
sort(all(st[id]));
if (l == r) return;
ll m = (l+r)/2;
build(id*2, l, m, a);
build(id*2+1, m+1, r, a);
}
ll query (ll l, ll r, ll a, ll b) { return query(1, 0, n-1, l, r, a, b); }
ll query (ll id, ll l, ll r, ll i, ll j, ll a, ll b){
if(l>j || r<i) return 0;
if(l>=i && r<=j) {
b = upper_bound(all(st[id]), b) - st[id].begin();
a = lower_bound(all(st[id]), a) - st[id].begin();
return b - a;
}
ll m = (l+r)/2;
return query(id*2, l, m, i, j, a, b) + query(id*2+1, m+1, r, i, j, a, b);
}
};
struct DSU {
vector<vll> graph, up;
vll pa, tin, tout;
ll n, tr;
DSU (ll n): n(n), tr(0), pa(n), graph(n), up(n, vll(LOG)), tin(n, 0), tout(n, 0) { iota(all(pa), 0); }
ll find (ll i) { return (i == pa[i] ? i : pa[i] = find(pa[i])); }
void unite (ll a, ll b) {
a = find(a);
b = find(b);
if (a == b) return;
graph[a].pb(b);
pa[b] = a;
}
void dfs (ll u, ll p) {
up[u][0] = p;
fore (i, 1, LOG) {
up[u][i] = up[up[u][i-1]][i-1];
}
tin[u] = tr++;
for (ll v: graph[u]) {
if (v == p) continue;
dfs(v, u);
}
tout[u] = tr-1;
}
void build (vll &ottin, vll &a) {
fo (i, n) a[i] = INF;
fo (i, n/2) {
a[tin[i]] = ottin[i];
}
}
void print () {
cout << "Tree\n";
fo (x, n) {
for (ll v: graph[x]) {
cout << x << ' ' << v << '\n';
}
}
cout << "Tour\n";
fo (x, n) cout << tin[x] << ' ' << tout[x] << '\n';
}
};
vector<vll> graph;
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(), m = X.size();
graph = vector<vll>(n);
fo (i, m) {
graph[X[i]].pb(Y[i]);
graph[Y[i]].pb(X[i]);
}
DSU hum(2*n), wolf(2*n);
SegTree st(2*n);
ffo (x, n-1) {
// x+n es el nuevo padre
hum.unite(x+n, x);
for (ll y: graph[x]) {
if (y < x) continue;
hum.unite(x+n, y);
}
}
fore (x, 1, n) {
wolf.unite(x+n, x);
for (ll y: graph[x]) {
if (y > x) continue;
wolf.unite(x+n, y);
}
}
hum.dfs(n, n);
wolf.dfs(2*n-1, 2*n-1);
vll a(2*n);
hum.build(wolf.tin, a);
st.build(a);
vector<int> ans(Q, 0);
fo (qi, Q) {
ll A = S[qi], B = E[qi];
ffo (i, LOG) {
if (hum.up[A][i] >= L[qi]+n)
A = hum.up[A][i];
}
ffo (i, LOG) {
if (wolf.up[B][i] <= R[qi]+n)
B = wolf.up[B][i];
}
ans[qi] = ((st.query(hum.tin[A], hum.tout[A], wolf.tin[B], wolf.tout[B])) >= 1);
}
return ans;
}
