#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
int n;
struct DSU
{
int father[200005],siz[200005];
void init()
{
for(int i=0;i<n;i++)
father[i]=i, siz[i]=1;
}
int get(int x)
{
if(father[x]!=x)
father[x]=get(father[x]);
return father[x];
}
void unite(int x, int y)
{
x = get(x);
y = get(y);
if(x==y)
return;
if(siz[x] < siz[y])
swap(x,y);
siz[x] += siz[y];
father[y] = x;
}
};
int dx[4] = {-2,+2,0,0};
int dy[4] = {0,0,-2,+2};
int construct_roads(std::vector<int> x, std::vector<int> y)
{
n = x.size();
if (n == 1)
{
build({}, {}, {}, {});
return 1;
}
std::vector<int> solu, solv, sola, solb;
map<pair<int,int>,pair<int,bool>> mp;
for(int i=0;i<n;i++)
{
mp[{x[i],y[i]}] = {i,1};
}
DSU dsu;
dsu.init();
for(int i=0;i<n;i++)
{
for(int v=0;v<4;v++)
{
int newx = x[i]+dx[v], newy = y[i]+dy[v];
if(mp[{newx,newy}].second)
{
int j = mp[{newx,newy}].first;
if(dsu.get(i) != dsu.get(j))
{
dsu.unite(i,j);
solu.push_back(i);
solv.push_back(j);
}
}
}
}
if(dsu.siz[dsu.get(1)] != n)
return 0;
sola.resize(solu.size());
solb.resize(solu.size());
map<pair<int,int>,bool> used;
for(int i=0;i<solu.size();i++)
{
int u = solu[i], v = solv[i];
pair<int,int> banca;
if(x[u] == x[v])
{
if(!used[{x[u]-1, (y[u]+y[v])/2}])
{
banca = {x[u]-1, (y[u]+y[v])/2};
}
else if(!used[{x[u]+1, (y[u]+y[v]/2)}])
{
banca = {x[u]+1, (y[u]+y[v])/2};
}
else
{
return 0;
//assert(0);
}
}
else
{
assert(y[u] == y[v]);
if(!used[{(x[u]+x[v])/2, y[u]-1}])
{
banca = {(x[u]+x[v])/2, y[u]-1};
}
else if(!used[{(x[u]+x[v])/2, y[u]+1}])
{
banca = {(x[u]+x[v])/2, y[u]+1};
}
else
{
return 0;
//assert(0);
}
}
used[banca] = 1;
sola[i] = banca.first;
solb[i] = banca.second;
}
build(solu, solv, sola, solb);
return 1;
}
