#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
struct dsu {
int n;
vector<int> par, val, l, r, p;
vector<vector<int>> adj, up;
dsu(int _n) : par(_n), adj(_n), n(_n), val(_n), l(_n), r(_n), p(_n) {
iota(all(par), 0), iota(all(val), 0);
}
int get(int x) {
if (x==par[x]) return x;
return par[x] = get(par[x]);
}
void unite(int x, int y, int basex) {
x=get(x), y=get(y);
if (x==y) return;
adj.pb({x, y}), par.pb(n), val.pb(basex), l.pb(0), r.pb(0), p.pb(n);
par[x]=par[y]=p[x]=p[y]=n;
n++;
}
vector<int> become;
int act=0;
void dfs(int u) {
l[u]=act;
for (int v: adj[u]) dfs(v);
if (u<sz(become)) become[u]=act++;
r[u]=act-1;
}
vector<int> plane(int m) {
become.resize(m);
for (int i=0; i<n; i++) if (par[i]==i) dfs(i);
return become;
}
void calcup() {
up.resize(n, vector<int>(20, -1));
for (int i=n-1; i>=0; i--) {
up[i][0]=p[i];
for (int j=1; j<20; j++) up[i][j]=up[up[i][j-1]][j-1];
}
}
} wolf(0), human(0);
int n, m, q;
vector<int> ans;
vector<vector<pair<int, int>>> queries;
set<int> dfs(int u) {
set<int> st;
if (u<n) st.insert(u);
for (int v: wolf.adj[u]) {
if (v==wolf.par[u]) continue;
set<int> st2=dfs(v);
if (st2.size()>st.size()) swap(st, st2);
for (int x: st2) {
if (st.count(x)) st.erase(x);
else st.insert(x);
}
}
for (auto [x, i]: queries[u]) {
int l=human.l[x], r=human.r[x];
auto lb=st.lower_bound(l);
if (lb!=st.end() && *lb<=r) ans[i]=1;
else ans[i]=0;
}
return move(st);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
q = sz(S), m=sz(X), n=N;
vector<vector<int>> adj(n);
for (int i=0; i<m; i++) adj[X[i]].pb(Y[i]), adj[Y[i]].pb(X[i]);
human=dsu(n);
for (int i=n-1; i>=0; i--) for (int j: adj[i]) if (j>i) human.unite(i, j, i);
vector<int> become=human.plane(n);
wolf=dsu(n);
for (int i=0; i<n; i++) for (int j: adj[i]) if (j<i) wolf.unite(become[i], become[j], i);
human.calcup(), wolf.calcup();
ans.resize(q), queries.resize(wolf.n);
for (int i=0; i<q; i++) {
int x=S[i], y=become[E[i]], l=L[i], r=R[i];
for (int j=19; j>=0; j--) if (human.val[human.up[x][j]]>=l) x=human.up[x][j];
for (int j=19; j>=0; j--) if (wolf.val[wolf.up[y][j]]<=r) y=wolf.up[y][j];
queries[y].pb({x, i});
}
for (int i=0; i<wolf.n; i++) {
if (wolf.par[i]==i) dfs(i);
}
return ans;
}
