#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R){
vector <vector<int>> adj(N);
for ( int i = 0; i < X.size(); i++ ){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
int n = N;
auto gen = [&](int s){
vector <vector<int>> tree(n);
vector <int> fa(n);
iota(all(fa), 0);
auto find = [&](auto find, int u) -> int{
return fa[u] == u ? u : fa[u] = find(find, fa[u]);
};
auto unite = [&](int u, int v){
u = find(find, u), v = find(find, v);
if ( u == v ){
return false;
}
if ( u * s > v * s ){
swap(u, v);
}
fa[v] = u;
tree[u].pb(v);
return true;
};
auto rng = [&](int u){
return u >= 0 && u < n;
};
for ( int i = (s > 0 ? n - 1 : 0); rng(i); i -= s ){
for ( auto &j: adj[i] ){
if ( i * s < j * s ){
unite(i, j);
}
}
}
return tree;
};
auto wa = gen(1), wb = gen(-1);
vector <vector<int>> upA(20, vector <int> (n)), upB(20, vector <int> (n, n - 1));
vector <int> tin(n), tout(n);
int ct = 0;
auto dfs_wa = [&](auto dfs_wa, int u, int p) -> void{
upA[0][u] = p;
tin[u] = ++ct;
for ( auto &v: wa[u] ){
dfs_wa(dfs_wa, v, u);
} tout[u] = ct;
};
auto dfs_wb = [&](auto dfs_wb, int u, int p) -> void{
upB[0][u] = p;
for ( auto &v: wb[u] ){
dfs_wb(dfs_wb, v, u);
}
};
dfs_wa(dfs_wa, 0, 0);
dfs_wb(dfs_wb, n - 1, n - 1);
for ( int i = 1; i < 20; i++ ){
for ( int j = 0; j < n; j++ ){
upA[i][j] = upA[i - 1][upA[i - 1][j]];
upB[i][j] = upB[i - 1][upB[i - 1][j]];
}
}
vector <vector<ar<int,2>>> qu(n);
for ( int i = 0; i < S.size(); i++ ){
int u = S[i], v = E[i];
for ( int j = 19; j >= 0; j-- ){
if ( upA[j][u] >= L[i] ){
u = upA[j][u];
}
if ( upB[j][v] <= R[i] ){
v = upB[j][v];
}
}
qu[v].pb({u, i});
}
int q = S.size();
vector <int> ans(q);
vector <set<int>> s(n);
auto dfs = [&](auto dfs, int u) -> void{
s[u].insert(tin[u]);
for ( auto &v: wb[u] ){
dfs(dfs, v);
if ( s[u].size() < s[v].size() ){
swap(s[u], s[v]);
}
for ( auto &x: s[v] ){
s[u].insert(x);
} s[v].clear();
}
for ( auto &[v, j]: qu[u] ){
ans[j] = s[u].lower_bound(tin[v]) != s[u].upper_bound(tout[v]);
}
};
dfs(dfs, n - 1);
return ans;
}
