#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 build){
a = get(a); b = get(b); if (a == b) return;
if (build){
dsuAdj[id].push_back(a); dsuAdj[id].push_back(b);
par[a] = par[b] = id++;
}
else{
if (nodes[a].size() > nodes[b].size()) swap(a, b);
par[a] = b;
nodes[b].insert(nodes[a].begin(), nodes[a].end());
}
}
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], st(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, 1);
for (int qry : QL[i]) st[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);
for (int i = 0; i < n; i++){
for (int x : adj[i]) if (x < i) merge(i, x, 0);
for (int qry : QR[i]){
int cmp = get(E[qry]);
auto it = nodes[cmp].lower_bound(tin[st[qry]]);
if (it != nodes[cmp].end() and *it <= tout[st[qry]]) ans[qry] = 1;
}
}
return ans;
}
