#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int counter=-1;
vector<int> in, out, dsu, ans, ooga;
vector<vector<int> > graph, query, temp;
vector<set<int> > ss;
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
void merge(int a, int b){
a=fp(a), b=fp(b);
if (a==b)return;
graph[b].pb(a);
dsu[a]=b;
}
void dfs(int node){
in[node]=++counter;
for (auto num:graph[node])dfs(num);
out[node]=counter;
}
void dfs2(int node){
ss[node].insert(in[node]);
for (auto num:graph[node]){
dfs2(num);
if (ss[node].size()<ss[num].size())swap(ss[node], ss[num]);
for (auto a:ss[num])ss[node].insert(a);
}
for (auto c:query[node]){
auto it=ss[node].lower_bound(in[ooga[c]]);
if (it!=ss[node].end()&&*it<=out[ooga[c]])ans[c]=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){
counter=-1;
in.clear();
out.clear();
graph.clear();
dsu.clear();
ans.clear();
ss.clear();
ooga.clear();
query.clear();
query.resize(n);
in.resize(n);
out.resize(n);
graph.resize(n);
dsu.resize(n, -1);
ans.resize(l.size(), 0);
ss.resize(n);
ooga.resize(l.size());
vector<vector<int> > adj(n), got(n);
for (int i=0; i<x.size(); ++i)adj[x[i]].pb(y[i]), adj[y[i]].pb(x[i]);
for (int i=0; i<l.size(); ++i)got[l[i]].pb(i);
for (int i=n-1; i>=0; --i){
for (auto num:adj[i])if (num>i)merge(num, i);
for (auto num:got[i])query[fp(s[num])].pb(num);
}
temp=graph;
graph.clear();
graph.resize(n);
dsu.clear();
dsu.resize(n, -1);
got.clear();
got.resize(n);
for (int i=0; i<r.size(); ++i)got[r[i]].pb(i);
for (int i=0; i<n; ++i){
for (auto num:adj[i])if (num<i)merge(num, i);
for (auto num:got[i])ooga[num]=fp(e[num]);
}
dfs(n-1);
graph=temp;
dfs2(0);
return ans;
}
