#include "parks.h"
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int n, x[200005], y[200005];
PII ord[200005];
int rt[200005];
int root(int x)
{
return rt[x] == x ? x : rt[x] = root(rt[x]);
}
map<PII, int> idx;
vector<int> u, v, a, b;
void add(int i, int j)
{
u.push_back(i);
v.push_back(j);
assert(root(i) != root(j));
rt[root(i)] = root(j);
if(x[i] == x[j]) {
if((x[i] + y[i]) % 4 == 2) a.push_back(x[i] - 1);
else a.push_back(x[i] + 1);
b.push_back((y[i] + y[j]) / 2);
} else {
a.push_back((x[i] + x[j]) / 2);
if((x[i] + y[i]) % 4 == 2) b.push_back(y[i] + 1);
else b.push_back(y[i] - 1);
}
}
int construct_roads(vector<int> X, vector<int> Y)
{
n = (int) X.size();
rep(i, n) {
x[i] = X[i];
y[i] = Y[i];
rt[i] = i;
idx[{x[i], y[i]}] = i;
}
rep(i, n) ord[i] = MP(x[i] + y[i], i);
sort(ord, ord + n);
reverse(ord, ord + n);
rep(id, n) {
int i = ord[id].second;
int id0 = (idx.count(MP(x[i] + 2, y[i])) ? idx[MP(x[i] + 2, y[i])] : -1);
int id1 = (idx.count(MP(x[i], y[i] + 2)) ? idx[MP(x[i], y[i] + 2)] : -1);
if(id0 == -1 && id1 == -1) continue;
if(id0 != -1 && id1 == -1) add(i, id0);
if(id0 == -1 && id1 != -1) add(i, id1);
if(id0 != -1 && id1 != -1) {
if(root(id0) != root(id1)) {
add(i, id0); add(i, id1);
} else {
if(ord[id].first % 4 == 2) add(i, id1);
else add(i, id0);
}
}
}
if((int) u.size() != n - 1) return 0;
build(u, v, a, b);
return 1;
}
