#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int p[N];
int sz[N];
set<int> se[N];
set<int> to_cross[N];
set<pair<int, int>> from_cross[N];
int get(int v) {
return p[v] = (p[v] == v ? v : get(p[v]));
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (sz[u] > sz[v]) swap(u, v);
p[u] = v;
sz[v] += sz[u];
}
int construct_roads(vector<int> vx, vector<int> vy) {
int n = (int) vx.size();
map<pair<int, int>, int> mp;
for (int i = 0; i < n; ++i) {
p[i] = i;
sz[i] = 1;
mp[{vx[i], vy[i]}] = i;
}
for (int i = 0; i < n; ++i) {
int x = vx[i], y = vy[i];
for (int dx : {-2, 0, 2}) {
for (int dy : {-2, 0, 2}) {
if (dx != 0 && dy != 0) continue;
if (mp.count({x + dx, y + dy})) {
int id = mp[{x + dx, y + dy}];
if (get(id) != get(i)) {
unite(i, id);
se[i].insert(id);
se[id].insert(i);
}
}
}
}
}
if (sz[get(1)] != n) {
return 0;
}
vector<int> u, v, a, b;
for (int i = 0; i < n; ++i) {
bool ok = true;
int x = vx[i], y = vy[i];
for (int dx : {-2, 0, 2}) {
for (int dy : {-2, 0, 2}) {
if (dx != 0 && dy != 0) continue;
ok &= mp.count({x + dx, y + dy});
}
}
if (ok) {
for (int dx : {-2, 2}) {
int id = mp[{x + dx, y}];
u.push_back(i);
v.push_back(id);
a.push_back(x + dx / 2);
b.push_back(y + (dx < 0 ? -1 : 1));
se[id].erase(i);
se[i].erase(id);
}
for (int dy : {-2, 2}) {
int id = mp[{x, y + dy}];
u.push_back(i);
v.push_back(id);
a.push_back(x + (dy < 0 ? 1 : -1));
b.push_back(y + dy / 2);
se[id].erase(i);
se[i].erase(id);
}
}
}
int cnt = 0;
vector<int> type;
vector<set<int>> g;
map<pair<int, int>, int> crosses;
map<int, pair<int, int>> lines, bck;
for (int i = 0; i < n; ++i) {
int x = vx[i], y = vy[i];
for (int id : se[i]) {
if (id < i) continue;
int xx = vx[id], yy = vy[id];
int line_id = cnt;
type.push_back(0);//type[cnt]
g.push_back({});
lines[cnt++] = {i, id};
for (int d : {-1, 1}) {
int cx, cy;
if (x == xx) {
cx = x + d, cy = (y + yy) / 2;
} else {
cx = (x + xx) / 2, cy = y + d;
}
if (!crosses.count({cx, cy})) {
g.push_back({});
type.push_back(1);
bck[cnt] = {cx, cy};
crosses[{cx, cy}] = cnt++;
}
int cross_id = crosses[{cx, cy}];
g[cross_id].insert(line_id);
g[line_id].insert(cross_id);
}
}
}
queue<int> que;
vector<int> indeg(cnt);
for (int i = 0; i < cnt; ++i) {
indeg[i] = g[i].size();
if (g[i].size() == 1) {
assert(type[i] == 1);
que.push(i);
}
}
set<int> mentioned;
while (!que.empty()) {
int cur = que.front();
que.pop();
if (indeg[cur] == 0) {
continue;
}
if (type[cur] == 0) {
for (int w : g[cur]) {
g[w].erase(cur);
--indeg[w];
if (indeg[w] == 1) {
que.push(w);
}
}
} else {
int line_id = *g[cur].begin();
if (!mentioned.count(line_id)) {
mentioned.insert(line_id);
u.push_back(lines[line_id].first);
v.push_back(lines[line_id].second);
a.push_back(bck[cur].first);
b.push_back(bck[cur].second);
}
for (int w : g[cur]) {
g[w].erase(cur);
--indeg[w];
if (indeg[w] == 1) {
que.push(w);
}
}
}
}
build(u, v, a, b);
return 1;
}
