#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pll;
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1e6 + 10;
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, -1, 0, 1};
namespace answer {
vector<int> u, v, a, b;
}
vector<pair<pll, int>> edges;
int X[MAXN], Y[MAXN], par[MAXN], n;
map<pll, int> mp;
int find(int v) {
return par[v] == v ? v : par[v] = find(par[v]);
}
inline bool unite(int u_, int v_) {
int u = find(u_), v = find(v_);
if (u == v) return false;
edges.push_back({{u_, v_}, (int)answer::u.size()});
answer::u.push_back(u_);
answer::v.push_back(v_);
par[u] = v;
return true;
}
int construct_roads(vector<int> x_, vector<int> y_) {
n = x_.size();
for (int i = 0; i < n; i++) {
X[i] = x_[i];
Y[i] = y_[i];
mp[pll(X[i], Y[i])] = i;
par[i] = i;
}
int edg = 0;
for (int i = 0; i < 4; i++) {
for (int v = 0; v < n; v++) {
int ux = X[v] + 2 * DX[i], uy = Y[v] + 2 * DY[i];
auto it = mp.find(pll(ux, uy));
if (it == mp.end()) continue;
int u = it -> second;
edg += unite(u, v);
}
}
if (edg < n - 1) return 0;
sort(all(edges), [] (const pair<pll, int>& a, const pair<pll, int>& b) {
return min(X[a.X.X], X[a.X.Y]) < min(X[b.X.X], X[b.X.Y]);
});
set<pll> st;
answer::a.resize(n - 1);
answer::b.resize(n - 1);
for (int ti = 0; ti < n - 1; ti++) {
int i = edges[ti].Y;
if (X[answer::u[i]] == X[answer::v[i]]) {
int tx = X[answer::u[i]] - 1, ty = (Y[answer::u[i]] + Y[answer::v[i]]) / 2;
if (st.find(pll(tx, ty)) == st.end()) {
st.insert(pll(tx, ty));
answer::a[i] = tx;
answer::b[i] = ty;
continue;
}
tx += 2;
if (st.find(pll(tx, ty)) == st.end()) {
st.insert(pll(tx, ty));
answer::a[i] = tx;
answer::b[i] = ty;
continue;
}
return 0;
} else {
int ty = Y[answer::u[i]] - 1, tx = (X[answer::u[i]] + X[answer::v[i]]) / 2;
if (st.find(pll(tx, ty)) == st.end()) {
st.insert(pll(tx, ty));
answer::a[i] = tx;
answer::b[i] = ty;
continue;
}
ty += 2;
if (st.find(pll(tx, ty)) == st.end()) {
st.insert(pll(tx, ty));
answer::a[i] = tx;
answer::b[i] = ty;
continue;
}
return 0;
}
}
build(answer::u, answer::v, answer::a, answer::b);
return 1;
}
