#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
const int MAXN = 2e5+5, LOG = 18;
int N, M, Q, T, ord[MAXN], fen[MAXN];
int dsu[MAXN], st[2][MAXN], en[2][MAXN], anc[2][MAXN][LOG];
vector <int> adj[MAXN], ch[2][MAXN], ans;
vector <piii> que[MAXN];
void update(int x) {
for (int i=x;i<=N;i+=i&-i) {
fen[i]++;
}
}
int query(int x) {
int ret = 0;
for (int i=x;i;i-=i&-i) {
ret += fen[i];
}
return ret;
}
int find(int x) {
if (dsu[x] == x) return x;
return dsu[x] = find(dsu[x]);
}
void dfs(int t,int x,int p) {
anc[t][x][0] = p;
for (int i=1;i<LOG;i++) {
anc[t][x][i] = anc[t][anc[t][x][i-1]][i-1];
}
T++;
ord[T] = x;
st[t][x] = T;
for (int y : ch[t][x]) {
dfs(t,y,x);
}
en[t][x] = T;
}
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;
M = X.size();
Q = S.size();
for (int i=0;i<M;i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i=0;i<N;i++) {
dsu[i] = i;
for (int j : adj[i]) {
if (j > i) continue;
j = find(j);
if (i != j) {
ch[0][i].push_back(j);
dsu[j] = i;
}
}
}
for (int i=N-1;i>=0;i--) {
dsu[i] = i;
for (int j : adj[i]) {
if (j < i) continue;
j = find(j);
if (i != j) {
ch[1][i].push_back(j);
dsu[j] = i;
}
}
}
dfs(0,N-1,N-1);
T = 0;
dfs(1,0,0);
for (int i=0;i<Q;i++) {
int x = S[i];
for (int j=LOG-1;j>=0;j--) {
if (anc[1][x][j] >= L[i]) {
x = anc[1][x][j];
}
}
int y = E[i];
for (int j=LOG-1;j>=0;j--) {
if (anc[0][y][j] <= R[i]) {
y = anc[0][y][j];
}
}
que[st[1][x]-1].push_back({i,{st[0][y]-1,en[0][y]}});
que[en[1][x]].push_back({i,{st[0][y]-1,en[0][y]}});
ans.push_back(0);
}
for (int i=1;i<=N;i++) {
update(st[0][ord[i]]);
for (auto x : que[i]) {
ans[x.fi] ^= query(x.se.se) - query(x.se.fi);
}
}
for (int i=0;i<Q;i++) {
ans[i] = !!ans[i];
}
return ans;
}
