#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn = 2e5 + 9;
struct DSU_Tree {
vector<vector<int>>a;
vector<int>f;
int n;
int fs(int u) {
if (f[u] < 0)
return u;
return f[u] = fs(f[u]);
}
void unite(int u, int v) {
u = fs(u), v = fs(v);
if (u == v)
return;
n++;
f[n] = f[u] + f[v];
a[n].pb(u);
a[n].pb(v);
f[u] = n;
f[v] = n;
}
int tme = 0;
vector<int>in, out, rev;
void dfs(int u) {
in[u] = ++tme;
rev[in[u]] = u;
for (auto v : a[u]) {
dfs(v);
}
out[u] = tme;
}
void resz(int _n) {
n = _n;
f.resize(2 * n + 9);
a.resize(2 * n + 9);
for1(i, 1, n)f[i] = -1;
in.resize(2 * n + 9);
out.resize(2 * n + 9);
rev.resize(2 * n + 9);
}
};
int st[maxn * 8];
void update(int id, int l, int r, int u, int val) {
if (l > u || r < u)
return;
if (l == r) {
st[id] = val;
return;
}
int mid = (l + r) / 2;
update(id * 2, l, mid, u, val);
update(id * 2 + 1, mid + 1, r, u, val);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v) {
if (l > v || r < u || u > v)
return 0;
if (u <= l && r <= v)
return st[id];
int mid = (l + r) / 2;
return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
bool ans[maxn];
struct edg {
int u, v;
} b[maxn * 2];
int pars[maxn], pare[maxn];
vector<int>ask1[maxn], ask2[maxn];
vector<int>canh[maxn];
vector<int>answer[maxn * 2];
bool valid[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), q = sz(S);
for1(i, 0, m - 1)x[i]++, y[i]++;
for1(i, 0, q - 1)S[i]++, E[i]++, L[i]++, R[i]++;
for1(i, 1, m) {
b[i] = {x[i - 1], y[i - 1]};
canh[max(x[i - 1], y[i - 1])].pb(i);
}
for1(i, 0, q - 1)swap(S[i], E[i]);;
DSU_Tree t1, t2; //t1 for 1->n t2 for n->1
for1(i, 0, q - 1) {
ask1[R[i]].pb(i);
}
t1.resz(n), t2.resz(n);
for1(i, 1, n) {
for (auto v : canh[i]) {
t1.unite(b[v].u, b[v].v);
}
for (auto v : ask1[i]) {
pars[v] = t1.fs(S[v]);
}
canh[i].clear();
}
for1(i, 1, m) {
canh[min(x[i - 1], y[i - 1])].pb(i);
}
for1(i, 0, q - 1) {
ask2[L[i]].pb(i);
}
for2(i, n, 1) {
for (auto v : canh[i]) {
t2.unite(b[v].u, b[v].v);
}
for (auto v : ask2[i]) {
pare[v] = t2.fs(E[v]);
}
}
t1.dfs(t1.n), t2.dfs(t2.n);
int nn = t2.n;
for1(i, 0, q - 1) {
answer[t1.out[pars[i]]].pb(i);
}
for1(i, 1, t1.n) {
if (t1.rev[i] <= n) {
update(1, 1, nn, t2.in[t1.rev[i]], i);
}
for (auto v : answer[i]) {
int start = pars[v], ed = pare[v];
if (get(1, 1, nn, t2.in[ed], t2.out[ed]) >= t1.in[start]) {
valid[v] = 1;
}
}
}
vector<int>last;
for1(i, 0, q - 1)last.pb(valid[i]);
return last;
}
