#include<bits/stdc++.h>
#include "werewolf.h"
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;
struct edge
{
int u,v;
edge(int _,int __):u(_),v(__){};
};
vector<edge> g;
bool cmp1(edge a,edge b)
{
return max(a.u,a.v)<max(b.u,b.v);
}
bool cmp2(edge a,edge b)
{
return min(a.u,a.v)>min(b.u,b.v);
}
bool cmp3(pii a,pii b)
{
return a>b;
}
int parent[mxn];
int findRep(int u)
{
if(parent[u]==u)return u;
return parent[u]=findRep(parent[u]);
}
void _union(int u,int v)
{
u=findRep(u);
v=findRep(v);
parent[min(u,v)]=max(u,v);
}
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<=N;i++)parent[i]=i;
pair<bool,bool> res[mxn];
for(int i=0;i<X.size();i++)
{
g.push_back(edge(X[i],Y[i]));
}
vector<pii> tr;
vector<pii> tl;
for(int i=0;i<R.size();i++)
{
tr.push_back({R[i],i});
tl.push_back({L[i],i});
}
sort(g.begin(),g.end(),cmp1);
sort(tr.begin(),tr.end());
int k=0;
for(int i=0;i<tr.size();i++)
{
while(k<g.size() && max(g[k].u,g[k].v)<=tr[i].f)
{
_union(g[k].u,g[k].v);
k++;
}
int q=tr[i].s;
int p=findRep(E[q]);
if(p>=L[q] && p<=R[q])
{
res[q]={true,false};
}
else
{
res[q]={false,false};
}
E[q]=p;
}
for(int i=0;i<=N;i++)parent[i]=i;
sort(g.begin(),g.end(),cmp2);
sort(tl.begin(),tl.end(),cmp3);
k=0;
for(int i=0;i<tr.size();i++)
{
while(k<g.size() && tl[i].f<=min(g[k].u,g[k].v))
{
_union(g[k].u,g[k].v);
k++;
}
int q=tl[i].s;
if(findRep(S[q])==findRep(E[q]))
{
res[q].s=true;
}
}
vector<int> rs;
for(int i=0;i<S.size();i++)
{
if(res[i].f && res[i].s)rs.push_back(1);
else rs.push_back(0);
}
return rs;
}
