#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct MergeTree {
int p[MAXN], s[MAXN], lebal[MAXN];
int cur_node;
vector<int> adj[MAXN];
void init(int n){
cur_node = n;
for (int i = 0; i < n; i++){
p[i] = i;
s[i] = 1;
lebal[i] = i;
}
}
int find(int u){
if (p[u] == u) return u;
return p[u] = find(p[u]);
}
void merge(int u, int v){
u = find(u);
v = find(v);
if (u == v) return;
adj[cur_node].pb(lebal[u]);
adj[cur_node].pb(lebal[v]);
adj[lebal[u]].pb(cur_node);
adj[lebal[v]].pb(cur_node);
if (s[u] < s[v]) swap(u, v);
s[u] += s[v];
p[v] = u;
lebal[u] = cur_node++;
}
int st[MAXN], ft[MAXN], timer = 1;
int mn[MAXN], mx[MAXN]; // for humans I need min, for werewolf max
int fa[MAXN][20];
void dfs(int node, int par){
st[node] = timer++;
fa[node][0] = par;
for (int b = 1; b < 20; b++){
fa[node][b] = fa[fa[node][b - 1]][b - 1];
}
if (sz(adj[node]) == 1 && adj[node][0] == par){
mx[node] = node;
mn[node] = node;
}
for (auto to : adj[node]){
if (to != par){
dfs(to, node);
ckmax(mx[node], mx[to]);
ckmin(mn[node], mn[to]);
}
}
ft[node] = timer++;
}
void get_dfs_order(){
cur_node--;
for (int i = 0; i <= cur_node; i++){
mn[i] = inf;
mx[i] = -inf;
}
dfs(cur_node, cur_node);
}
pii find_range(int u, int time, bool human){
for (int b = 19; b >= 0; b--){
if (human && mn[fa[u][b]] >= time){
u = fa[u][b];
}
if (!human && mx[fa[u][b]] <= time){
u = fa[u][b];
}
}
return {st[u], ft[u]};
}
void dbg(){
cout << "HERE\n";
for (int i = 0; i <= cur_node; i++){
cout << i << ' ' << st[i] << ' ' << ft[i] << ' ' << mn[i] << ' ' << mx[i] << endl;
}
}
} human, werewolf;
const int off = (1<<20);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
int t[off<<1];
void update(int idx, int u){
t[idx+=off] += u;
while (idx/=2)
t[idx] = t[ls] + t[rs];
}
int get(int l, int r, int idx=1, int lo=0, int hi=off){
if (r <= lo || hi <= l)
return 0;
if (l <= lo && hi <= r)
return t[idx];
int mi = (lo+hi)>>1;
return get(l, r, ls, lo, mi)+get(l, r, rs, mi, hi);
}
} seg;
vector<int> adj[MAXN];
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 m = sz(X);
int Q = S.size();
for (int i = 0; i < m; i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
werewolf.init(n);
for (int i = 0; i < n; i++){
// I want to caclute component for werewolf for L <= i
for (auto u : adj[i]){
if (u <= i){
werewolf.merge(i, u);
}
}
}
human.init(n);
for (int i = n - 1; i >= 0; i--){
// I want to caclute component for werewolf for L <= i
for (auto u : adj[i]){
if (u >= i){
human.merge(i, u);
}
}
}
werewolf.get_dfs_order();
human.get_dfs_order();
//werewolf.dbg();
//human.dbg();
vector<int> add[MAXN];
for (int i = 0; i < n; i++){
add[human.st[i]].pb(werewolf.st[i]);
}
vector<array<int, 4>> Queries[MAXN]; // type, bot, top, idx
for (int i = 0; i < Q; i++){
pii hr = human.find_range(S[i], L[i], 1);
pii wr = werewolf.find_range(E[i], R[i], 0);
Queries[hr.F - 1].pb({-1, wr.F, wr.S, i});
Queries[hr.S].pb({1, wr.F, wr.S, i});
}
vector<int> ans(Q);
for (int i = 0; i < MAXN; i++){
for (auto pos : add[i]){
seg.update(pos, 1);
}
for (auto [type, bot, top, idx] : Queries[i]){
ans[idx] += type * seg.get(bot, top);
}
}
for (int i = 0; i < Q; ++i) {
ans[i] = !!ans[i];
}
return ans;
}
