#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
int dx[4] = {2,-2,0,0};
int dy[4] = {0,0,2,-2};
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
int construct_roads(std::vector<int> x, std::vector<int> y) {
const int n = (int)x.size();
set<pair<int,int>>s;
map<pair<int,int>,int>mp;
for(int i = 0 ; i < n ; i++)
mp[{x[i],y[i]}] = i;
vector<int>u(n-1),v(n-1),a(n-1),b(n-1);
map<pair<int,int>,bool>processed;
for(int i = 0 ; i < n ; i++) {
for(int d = 0 ; d < 4 ; d++) {
processed[{x[i],y[i]}] = 1;
if(mp.count({x[i] + dx[d], y[i] + dy[d]})) {
if(processed[{x[i] + dx[d], y[i] + dy[d]}])
continue;
int f = mp[{x[i] + dx[d], y[i] + dy[d]}];
if(dx[d] == 0) {
if(s.count({x[i]+1,y[i] + dy[d]/2}))
a[i] = x[i]-1, b[i] = y[i] + dy[d]/2, u[i] = i, v[i] = f, s.insert({a[i],b[i]});
else
a[i] = x[i]+1, b[i] = y[i] + dy[d]/2, u[i] = i, v[i] = f, s.insert({a[i],b[i]});
} else {
if(s.count({x[i] + dx[d]/2, y[i]+1}))
a[i] = x[i] + dx[d]/2, b[i] = y[i]-1, u[i] = i, v[i] = f, s.insert({a[i],b[i]});
else
a[i] = x[i] + dx[d]/2, b[i] = y[i]+1, u[i] = i, v[i] = f, s.insert({a[i],b[i]});
}
}
}
}
build(u,v,a,b);
return 1;
}
