#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, _in, _out, euler;
vector <vector<int>> adj;
bool isMax;
Dsu(int n, bool isMax) : isMax(isMax) {
fa.resize(n);
iota(all(fa), 0);
adj.resize(n);
_in.resize(n);
_out.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{
_in[u] = ++ct;
euler.pb(u);
for ( auto &v: adj[u] ){
//~ cout << u << " " << v << ln;
dfs(dfs, v);
} _out[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 <int> ans(q);
for ( int i = 0; i < q; i++ ){
for ( int j = ds._in[ps[i]]; j <= ds._out[ps[i]]; j++ ){ // subtree of pe[i]
for ( int k = de._in[pe[i]]; k <= de._out[pe[i]]; k++ ){ // subtree of pe[i]
if ( ds.euler[j] == de.euler[k] ){
ans[i] = 1;
}
}
}
}
return ans;
}
