#include <bits/stdc++.h>
using namespace std;
#include "parks.h"
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
const int MX = 2e5 + 10;
int dx[4] = {2, -2, 0, 0}, dy[4] = {0, 0, 2, -2};
int dgx[4] = {1, 1, -1, -1}, dgy[4] = {1, -1, 1, -1};
pii pos[MX]; map<pii, int> nd;
bool vis[MX];
void dfs(int u){
vis[u] = true;
int nx = pos[u].fi, ny = pos[u].se;
for(int i = 0; i < 4; i++){
int v = nd[mp(nx + dx[i], ny + dy[i])];
if(v != 0 && !vis[v]) dfs(v);
}
}
// if there doesn't exist 2 * 2 squares
// we can color the 2 * 2 cells by black or white like a chess board
// if it is black color the left or right
// if it is white color the up or down
// We know that for every color at most direction exists because there doesn't exist 2 * 2 squares
/*
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b){
int N = u.size();
for(int i = 0; i < N; i++){
printf("edge %d - %d and bench at (%d, %d)\n", u[i], v[i], a[i], b[i]);
}
}
*/
vector<pii> pts;
int construct_roads(vector<int> x, vector<int> y){
int N = x.size();
vector<int> u, v, a, b; // u - v the fountains, (a, b) the index of the bench
for(int i = 0; i < N; i++){
pos[i + 1] = mp(x[i], y[i]);
nd[pos[i + 1]] = i + 1;
for(int j = 0; j < 4; j++)
pts.push_back(mp(x[i] + dgx[j], y[i] + dgy[j]));
}
dfs(1);
for(int i = 0; i < N; i++) if(!vis[i + 1]) return 0;
sort(pts.begin(), pts.end());
pts.resize(unique(pts.begin(), pts.end()) - pts.begin());
for(auto p : pts){
bool st = ((p.fi >> 1) + (p.se >> 1)) & 1;
if(st){
// left or right
if(nd[mp(p.fi - 1, p.se - 1)] && nd[mp(p.fi - 1, p.se + 1)]){
u.push_back(nd[mp(p.fi - 1, p.se - 1)]);
v.push_back(nd[mp(p.fi - 1, p.se + 1)]);
a.push_back(p.fi);
b.push_back(p.se);
}else if(nd[mp(p.fi + 1, p.se - 1)] && nd[mp(p.fi + 1, p.se + 1)]){
u.push_back(nd[mp(p.fi + 1, p.se - 1)]);
v.push_back(nd[mp(p.fi + 1, p.se + 1)]);
a.push_back(p.fi);
b.push_back(p.se);
}
}else{
// up or down
if(nd[mp(p.fi - 1, p.se + 1)] && nd[mp(p.fi + 1, p.se + 1)]){
u.push_back(nd[mp(p.fi - 1, p.se + 1)]);
v.push_back(nd[mp(p.fi + 1, p.se + 1)]);
a.push_back(p.fi);
b.push_back(p.se);
}else if(nd[mp(p.fi - 1, p.se - 1)] && nd[mp(p.fi + 1, p.se - 1)]){
u.push_back(nd[mp(p.fi - 1, p.se - 1)]);
v.push_back(nd[mp(p.fi + 1, p.se - 1)]);
a.push_back(p.fi);
b.push_back(p.se);
}
}
}
for(auto& p : u) p--;
for(auto& p : v) p--;
build(u, v, a, b);
return 1;
}
/*
int main(){
int N;
vector<int> x, y;
scanf("%d", &N);
x.resize(N); y.resize(N);
for(int i = 0; i < N; i++) scanf("%d %d", &x[i], &y[i]);
printf("%d\n", construct_roads(x, y));
}
*/
