#include "parks.h"
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <iostream>
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<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(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;
}
bx=vector<int>(n-1,-1);
by=bx;
map<pair<int,int>,set<int>>cont;
map<int,set<pair<int,int>>>pos;
for (auto i:s)
{
for (auto j:hor[i])
{
cont[{i+1,y[ex[j]]-1}].insert(j);
cont[{i+1,y[ex[j]]+1}].insert(j);
pos[j].insert({i+1,y[ex[j]]-1});
pos[j].insert({i+1,y[ex[j]]+1});
}
for (auto j:ver[i])
{
cont[{i-1,y[ex[j]]+1}].insert(j);
cont[{i+1,y[ex[j]]+1}].insert(j);
pos[j].insert({i+1,y[ex[j]]+1});
pos[j].insert({i-1,y[ex[j]]+1});
}
}
set<pair<int,pair<int,int>>>s1;
for (auto [i,j]:cont)
s1.insert({j.size(),i});
while (s1.size())
{
auto z=*begin(s1);
s1.erase(z);
if (z.first==0) continue;
int mn=*begin(cont[z.second]);
for (auto i:cont[z.second])
{
if(pos[i].size()<pos[mn].size())
mn=i;
}
bx[mn]=z.second.first,by[mn]=z.second.second;
for (auto t:cont[z.second])
pos[t].erase(z.second);
for (auto i:pos[mn])
{
s1.erase({cont[i].size(),i});
cont[i].erase(mn);
s1.insert({cont[i].size(),i});
}
}
for (auto i:bx)
{
if (i==-1)
return 0;
}
build(ex,ey,bx,by);
return 1;
}
