#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define vi vector<int>
const int mx = 6e5 + 5;
int par[mx], tin[mx], tout[mx], ti, id; vector<int> dsuAdj[mx]; set<int> nodes[mx];
int get(int i){
return i == par[i] ? i : par[i] = get(par[i]);
}
void merge(int a, int b, bool ty){
a = get(a); b = get(b); if (a == b) return;
if (!ty) dsuAdj[id].push_back(a), dsuAdj[id].push_back(b);
else{
nodes[id].insert(nodes[a].begin(), nodes[a].end());
nodes[id].insert(nodes[b].begin(), nodes[b].end());
}
par[a] = par[b] = id++;
}
void dfs(int i){
tin[i] = ti++;
for (int x : dsuAdj[i]) dfs(x);
tout[i] = ti - 1;
}
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R){
int m = X.size(), q = L.size();
vi adj[n], QL[n], QR[n], st1(q), ans(q);
for (int i = 0; i < m; i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
for (int i = 0; i < q; i++) QL[L[i]].push_back(i), QR[R[i]].push_back(i);
iota(par, par + n * 2, 0); id = n;
for (int i = n - 1; ~i; i--){
for (int x : adj[i]) if (x > i) merge(i, x, 0);
for (int qry : QL[i]) st1[qry] = get(S[qry]);
}
dfs(id - 1);
for (int i = 0; i < n; i++) nodes[i].insert(tin[i]);
iota(par, par + n * 2, 0); id = n;
for (int i = 0; i < n; i++){
for (int x : adj[i]) if (x < i) merge(i, x, 1);
for (int qry : QR[i]){
int st2 = get(E[qry]);
auto it = nodes[st2].lower_bound(tin[st1[qry]]);
if (it != nodes[st2].end() and *it <= tout[st1[qry]]) ans[qry] = 1;
}
}
return ans;
}
