#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
int n;
const int N = (int)2e5 + 10;
vector<int> T[N];
int par[N];
vector<int> T1[N];
vector<int> T2[N];
int fin(int x){
if(par[x]==x)return x;
return par[x]=fin(par[x]);
}
int S[N], E[N], L[N], R[N];
int t1[N], t2[N];
vector<int> sol;
vector<int> i1[N];
vector<int> i2[N];
int tin[N], tout[N];
int ti;
void dfs1(int u){
tin[u] = ++ti;
for(auto x : T2[u]){
dfs1(x);
}
tout[u] = ti;
}
vector<int> tq[N];
set<int> un[N];
void dfs2(int u){
un[u].insert(tin[u]);
for(auto x : T1[u]){
dfs2(x);
if(un[x].size() > un[u].size())
swap(un[x], un[u]);
for(auto x : un[x]){
un[u].insert(x);
}
un[x].clear();
}
for(auto p : tq[u]){
auto it = un[u].lower_bound(tin[t2[p]]);
if(it == un[u].end() || (*it) > tout[t2[p]])
sol[p]=0;
else
sol[p]=1;
}
}
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;
for(int i = 0 ; i < n; i ++ )
par[i] = i;
int m = X.size();
int us, vs;
int qq = _S.size();
sol.resize(qq);
for(int i = 0 ; i < qq; i ++ ){
S[i] = _S[i];
E[i] = _E[i];
L[i] = _L[i];
R[i] = _R[i];
}
for(int i = 0 ; i < qq; i ++ ){
i1[L[i]].push_back(i);
i2[R[i]].push_back(i);
}
for(int i = 0 ; i < m ; i ++ ){
us = X[i];
vs = Y[i];
if(us > vs)
swap(us, vs);
T[us].push_back(vs);
}
for(int i = n - 1; i >= 0 ; i -- ){
for(auto &x : T[i]){
x=fin(x);
if(x != i){
T1[i].push_back(x);
par[x] = i;
}
}
for(auto x : i1[i]){
t1[x]=fin(S[x]);
}
}
for(int i = 0 ; i < n; i ++ ){
T[i].clear();
par[i] = i;
}
for(int i = 0 ; i < m; i ++ ){
us = X[i];
vs = Y[i];
if(us < vs) swap(us, vs);
T[us].push_back(vs);
}
for(int i = 0 ; i < n; i ++ ){
for(auto &x : T[i]){
x = fin(x);
if(x != i){
T2[i].push_back(x);
par[x] = i;
}
}
for(auto x : i2[i]){
t2[x]=fin(E[x]);
}
}
dfs1(n-1);
for(int i = 0 ; i < qq ; i ++ ){
tq[t1[i]].push_back(i);
}
dfs2(0);
return sol;
}
