#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int construct_roads(vector<int> x, vector<int> y) {
int N = x.size();
map<pair<int,int>,int> mp;
for(int i = 0;i < N;i++) mp[{x[i],y[i]}] = i;
vector<int> vis(N,false);
int dx[4] = {0,2,-2,0};
int dy[4] = {2,0,0,-2};
vector<int> u,v,a,b;
auto add_road = [&](int aidx,int bidx){
int midx = (x[aidx]+x[bidx])/2;
int midy = (y[aidx]+y[bidx])/2;
if(x[aidx] == x[bidx]){
// vertical
// if((midy/2)%2 == (midx/2)%2){
// midx++;
// }else{
// midx--;
// }
if(x[aidx] == 2) midx--;
else midx++;
}else{
// horizontal
// if((midx/2)%2 == (midy/2)%2){
// midy--;
// }else{
// midy++;
// }
midy--;
}
u.push_back(aidx);
v.push_back(bidx);
a.push_back(midx);
b.push_back(midy);
};
function<void(int)> dfs = [&](int idx){
// cout << "!" << idx << endl;
vis[idx] = true;
int cx = x[idx],cy = y[idx];
for(int d = 0;d < 4;d++){
int nx = cx+dx[d];
int ny = cy+dy[d];
if(!mp.count({nx,ny})) continue;
int nidx = mp[{nx,ny}];
if(vis[nidx]) continue;
add_road(idx,nidx);
dfs(nidx);
}
};
dfs(0);
for(auto &i:vis){
if(!i) return 0;
}
build(u,v,a,b);
return true;
}
