#include "parks.h"
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
int const N=2e5+10;
int par[N]={};
int root(int n)
{
return (par[n]==n?n:par[n]=root(par[n]));
}
void merge(int u,int v)
{
u=root(u);
v=root(v);
if (u==v) return;
par[v]=u;
}
int dx[4]={-2,2,0,0},dy[4]={0,0,2,-2};
int construct_roads(vector<int> x, vector<int> y)
{
int n=x.size();
map<pair<int,int>,int>ind;
map<int,vector<int>>ver;
map<int,vector<pair<int,int>>>hor;
for (int i=0;i<n;i++)
{
ind[{x[i],y[i]}]=i;
par[i]=i;
}
set<int>s;
vector<int>ex,ey,bx,by;
for (int i=0;i<n;i++)
{
s.insert(x[i]);
for (int j=0;j<4;j++)
{
int x1=x[i]+dx[j],y1=y[i]+dy[j];
if (ind.find({x1,y1})!=ind.end())
{
int z=ind[{x1,y1}];
if (root(z)==root(i)) continue;
merge(i,z);
ex.push_back(i);
ey.push_back(z);
if (x1<x[i])
swap(ex.back(),ey.back());
if (x1==x[i])
if (y1<y[i])
swap(ex.back(),ey.back());
if (j<2)
{
hor[min(x[i],x1)].push_back({y[i],ex.size()-1});
}
else
ver[min(x[i],x1)].push_back(ex.size()-1);
}
}
}
for (int i=0;i<n;i++)
{
if (root(i)!=root(0))
return 0;
}
for (int i=0;i<n-1;i++)
{
pair<int,int>a,b;
a={x[ex[i]],y[ex[i]]};
b={x[ey[i]],y[ey[i]]};
if (a>=b)
return 0;
}
bx.resize(n-1);
by.resize(n-1);
map<pair<int,int>,bool>vis;
for (auto i:s)
{
for (auto j:ver[i])
{
if (vis.find({i-1,y[ex[j]]+1})==vis.end())
{
vis[{i-1,y[ex[j]]+1}]=1;
bx[j]=i-1;
by[j]=y[ex[j]]+1;
}
else if (vis.find({i+1,y[ex[j]]+1})==vis.end())
{
vis[{i+1,y[ex[j]]+1}]=1;
bx[j]=i+1;
by[j]=y[ex[j]]+1;
}
// else
// return 0;
}
sort(rbegin(hor[i]),rend(hor[i]));
for(auto [k,j]:hor[i])
{
if (vis.find({i+1,y[ex[j]]+1})==vis.end())
{
vis[{i+1,y[ex[j]]+1}]=1;
bx[j]=i+1;
by[j]=y[ex[j]]+1;
}
else if (vis.find({i+1,y[ex[j]]-1})==vis.end())
{
vis[{i+1,y[ex[j]]-1}]=1;
bx[j]=i+1;
by[j]=y[ex[j]]-1;
}
// else return 0;
}
}
build(ex,ey,bx,by);
return 1;
}
