using namespace std;
#include <vector>
#include "parks.h"
#include <map>
#define pi pair<int,int>
#define vi vector<int>
const int siz = 2e5 + 2;
map<pi, int> m;
int my[siz];
vi col[siz];
#include <set>
bool con(int a, int b) {
if (my[a] == my[b])return 0;
a = my[a], b = my[b];
if (col[a].size() > col[b].size())swap(a, b);
for (int x : col[a]) {
my[x] = b;
col[b].push_back(x);
}
return 1;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
for (int i = 0; i < n; i++) {
m[{x[i], y[i]}] = i + 1;
}
vector<pi> ed1, ed2;
for (int i = 0; i < n; i++) {
if (m[{x[i] + 2, y[i]}])ed2.push_back({ i+1,m[{x[i] + 2, y[i]}] });
if (m[{x[i], y[i] + 2}])ed1.push_back({ i+1,m[{x[i],y[i] + 2}] });
}
vector<pi> ed; for (pi p : ed2)ed.push_back(p); for (pi p : ed1)ed.push_back(p);
vector<pi> ans;
for (int i = 0; i <= n; i++) {
my[i] = i; col[i].push_back(i);
}
for (pi e : ed) {
if (con(e.first, e.second))ans.push_back(e);
}
if (ans.size()+1 < n )return 0;
vi ans1(n - 1), ans2(n - 1), ans3(n - 1), ans4(n - 1);
for (int i = 0; i < n - 1; i++) {
ans1[i] = ans[i].first - 1; ans2[i] = ans[i].second - 1;
}
map<pi, vi> fr;
vector<vector<pi>> fr2(n - 1);
for (int i = 0; i < n - 1; i++) {
if (x[ans[i].first - 1] == x[ans[i].second - 1]) {
int mid = (y[ans[i].first - 1] + y[ans[i].second - 1]) / 2;
fr[{x[ans[i].first - 1]-1, mid}].push_back(i);
fr[{x[ans[i].first - 1]+1, mid}].push_back(i);
fr2[i].push_back({ x[ans[i].first - 1]-1, mid });
fr2[i].push_back({ x[ans[i].first - 1]+1, mid });
}
else {
int mid = (x[ans[i].first - 1] + x[ans[i].second - 1]) / 2;
fr[{mid,y[ans[i].first - 1]+1}].push_back(i);
fr[{mid,y[ans[i].first - 1]-1}].push_back(i);
fr2[i].push_back( {mid,y[ans[i].first - 1]-1 });
fr2[i].push_back( {mid,y[ans[i].first - 1]+1} );
}
}
for (pair<pi,vi> p : fr) {
pi poi = p.first;
while (fr[poi].size() == 1) {
int i = fr[poi][0];
fr[poi].pop_back();
if (fr2[i].back() != poi)swap(fr2[i][0], fr2[i][1]);
fr2[i].pop_back();
ans3[i] = poi.first, ans4[i] = poi.second;
if (fr2[i].size() == 1) {
poi = fr2[i][0];
if (fr[poi].size()) {
if (fr[poi].back() != i)swap(fr[poi][0], fr[poi][1]);
fr[poi].pop_back();
}
}
}
}
for (pair<pi, vi> p : fr) {
pi poi = p.first;
if (p.second.size() == 2)fr[poi].pop_back();
while (fr[poi].size() == 1) {
int i = fr[poi][0];
fr[poi].pop_back();
if (fr2[i].back() != poi)swap(fr2[i][0], fr2[i][1]);
fr2[i].pop_back();
ans3[i] = poi.first, ans4[i] = poi.second;
if (fr2[i].size() == 1) {
poi = fr2[i][0];
if (fr[poi].size()) {
if (fr[poi].back() != i)swap(fr[poi][0], fr[poi][1]);
fr[poi].pop_back();
}
}
}
}
build(ans1, ans2, ans3, ans4);
return 1;
}
