#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXY = 2e5 + 5;
map<pair<int, int>, int> mp;
vector<pair<int, int>> inY[MAXY];
int construct_roads(vector<int> x, vector<int> y) {
int n = (int) x.size();
for (int i = 0; i < n; ++i) {
inY[y[i]].emplace_back(x[i], i);
mp[{x[i], y[i]}] = i;
}
set<pair<int, int>> se;
vector<int> u, v, a, b;
vector<vector<int>> g(n);
auto addedge = [&](int uu, int vv, int aa, int bb) {
u.push_back(uu);
v.push_back(vv);
a.push_back(aa);
b.push_back(bb);
g[uu].push_back(vv);
g[vv].push_back(uu);
se.insert({aa, bb});
};
for (int cury = 2; cury < MAXY; cury += 2) {//add vertical lines
int cnt = 0;
sort(inY[cury].begin(), inY[cury].end());
for (int j = 0; j < (int) inY[cury].size(); ++j) {
auto [curx, id] = inY[cury][j];
if (mp.count({curx, cury + 2})) {
cnt++;
}
}
for (int j = 0; j < (int) inY[cury].size(); ++j) {
auto [curx, id] = inY[cury][j];
if (!mp.count({curx, cury + 2})) {
continue;
}
addedge(id, mp[{curx, cury + 2}], curx - 1, cury + 1);
//if (curx == 2) {
//} else if (curx == 6) {
//addedge(id, mp[{curx, cury + 2}], curx + 1, cury + 1);
//} else if (cnt == 1) {
//addedge(id, mp[{curx, cury + 2}], curx + (cury % 4 == 0 ? -1 : 1), cury + 1);
//}
}
}
for (int cury = 2; cury < MAXY; cury += 2) {//add horizontal lines (x, y) -> (x + 2, y)
for (int j = 0; j < (int) inY[cury].size() - 1; ++j) {
auto [curx, id] = inY[cury][j];
if (inY[cury][j + 1].first - curx > 2) continue;
if (se.count({curx + 1, cury - 1})) {
addedge(id, inY[cury][j + 1].second, curx + 1, cury + 1);
} else {
addedge(id, inY[cury][j + 1].second, curx + 1, cury - 1);
}
}
}
vector<bool> vis(n);
function<void(int)> dfs = [&](int nd) {
vis[nd] = true;
for (int ch : g[nd]) {
if (!vis[ch]) {
dfs(ch);
}
}
};
dfs(0);
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
return 0;
}
}
build(u, v, a, b);
return 1;
}
