#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define ln '\n'
struct Dsu{
vector <int> fa, tin, tout, euler;
vector <vector<int>> adj;
bool isMax;
Dsu(int n, bool isMax) : isMax(isMax) {
fa.resize(n);
iota(all(fa), 0);
adj.resize(n);
tin.resize(n);
tout.resize(n);
}
int get(int u){
return u ^ fa[u] ? fa[u] = get(fa[u]) : u;
}
bool f(int u, int v){
return isMax ? u > v : u < v;
}
bool merge(int u, int v){
u = get(u), v = get(v);
if ( u == v ) return false;
if ( !f(u, v) ) swap(u, v);
fa[v] = u;
adj[u].pb(v);
return true;
}
void RunDfs(){
int ct = -1;
auto dfs = [&](auto dfs, int u) -> void{
tin[u] = ++ct;
euler.pb(u);
for ( auto &v: adj[u] ){
//~ cout << u << " " << v << ln;
dfs(dfs, v);
} tout[u] = ct;
};
int root = get(0);
dfs(dfs, root);
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int n = N, m = X.size(), q = S.size();
// Subtask #3
vector <vector<int>> adj(n);
for ( int i = 0; i < m; i++ ){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
Dsu ds(n, 0), de(n, 1);
vector <int> ps(q), pe(q);
{ // for S[i]
vector <vector<int>> qu(n);
for ( int i = 0; i < q; i++ ){
qu[L[i]].pb(i);
}
for ( int u = n - 1; u >= 0; u-- ){
for ( auto &v: adj[u] ){
if ( v > u ){
ds.merge(u, v);
}
}
for ( auto &j: qu[u] ){
ps[j] = ds.get(S[j]);
}
}
}
{ // for E[i]
vector <vector<int>> qu(n);
for ( int i = 0; i < q; i++ ){
qu[R[i]].pb(i);
}
for ( int u = 0; u < n; u++ ){
for ( auto &v: adj[u] ){
if ( v < u ){
de.merge(u, v);
}
}
for ( auto &j: qu[u] ){
pe[j] = de.get(E[j]);
}
}
}
ds.RunDfs();
de.RunDfs();
vector <vector<int>> qu(n);
for ( int i = 0; i < q; i++ ){
qu[ps[i]].pb(i);
}
vector <set<int>> s(n);
vector <int> ans(q);
auto dfs = [&](auto dfs, int u) -> void{
s[u].insert(de.tin[u]);
for ( auto &v: ds.adj[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 &j: qu[u] ){
int l = de.tin[pe[j]], r = de.tout[pe[j]];
ans[j] = (s[u].lower_bound(l) != s[u].upper_bound(r));
}
};
dfs(dfs, 0);
return ans;
}
