#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int MAXN = (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
int n;
vector <int> X, Y, L, R, S, E;
vector <int> g[MAXN], adj[2][MAXN];
bool was[MAXN];
struct dsu {
int p[MAXN];
int get(int i) {
return p[i] == i ? i : p[i] = get(p[i]);
}
} d;
struct fenwick {
int f[MAXN];
void upd(int p, int x) {
for (; p < MAXN; p |= p + 1) f[p] += x;
}
int get(int p) {
int sum = 0;
for (; p >= 0; p = (p & (p + 1)) - 1) sum += f[p];
return sum;
}
} f;
vector < pair <int, int> > q[2][MAXN];
vector < array <int, 4> > qu[MAXN]; /// i, f, l, r
int sum[MAXN];
int par[2][MAXN];
int tmr;
int tin[2][MAXN], tout[2][MAXN];
int a[2][MAXN];
void dfs(int v, int id) {
tin[id][v] = ++tmr;
a[id][tmr] = v;
/*
{
/ *
TODO:
Then Delete it (it's just for debug)
* /
cerr << v << " -> ";
for (auto to : adj[id][v]) {
{
cerr << to << ' ';
}
}
cerr << nl;
}
*/
for (auto to : adj[id][v]) {
if (!tin[id][to]) {
dfs(to, id);
}
}
tout[id][v] = tmr;
}
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;
X = _X;
Y = _Y;
S = _S;
E = _E;
L = _L;
R = _R;
// copy finished
// checked 1
rep(i, 0, sz(X)) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
// checked 1
rep(i, 0, sz(S)) {
q[0][L[i]].pb({S[i], i});
q[1][R[i]].pb({E[i], i});
}
// checked 1
per(i, n - 1, 0) {
d.p[i] = i;
for (auto to : g[i]) {
if (!was[to] || d.get(to) == i) continue;
adj[0][i].pb(d.get(to));
d.p[d.get(to)] = i;
}
for (auto it : q[0][i]) {
par[0][it.s] = d.get(it.f);
}
was[i] = 1;
}
// checked 1
memset(was, 0, sizeof(was));
rep(i, 0, n) {
d.p[i] = i;
for (auto to : g[i]) {
if (!was[to] || d.get(to) == i) continue;
adj[1][i].pb(d.get(to));
d.p[d.get(to)] = i;
}
for (auto it : q[1][i]) {
par[1][it.s] = d.get(it.f);
}
was[i] = 1;
}
// checked 1
dfs(0, 0);
tmr = 0;
dfs(n - 1, 1);
// checked 1
rep(i, 0, sz(S)) {
int v1 = par[0][i];
int l1 = tin[0][v1], r1 = tout[0][v1];
int v2 = par[1][i];
int l2 = tin[1][v2], r2 = tout[1][v2];
if (l1) qu[l1 - 1].pb({i, -1, l2, r2});
qu[r1].pb({i, 1, l2, r2});
}
vector <int> ans(sz(S)), pos(n, 0);
rep(i, 1, n + 1) pos[a[1][i]] = i;
rep(i, 1, n + 1) {
f.upd(pos[a[0][i]], 1);
for (auto it : qu[i]) {
ans[it[0]] += it[1] * (f.get(it[3]) - f.get(it[2] - 1));
}
}
rep(i, 0, sz(ans)) {
assert(ans[i] >= 0);
if (ans[i] > 0) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}
