#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
map<pair<int,int>,int> idk;
int haha[MAXN][4];
vector<bool> bruh(MAXN,true);
void dfs(int a) {
bruh[a] = false;
for(int i = 0; i < 4; i++) {
if(haha[a][i] != -1 && bruh[haha[a][i]]) {
dfs(haha[a][i]);
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
for(int i = 0; i < n; i++) {
idk[{x[i],y[i]}] = i;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < 4; j++) {
haha[i][j] = -1;
}
}
for(int i = 0; i < n; i++) {
int a = x[i],b = y[i];
auto d = idk.find({a+2,b});
if(d != idk.end()) {
haha[i][0] = d->second;
}
d = idk.find({a,b+2});
if(d != idk.end()) {
haha[i][1] = d->second;
}
d = idk.find({a-2,b});
if(d != idk.end()) {
haha[i][2] = d->second;
}
d = idk.find({a,b-2});
if(d != idk.end()) {
haha[i][3] = d->second;
}
}
dfs(0);
for(int i = 0; i < n; i++) {
if(bruh[i]) {
return 0;
}
}
vector<int> banana0(0);
vector<int> banana1(0);
for(int i = 0; i < n; i++) {
int a = x[i],b = y[i];
if(haha[i][0] != -1 && haha[i][1] != -1 && haha[haha[i][0]][1] != -1) {
if(((a+1)/2+(b-1)/2)%2 == 1) {
banana0.push_back(i);
}
else {
banana1.push_back(i);
}
}
}
for(int v: banana0) {
haha[v][0] = -1;
}
for(int v: banana1) {
haha[v][1] = -1;
}
vector<int> ans1(0);
vector<int> ans2(0);
vector<int> ans3(0);
vector<int> ans4(0);
for(int i = 0; i < n; i++) {
int a = x[i],b = y[i];
if(haha[i][0] != -1) {
ans1.push_back(i);
ans2.push_back(haha[i][0]);
ans3.push_back(a+1);
if(((a+1)/2+(b-1)/2)%2 == 0) {
ans4.push_back(b-1);
}
else {
ans4.push_back(b+1);
}
}
if(haha[i][1] != -1) {
ans1.push_back(i);
ans2.push_back(haha[i][1]);
ans4.push_back(b+1);
if(((b+1)/2+(a-1)/2)%2 == 1) {
ans3.push_back(a-1);
}
else {
ans3.push_back(a+1);
}
}
}
build(ans1,ans2,ans3,ans4);
return 1;
}
