#include "parks.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
pii add(pii a,pii b)
{
return make_pair(a.ff+b.ff,a.ss+b.ss);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
map<pii,int> __idx;
for(int i = 0; i < n; i++)
__idx[{x[i],y[i]}]=i;
function<int(pii)> fnd = [&](pii cur)
{
if(__idx.find(cur)==__idx.end())
return -1;
return __idx[cur];
};
vector<pii>delta = {{2,0},{-2,0},{0,2},{0,-2}};
map<pii,int> vis;
vector<int> u,v,a,b;
map<pii,set<pair<pii,int>>> graph;
function<void(pii,pii)> dfs =[&](pii cur,pii prev)
{
if(vis[cur] || fnd(cur)==-1)return;
vis[cur]=1;
if(prev!=cur)
{
int ae = add(cur,prev).ff/2;
int be = add(cur,prev).ss/2;
pii x = {ae,be-1},y = {ae,be+1};
if(be%2!=0)
x = {ae-1,be},y = {ae+1,be};
graph[x].insert({y,u.size()});
graph[y].insert({x,u.size()});
u.push_back(fnd(cur));
v.push_back(fnd(prev));
}
for(pii a : delta)
dfs(add(a,cur),cur);
};
dfs({x[0],y[0]},{x[0],y[0]});
int m= u.size();
a.resize(m,-1);
b.resize(m,-1);
for(auto a : __idx)
if(vis[a.ff]==0)
return 0;
vis.clear();
dfs = [&](pii cur,pii prev){
while(graph[cur].size())
{
auto par = (*graph[cur].begin());
graph[par.ff].erase(make_pair(cur,par.ss));
graph[cur].erase(par);
if(vis[par.ff])
{
a[par.ss]=cur.ff;
a[par.ss]=cur.ss;
}
else
{
a[par.ss]=par.ff.ff;
b[par.ss] = par.ff.ss;
}
dfs(par.ff,par.ff);
}
};
for(auto a : graph)
dfs(a.ff,a.ff);
build(u,v,a,b);
return 1;
}
