#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e5+5;
vector<int> g[MXN], ch[2][MXN], Q[MXN], tmp[MXN];
int dsu[MXN], wh[MXN];
int find(int v) { return v==dsu[v] ? v : dsu[v]=find(dsu[v]); }
void merge(int u, int v, int id) {
u = find(u), v = find(v);
if(u==v) return;
ch[id][dsu[v] = u].push_back(v);
}
int stt[MXN], fnt[MXN], timer;
vector<int> ans;
void dfs1(int v) {
stt[v] = timer++;
for(int u : ch[1][v])
dfs1(u);
fnt[v] = timer;
}
set<int> st[MXN];
void dfs0(int v) {
for(int u : ch[0][v]) {
dfs0(u);
if(st[v].size()<st[u].size()) st[v].swap(st[u]);
for(int x : st[u]) st[v].insert(x);
st[u].clear();
}
st[v].insert(stt[v]);
for(int i : Q[v]) {
auto it = st[v].lower_bound(stt[wh[i]]);
if(it!=st[v].end() && (*it)<fnt[wh[i]]) ans[i] = 1;
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
for(int i=0; i<X.size(); i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for(int i=0; i<L.size(); i++) tmp[L[i]].push_back(i);
iota(dsu, dsu+N, 0);
for(int i=N-1; i>=0; i--) {
for(int j : g[i])
if(j>i)
merge(i, j, 0);
for(int j : tmp[i])
Q[find(S[j])].push_back(j);
}
for(int i=0; i<N; i++) tmp[i].clear();
for(int i=0; i<R.size(); i++) tmp[R[i]].push_back(i);
iota(dsu, dsu+N, 0);
for(int i=0; i<N; i++) {
for(int j : g[i])
if(j<i)
merge(i, j, 1);
for(int j : tmp[i])
wh[j] = find(E[j]);
}
dfs1(N-1);
ans = vector<int>(L.size(), 0);
dfs0(0);
return ans;
}
