#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 69;
const int K = 18;
/*
g++ werewolf.cpp werewolf.h grader.cpp
./a.out
*/
int p[N], sz[N];
int up[N][K], tin[N], tout[N], timer, mx[N][K], dep[N];
vector<pair<int, int>> t[N];
vector<pair<int, int>> qs[N];
vector<int> g[N];
int root(int v) {
if (p[v] == v)
return v;
return p[v] = root(p[v]);
}
bool anc(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (anc(a, b))
return a;
else if (anc(b, a))
return b;
for (int i = K - 1;i >= 0;i--) {
if (!anc(up[a][i], b) && up[a][i] > 0)
a = up[a][i];
}
return up[a][0];
}
void dfs(int v, int p) {
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1;i < K;i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
mx[v][i] = max(mx[v][i - 1], mx[up[v][i - 1]][i - 1]);
}
for (auto u : t[v]) {
if (u.f == p)
continue;
dep[u.f] = dep[v] + 1;
mx[u.f][0] = u.s;
dfs(u.f, v);
}
tout[v] = timer;
}
int Mx(int a, int b) {
assert(anc(b, a));
int d = dep[a] - dep[b];
int r = 0;
for (int i = K - 1;i >= 0;i--) {
if (d >> i & 1) {
r = max(r, mx[a][i]);
a = up[a][i];
}
}
return r;
}
vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
int q = s.size();
int m = u.size();
vector<int> ans(q);
vector<tuple<int, int, int>> edges, edges1;
for (int i = 0;i < m;i++) {
++u[i], ++v[i];
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
for (int i = 0;i < q;i++) {
l[i]++, r[i]++;
s[i]++, e[i]++;
}
for (int i = 1;i <= n;i++) {
p[i] = i;
sz[i] = 1;
}
for (int i = 0;i < q;i++)
qs[l[i]].push_back({r[i], i});
for (int i = 0;i < m;i++) {
int a = u[i], b = v[i];
int c = min(a, b);
edges.push_back({c, a, b});
c = max(a, b);
edges1.push_back({c, a, b});
}
sort(edges.begin(), edges.end());
sort(edges1.begin(), edges1.end());
int ptr = m - 1;
for (auto u : edges1) {
int a, b, c;
tie(c, a, b) = u;
int x = root(a);
int y = root(b);
if (x != y) {
t[a].push_back({b, c});
t[b].push_back({a, c});
if (sz[x] < sz[y])
swap(x, y);
p[y] = x;
sz[x] += sz[y];
}
}
dfs(1, 0);
for (int i = 1;i <= n;i++) {
p[i] = i;
sz[i] = 1;
}
for (int i = n;i >= 1;i--) {
while (ptr >= 0 && get<0>(edges[ptr]) >= i) {
int a = get<1>(edges[ptr]), b = get<2>(edges[ptr]);
ptr--;
int x = root(a), y = root(b);
if (x != y) {
if (sz[x] < sz[y])
swap(x, y);
sz[x] += sz[y];
p[y] = x;
}
}
for (auto j : qs[i]) {
int r = j.f, ind = j.s;
int ok = 0;
for (int k = 1;k <= n;k++) {
if (root(k) == root(s[ind]) && k >= i && k <= r) {
int lc = lca(k, e[ind]);
int x = max(Mx(k, lc), Mx(e[ind], lc));
ok |= (x <= r);
}
}
ans[ind] = ok;
}
}
return ans;
}
/*
6 6 3
5 1
1 2
2 5
1 3
3 4
0 3
4 2 1 2
4 2 2 2
5 4 3 4
*/
