#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int t[400005],sz[400005],l[400005],st[400005],en[400005],cur[400005],sz2[400005];
vector<int>g[400005],g2[400005],ev[400005];
set<int>nod[400005];
int n,m,q;
int findt(int x)
{
if (x==t[x])
return x;
return t[x]=findt(t[x]);
}
void onion(int a,int b,bool tip)
{
a=findt(a);
b=findt(b);
if (a==b)
return ;
if (sz[a]<sz[b])
swap(a,b);
if (tip==0)
g[a].push_back(b);
else
for(auto it:nod[b])
nod[a].insert(it);
t[b]=a;
sz[a]+=sz[b];
}
void dfs(int x)
{
static int u=0;
l[x]=++u;
for(auto it:g[x])
dfs(it);
}
vector<int>check_validity(int n2,vector<int>x,vector<int>y,vector<int>s,vector<int>e,vector<int>l2,vector<int>r)
{
n=n2;
m=x.size();
q=s.size();
vector<int>ans(q,0);
iota(t,t+n,0);
fill(sz,sz+n,1);
int i;
for(i=0;i<m;i++){
g2[x[i]].push_back(y[i]);
g2[y[i]].push_back(x[i]);
}
for(i=0;i<q;i++)
ev[l2[i]].push_back(i);
for(i=n-1;i>=0;i--){
for(auto it:g2[i])
if (i<it)
onion(it,i,0);
for(auto it:ev[i]){
int nodi=findt(s[it]);
cur[it]=nodi;
sz2[it]=sz[nodi];
}
ev[i].clear();
}
for(i=0;i<n;i++){
if (i==t[i]){
dfs(i);
break;
}
}
for(i=0;i<q;i++){
st[i]=l[cur[i]];
en[i]=l[cur[i]]+sz2[i]-1;
ev[r[i]].push_back(i);
}
for(i=0;i<n;i++)
nod[i].insert(l[i]);
iota(t,t+n,0);
fill(sz,sz+n,1);
for(i=0;i<n;i++){
for(auto it:g2[i])
if (it<i)
onion(i,it,1);
for(auto it:ev[i]){
int nodi=findt(e[it]);
auto it2=nod[nodi].lower_bound(st[it]);
if (it2!=nod[nodi].end() && *(it2)<=en[it])
ans[it]=1;
}
}
return ans;
}
