// The other code was too messy, testing the new brute (with binary lifting)
#include "werewolf.h"
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
using pii = pair<int,int>;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ff first
#define ss second
constexpr int maxn = 4e5+10, logn = 20;
int n;
struct DSU
{
int pai[maxn];
DSU() { for(int i = 0; i < maxn; i++) pai[i] = i; }
void init() { for(int i = 0; i < maxn; i++) pai[i] = i; }
int find(int x) { return pai[x]==x?x:pai[x]=find(pai[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if(a == b) return 0;
pai[b] = a;
return 1;
}
} dsu;
struct KRT
{
vector<int> g[maxn]; // graph pointing down
int tab[maxn][logn], val[maxn], pos[maxn], head = 0, t = 1; // position of leafs
int in[maxn], out[maxn];
DSU aux;
void addEdge(int from, int to, int weight) {
head = from;
val[from] = weight;
to = aux.find(to); // gets the head of the component
aux.join(from, to); // make him my son
tab[to][0] = from;
g[from].pb(to);
}
void dfs(int u) {
if(u <= n) return (void)(pos[u] = t++);
in[u] = t;
for(int v : g[u])
dfs(v);
out[u] = t-1;
}
void build() {
dfs(head);
for(int l = 1; l < logn; l++)
for(int i = 1; i <= head; i++)
tab[i][l] = tab[tab[i][l-1]][l-1];
}
int get(int u, int v, int k) {
auto comp = [&](int a, int b) { return k?a>=b:a<=b; };
for(int l = logn-1; l >= 0; l--) {
if(tab[u][l] && comp(val[tab[u][l]], v))
u = tab[u][l];
}
return u;
}
void get_dfs(int u, vector<int>& vv) {
if(u <= n) return (void)(vv.pb(u));
for(int v : g[u])
get_dfs(v, vv);
}
void dfs_debug(int u, int p) {
printf("%d %d\n", u, p);
// printf("(%d %d) <- %d\n", u, pos[u], p);
// printf("(%d [%d %d]) <- %d\n", u, in[u], out[u], p);
for(int v : g[u])
dfs_debug(v, u);
}
void debug() {
puts("PRINTING THE TREE");
dfs_debug(head, 0);
}
} krt[2];
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N;
vector<pii> edges;
int M = (int)X.size();
for(int i = 0; i < M; i++) {
if(X[i] > Y[i]) swap(X[i], Y[i]);
++X[i], ++Y[i];
edges.pb({X[i], Y[i]});
}
{
sort(all(edges), [](pii a, pii b) {
return a.first > b.first;
});
int cnt = N;
for(int i = 0; i < M; i++) {
int a = edges[i].ff, b = edges[i].ss;
// puts("OI");
if(dsu.join(a, b)) {
// printf("%d %d\n", a, b);
++cnt;
krt[0].addEdge(cnt, a, a); // from, to, value of new node
krt[0].addEdge(cnt, b, a);
}
}
krt[0].build();
// krt[0].debug();
}
{
dsu.init();
// Sort by increasing big value
sort(all(edges), [](pii a, pii b) {
return a.ss < b.ss;
});
int cnt = N;
for(int i = 0; i < M; i++) {
int a = edges[i].ff, b = edges[i].ss;
if(dsu.join(a, b)) {
++cnt;
krt[1].addEdge(cnt, a, b);
krt[1].addEdge(cnt, b, b);
}
}
krt[1].build();
// krt[1].debug();
}
int Q = S.size();
vector<int> ans(Q);
for(int i = 0; i < Q; i++) {
if(S[i] < L[i] || E[i] > R[i]) continue;
vector<int> r1; krt[0].get_dfs(krt[0].get(S[i], L[i], 1), r1);
vector<int> r2; krt[1].get_dfs(krt[1].get(E[i], R[i], 0), r2);
sort(all(r1));
for(int j = 0; j < (int)r2.size(); j++)
ans[i] |= binary_search(all(r1), r2[i]);
}
return ans;
// return vector<int>(0);
}
