#include "werewolf.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
//#include "werewolf.h"
using namespace std;
int sef[300005];
int cnt[300005];
int x[600005];
int y[600005];
vector<int>adj[200005];
vector<int>tree1[200005];
vector<int>tree2[200005];
int find(int a)
{
if(sef[a]==a)
{
return a;
}
return sef[a]=find(sef[a]);
}
void merge(int a,int b)
{
a=find(a);
b=find(b);
sef[b]=a;
}
int in1[200005];
int out1[200005];
int timp1=0;
void dfs1(int curr)
{
timp1++;
in1[curr]=timp1;
for(auto k:tree1[curr])
{
dfs1(k);
}
out1[curr]=timp1;
}
int in2[200005];
int out2[200005];
int timp2=0;
void dfs2(int curr)
{
timp2++;
in2[curr]=timp2;
for(auto k:tree2[curr])
{
dfs2(k);
}
out2[curr]=timp2;
}
int st1[200005];
int st2[200005];
int dr1[200005];
int dr2[200005];
int can1[200005];
int can2[200005];
vector<pair<int,int>>qu1[200005];
vector<pair<int,int>>qu2[200005];
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int n=N,dim;
int m=X.size();
int q=S.size();
vector<int>rasp;
for(int i=0;i<m;i++)
{
x[i]=X[i];
y[i]=Y[i];
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i=0;i<q;i++)
{
qu1[R[i]].push_back({E[i],i});
qu2[L[i]].push_back({S[i],i});
}
for(int i=0;i<n;i++)
{
sef[i]=i;
}
for(int i=0;i<n;i++)
{
for(auto j:adj[i])
{
if(j<i)
{
if(find(i)!=find(j))
{
//cout<<"muhc "<<i<<" "<<find(j)<<'\n';
tree1[i].push_back(find(j));
merge(i,j);
}
}
}
for(auto j:qu1[i])
{
can1[j.second]=find(j.first);
//cout<<"query"<<" "<<j.second<<" "<<j.first<<" "<<can1[j.second]<<'\n';
}
}
dfs1(n-1);
for(int i=0;i<n;i++)
{
sef[i]=i;
}
for(int i=n-1;i>=0;i--)
{
for(auto j:adj[i])
{
if(j>i)
{
if(find(i)!=find(j))
{
//cout<<"muhc "<<i<<" "<<find(j)<<'\n';
tree2[i].push_back(find(j));
merge(i,j);
}
}
}
for(auto j:qu2[i])
{
can2[j.second]=find(j.first);
//cout<<"query"<<" "<<j.second<<" "<<j.first<<" "<<can1[j.second]<<'\n';
}
}
dfs2(0);
vector<int>rez;
for(int i=0;i<q;i++)
{
//cout<<in1[can1[i]]<<" "<<out1[can1[i]]<<" "<<in2[can2[i]]<<" "<<out2[can2[i]]<<'\n';
int gas=0;
for(int j=0;j<n;j++)
{
if(in1[can1[i]]<=in1[j] && in1[j]<=out1[can1[i]] && in2[can2[i]]<=in2[j] && in2[j]<=out2[can2[i]])
{
gas=1;
break;
}
}
rez.push_back(gas);
}
return rez;
}
