#include<bits/stdc++.h>
#include "parks.h"
using namespace std;
using ll = long long;
ll n, m, q, k, x, y, a, b, c;
struct dsu {
ll n;
vector<ll> par;
vector<ll> sz;
dsu(ll N) : n(N) {
par.resize(n);
sz.resize(n);
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
}
ll find_p(ll x) {
if (par[x] == x) {
return x;
}
ll p = find_p(par[x]);
par[x] = p;
return p;
}
void join(ll x, ll y) {
x = find_p(x);
y = find_p(y);
if (x == y) {
return;
}
if (sz[y] > sz[x]) {
swap(x, y);
}
par[y] = x;
sz[x] += sz[y];
}
};
int construct_roads(vector<int> x, vector<int> y) {
n = x.size();
array< vector<int>, 4 > ans;
if (*max_element(x.begin(), x.end()) <= 6) {
vector< vector<ll> > v(7, vector<ll> (200001, -1));
for (int i = 0; i < n; i++) {
v[x[i]][y[i]] = i;
}
dsu d(n);
for (int i = 2; i < 200000; i += 2) {
if (v[2][i] != -1 && v[2][i + 2] != -1 && d.find_p(v[2][i]) != d.find_p(v[2][i + 2])) {
d.join(v[2][i], v[2][i + 2]);
ans[0].push_back(v[2][i]);
ans[1].push_back(v[2][i + 2]);
ans[2].push_back(1);
ans[3].push_back(i + 1);
}
if (v[6][i] != -1 && v[6][i + 2] != -1 && d.find_p(v[6][i]) != d.find_p(v[6][i + 2])) {
d.join(v[6][i], v[6][i + 2]);
ans[0].push_back(v[6][i]);
ans[1].push_back(v[6][i + 2]);
ans[2].push_back(7);
ans[3].push_back(i + 1);
}
}
vector< pair< ll, pair<ll, ll> > > vec;
for (int i = 2; i < 200000; i += 2) {
if (v[4][i] != -1 && v[4][i + 2] != -1 && d.find_p(v[4][i]) != d.find_p(v[4][i + 2])) {
d.join(v[4][i], v[4][i + 2]);
vec.push_back({i + 1, {v[4][i], v[4][i + 2]}});
}
}
for (int i = 2; i <= 200000; i += 2) {
if (v[4][i] != -1 && v[2][i] != -1 && d.find_p(v[4][i]) != d.find_p(v[2][i])) {
d.join(v[4][i], v[2][i]);
vec.push_back({i, {v[4][i], v[2][i]}});
}
if (v[4][i] != -1 && v[6][i] != -1 && d.find_p(v[4][i]) != d.find_p(v[6][i])) {
d.join(v[4][i], v[6][i]);
vec.push_back({i, {v[4][i], v[6][i]}});
}
}
set< pair<ll, ll> > st;
sort(vec.begin(), vec.end());
for (auto i : vec) {
if (i.first % 2 == 0) {
if (!st.count({(x[i.second.first] + x[i.second.second]) / 2, i.first - 1})) {
st.insert({(x[i.second.first] + x[i.second.second]) / 2, i.first - 1});
ans[0].push_back(i.second.first);
ans[1].push_back(i.second.second);
ans[2].push_back((x[i.second.first] + x[i.second.second]) / 2);
ans[3].push_back(i.first - 1);
}
else {
st.insert({(x[i.second.first] + x[i.second.second]) / 2, i.first + 1});
ans[0].push_back(i.second.first);
ans[1].push_back(i.second.second);
ans[2].push_back((x[i.second.first] + x[i.second.second]) / 2);
ans[3].push_back(i.first + 1);
}
}
else {
if (!st.count({(x[i.second.first] + x[i.second.second]) / 2 - 1, (y[i.second.first] + y[i.second.second]) / 2})) {
st.insert({(x[i.second.first] + x[i.second.second]) / 2 - 1, (y[i.second.first] + y[i.second.second]) / 2});
ans[0].push_back(i.second.first);
ans[1].push_back(i.second.second);
ans[2].push_back((x[i.second.first] + x[i.second.second]) / 2 - 1);
ans[3].push_back((y[i.second.first] + y[i.second.second]) / 2);
}
else {
st.insert({(x[i.second.first] + x[i.second.second]) / 2 + 1, (y[i.second.first] + y[i.second.second]) / 2});
ans[0].push_back(i.second.first);
ans[1].push_back(i.second.second);
ans[2].push_back((x[i.second.first] + x[i.second.second]) / 2 + 1);
ans[3].push_back((y[i.second.first] + y[i.second.second]) / 2);
}
}
}
if (d.sz[d.find_p(0)] != n) {
return 0;
}
build(ans[0], ans[1], ans[2], ans[3]);
return 1;
}
map< pair<ll, ll>, ll > pts;
for (int i = 0; i < n; i++) {
pts[{x[i], y[i]}] = i;
}
dsu d(n);
vector< pair< pair<ll, ll>, pair<ll, ll> > > vec;
for (int i = 0; i < n; i++) {
if (pts.count({x[i], y[i] - 2}) && d.find_p(i) != d.find_p(pts[{x[i], y[i] - 2}])) {
d.join(i, pts[{x[i], y[i] - 2}]);
vec.push_back({{x[i], y[i] - 1}, {i, pts[{x[i], y[i] - 2}]}});
}
if (pts.count({x[i], y[i] + 2}) && d.find_p(i) != d.find_p(pts[{x[i], y[i] + 2}])) {
d.join(i, pts[{x[i], y[i] + 2}]);
vec.push_back({{x[i], y[i] + 1}, {i, pts[{x[i], y[i] + 2}]}});
}
}
for (int i = 0; i < n; i++) {
if (pts.count({x[i] - 2, y[i]}) && d.find_p(i) != d.find_p(pts[{x[i] - 2, y[i]}])) {
d.join(i, pts[{x[i] - 2, y[i]}]);
vec.push_back({{x[i] - 1, y[i]}, {i, pts[{x[i] - 2, y[i]}]}});
}
if (pts.count({x[i] + 2, y[i]}) && d.find_p(i) != d.find_p(pts[{x[i] + 2, y[i]}])) {
d.join(i, pts[{x[i] + 2, y[i]}]);
vec.push_back({{x[i] + 1, y[i]}, {i, pts[{x[i] + 2, y[i]}]}});
}
}
set< pair<ll, ll> > st;
sort(vec.rbegin(), vec.rend());
for (auto i : vec) {
if (i.first.first % 2 == 0) {
if (!st.count({i.first.first + 1, i.first.second})) {
st.insert({i.first.first + 1, i.first.second});
ans[0].push_back(i.second.first);
ans[1].push_back(i.second.second);
ans[2].push_back(i.first.first + 1);
ans[3].push_back(i.first.second);
}
else {
st.insert({i.first.first - 1, i.first.second});
ans[0].push_back(i.second.first);
ans[1].push_back(i.second.second);
ans[2].push_back(i.first.first - 1);
ans[3].push_back(i.first.second);
}
}
else {
if (!st.count({i.first.first, i.first.second + 1})) {
st.insert({i.first.first, i.first.second + 1});
ans[0].push_back(i.second.first);
ans[1].push_back(i.second.second);
ans[2].push_back(i.first.first);
ans[3].push_back(i.first.second + 1);
}
else {
st.insert({i.first.first, i.first.second - 1});
ans[0].push_back(i.second.first);
ans[1].push_back(i.second.second);
ans[2].push_back(i.first.first);
ans[3].push_back(i.first.second - 1);
}
}
}
if (d.sz[d.find_p(0)] != n) {
return 0;
}
build(ans[0], ans[1], ans[2], ans[3]);
return 1;
}
