// O(N*Q) brute to check if my krt works properly
#include "werewolf.h"
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
constexpr int maxn = 4e5+10, logn = 20;
struct DSU
{
vector<int> g[maxn];
int pai[maxn], val[maxn], p[maxn][logn], cnt;
bool leaf[maxn];
DSU() { for(int i = 0; i < maxn; i++) pai[i] = i; }
void init() { for(int i = 0; i < cnt; i++) val[i] = i, leaf[i] = 1; }
int find(int x) { return pai[x]==x?x:pai[x]=find(pai[x]); }
void join(int a, int b, int v) {
a = find(a), b = find(b);
if(a == b) return;
// printf("(%d %d) %d %d\n", cnt, v, a, b);
g[cnt].push_back(a);
g[cnt].push_back(b);
val[cnt] = v;
pai[a] = cnt;
pai[b] = cnt;
p[a][0] = cnt;
p[b][0] = cnt;
++cnt;
}
void dfs(int u, vector<int>& reach) {
if(leaf[u]) return (void)(reach.push_back(u));
for(int v : g[u])
dfs(v, reach);
}
} dsu, dsu2;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
vector<pair<int,int>> edges;
dsu.cnt = N; dsu.init();
dsu2.cnt = N; dsu2.init();
int M = (int)(X.size());
for(int i = 0; i < M; i++) {
if(X[i] > Y[i]) swap(X[i], Y[i]);
edges.push_back({X[i], Y[i]});
}
sort(edges.begin(), edges.end(), [](pair<int,int> a, pair<int,int> b) {
return a.first > b.first;
});
for(int i = 0; i < M; i++) {
int a = edges[i].first, b = edges[i].second;
dsu.join(a, b, a); // a já é o minimo
}
// puts("");
// Do the same but using the bigger edge now in increasing order
sort(edges.begin(), edges.end(), [](pair<int,int> a, pair<int,int> b) {
return a.second < b.second;
});
for(int i = 0; i < M; i++) {
int a = edges[i].first, b = edges[i].second;
dsu2.join(a, b, b);
}
// puts("");
// brute force to check if my krt works
int Q = S.size();
vector<int> ans(Q);
// vector<int> go;
// dsu2.dfs(5, go);
// for(int x : go)
// printf("%d ", x);
// printf("\n");
for(int i = 0; i < Q; i++) {
int v = S[i];
while(dsu2.p[v][0] && dsu2.val[dsu2.p[v][0]] <= R[i])
v = dsu2.p[v][0]; // too lazy to do binary lifting
vector<int> reach1; dsu2.dfs(v, reach1);
sort(reach1.begin(), reach1.end());
// printf("R1 %d %d\n", S[i], v);
// for(int x : reach1)
// printf("%d ", x);
// printf("\n");
v = E[i];
while(dsu.p[v][0] && dsu.val[dsu.p[v][0]] >= L[i])
v = dsu.p[v][0];
vector<int> reach2; dsu.dfs(v, reach2);
// printf("R2 %d %d\n", E[i], v);
// for(int x : reach2)
// printf("%d ", x);
// printf("\n");
bool ok = 0;
for(int i = 0; i < (int)reach2.size(); i++)
ok |= binary_search(reach1.begin(), reach1.end(), reach2[i]);
ans[i] = ok;
}
return ans;
}
