#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 4e5 + 10;
int nodeInd , timer , par[MAXN] , sz[MAXN] , root[MAXN] , subtree[MAXN] , st[MAXN] , fn[MAXN] , l[MAXN] , r[MAXN];
vector<int> ans , G[2][MAXN] , adj[MAXN] , Q[2][MAXN] , vec[MAXN];
set<int> sub[MAXN];
void clear(int n){
fill(par , par + MAXN , -1);
fill(sz , sz + MAXN , 1);
fill(adj , adj + MAXN , vector<int>());
fill(subtree , subtree + MAXN , 0);
for(int i = 0 ; i < MAXN ; i++) root[i] = i;
nodeInd = n;
}
int Find(int v){
return (par[v] == -1 ? v : par[v] = Find(par[v]));
}
void Union(int v , int u){
v = Find(v); u = Find(u);
if(v == u) return;
if(sz[v] < sz[u]) swap(v , u);
par[u] = v; sz[v] += sz[u];
adj[nodeInd].push_back(root[v]);
adj[nodeInd].push_back(root[u]);
root[v] = nodeInd++;
}
void PreDFS(int v){
st[v] = ++timer;
for(int u : adj[v]){
PreDFS(u);
}
fn[v] = timer;
}
void SolveDFS(int v){
int leaf = 1;
for(int u : adj[v]){
leaf = 0;
SolveDFS(u);
if(sub[v].size() < sub[u].size()){
sub[v].swap(sub[u]);
}
for(auto &i : sub[u]) sub[v].insert(i);
}
if(leaf) sub[v].insert(st[v]);
for(int i : vec[v]){
auto it = sub[v].lower_bound(l[i]);
if(it == sub[v].end() || (*it) > r[i]) ans[i] = 0;
}
}
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 m = X.size() , q = S.size();
ans = vector<int>(q , 1);
for(int i = 0 ; i < m ; i++){
int v = X[i] , u = Y[i];
if(v > u) swap(v , u);
G[0][v].push_back(u);
G[1][u].push_back(v);
}
for(int i = 0 ; i < q ; i++){
Q[0][L[i]].push_back(i);
Q[1][R[i]].push_back(i);
}
clear(n);
for(int i = n - 1 ; i >= 0 ; i--){
for(int j : G[0][i]){
Union(i , j);
}
for(int j : Q[0][i]){
if(S[j] < i) ans[j] = 0;
subtree[j] = root[Find(S[j])];
}
}
PreDFS(nodeInd - 1);
for(int i = 0 ; i < q ; i++){
l[i] = st[subtree[i]];
r[i] = fn[subtree[i]];
}
clear(n);
for(int i = 0 ; i < n ; i++){
for(int j : G[1][i]){
Union(i , j);
}
for(int j : Q[1][i]){
if(E[j] > i) ans[j] = 0;
subtree[j] = root[Find(E[j])];
vec[subtree[j]].push_back(j);
}
}
SolveDFS(nodeInd - 1);
return ans;
}
