#include "werewolf.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 2e5 + 10;
int par[N], pos[N];
vector<int> C[N];
int Find(int u){
if(par[u] == u) return u;
return par[u] = Find(par[u]);
}
void Unite(int u, int v){
u = Find(u);
v = Find(v);
if(u == v) return ;
if(C[u].size() < C[v].size()) swap(u, v);
par[v] = u;
for(auto x : C[v]){
pos[x] = C[u].size();
C[u].pb(x);
}
C[v].clear();
}
int n;
vi G[N];
pii res[N], s1[N], s2[N];
vector<pii> Q[N];
vi dsuArray(vi ord){
vi mk(n, 0);
for(int i : ord){
par[i] = i;
C[i] = {i};
pos[i] = 0;
for(int adj : G[i])
if(mk[adj]) Unite(adj, i);
for(auto X : Q[i]){
res[X.S] = {-pos[X.F], C[Find(X.F)].size() - pos[X.F]};
}
mk[i] = 1;
}
return C[Find(0)];
}
vi DR, DL;
vi check_validity(int _n, vi X, vi Y, vi S, vi E, vi L, vi R){
n = _n;
int m = X.size();
int q = S.size();
for(int i = 0; i < m; i++) G[X[i]].pb(Y[i]), G[Y[i]].pb(X[i]);
vi O;
for(int i = 0; i < n; i++) O.pb(i);
for(int i = 0; i < n; i++) Q[i].clear();
for(int i = 0; i < q; i++) Q[R[i]].pb({E[i], i});
DR = dsuArray(O);
for(int i = 0; i < q; i++) s1[i] = {res[i].F + pos[E[i]], res[i].S + pos[E[i]]};
reverse(all(O));
for(int i = 0; i < n; i++) Q[i].clear();
for(int i = 0; i < q; i++) Q[L[i]].pb({S[i], i});
DL = dsuArray(O);
for(int i = 0; i < q; i++) s2[i] = {res[i].F + pos[S[i]], res[i].S + pos[S[i]]};
//cerr << "! ";
//for(auto x : DR) cerr << x << ' ';
//cerr << '\n';
//for(int i = 0; i < q; i++) cerr << "# " << s1[i].F << ' ' << s1[i].S << '\n';
vi ans;
for(int i = 0; i < q; i++){
bool fl = false;
for(int j = s1[i].F; j < s1[i].S; j++)
for(int k = s2[i].F; k < s2[i].S; k++)
fl |= (DR[j] == DL[k]);
ans.pb(fl);
}
return ans;
}
