#include "parks.h"
#include <iostream>
#include <map>
#include <algorithm>
#define f first
#define s second
using namespace std;
int n, vis[200010];
vector<pair<int,int>> pt;
map<pair<int,int>,int> mp, hv;
vector<int> edge[200010];
void dfs(int u) {
vis[u] = 1;
for (int i = 0; i < edge[u].size(); i++) if (!vis[edge[u][i]]) dfs(edge[u][i]);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
n = x.size();
for (int i = 0; i < n; i++) pt.push_back({x[i],y[i]}), mp[{x[i],y[i]}] = i+1;
sort(pt.begin(),pt.end());
vector<int> u, v, a, b;
for (int i = 0; i < n; i++) {
if (mp[{pt[i].f,pt[i].s-2}]) {
if ((pt[i].f+pt[i].s)%4 == 0) {
hv[{pt[i].f,pt[i].s}] = 1;
u.push_back(mp[{pt[i].f,pt[i].s-2}]-1);
v.push_back(mp[{pt[i].f,pt[i].s}]-1);
a.push_back(pt[i].f+1);
b.push_back(pt[i].s-1);
edge[mp[{pt[i].f,pt[i].s-2}]].push_back(mp[{pt[i].f,pt[i].s}]);
edge[mp[{pt[i].f,pt[i].s}]].push_back(mp[{pt[i].f,pt[i].s-2}]);
} else if (hv[{pt[i].f-2,pt[i].s}] == 0) {
u.push_back(mp[{pt[i].f,pt[i].s-2}]-1);
v.push_back(mp[{pt[i].f,pt[i].s}]-1);
a.push_back(pt[i].f-1);
b.push_back(pt[i].s-1);
edge[mp[{pt[i].f,pt[i].s-2}]].push_back(mp[{pt[i].f,pt[i].s}]);
edge[mp[{pt[i].f,pt[i].s}]].push_back(mp[{pt[i].f,pt[i].s-2}]);
}
}
if (mp[{pt[i].f-2,pt[i].s}]) {
if ((pt[i].f+pt[i].s)%4 == 2) {
hv[{pt[i].f,pt[i].s}] = 1;
u.push_back(mp[{pt[i].f-2,pt[i].s}]-1);
v.push_back(mp[{pt[i].f,pt[i].s}]-1);
a.push_back(pt[i].f-1);
b.push_back(pt[i].s+1);
edge[mp[{pt[i].f-2,pt[i].s}]].push_back(mp[{pt[i].f,pt[i].s}]);
edge[mp[{pt[i].f,pt[i].s}]].push_back(mp[{pt[i].f-2,pt[i].s}]);
} else if (hv[{pt[i].f,pt[i].s-2}] == 0) {
u.push_back(mp[{pt[i].f-2,pt[i].s}]-1);
v.push_back(mp[{pt[i].f,pt[i].s}]-1);
a.push_back(pt[i].f-1);
b.push_back(pt[i].s-1);
edge[mp[{pt[i].f-2,pt[i].s}]].push_back(mp[{pt[i].f,pt[i].s}]);
edge[mp[{pt[i].f,pt[i].s}]].push_back(mp[{pt[i].f-2,pt[i].s}]);
}
}
}
dfs(1);
for (int i = 1; i <= n; i++) if (!vis[i]) return 0;
build(u,v,a,b);
return 1;
}
