// In the name of Allah
#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define endl '\n'
#define sep ' '
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define pb push_back
#define Mp make_pair
const int maxn = 1e6 + 4;
int n;
vector<pii> adj[maxn]; set<pii> E;
vector<pii> arr, arrx;
int val[maxn], D[maxn];
int mark[maxn], h[maxn];
vector<int> ux, vx, X1, Y1;
int GI(pii x) {
int j = lower_bound(all(arr), x) - arr.begin();
if (j < len(arr) && arr[j] == x) return j;
else return -1;
}
int GIx(pii x) {
int j = lower_bound(all(arrx), x) - arrx.begin();
if (j < len(arrx) && arrx[j] == x) return j;
else return -1;
}
bool ok(int x, int y) {
int j = GI(Mp(x, y));
return (j != -1);
}
void addE(int x1, int y1, int x2, int y2) {
int u = val[GI(Mp(x1, y1))], v = val[GI(Mp(x2, y2))];
if (u > v) swap(u, v);
E.insert(Mp(u, v));
D[u]++; D[v]++;
}
void delE(int x1, int y1, int x2, int y2) {
int u = val[GI(Mp(x1, y1))], v = val[GI(Mp(x2, y2))];
if (u > v) swap(u, v);
E.erase(Mp(u, v));
D[u]--; D[v]--;
}
void dfs(int v) {
mark[v] = 1;
for (auto f : adj[v]) {
int u = f.F, j = f.S;
if (!mark[u]) dfs(u);
}
}
void res_dfs(int v, int i = -1) {
mark[v] = 1;
for (auto f : adj[v]) {
int u = f.F, j = f.S;
if (!mark[u]) {
h[u] = h[v] + 1;
res_dfs(u, j);
X1[j] = arrx[u].F; Y1[j] = arrx[u].S;
}
else if (j != i && h[u] < h[v]) {
X1[j] = arrx[u].F; Y1[j] = arrx[u].S;
}
}
}
bool checkx() {
for (auto f : E) {
int u = f.F, v = f.S;
adj[u].pb(Mp(v, -1)); adj[v].pb(Mp(u, -1));
}
dfs(0);
for (int i = 0; i < n; i++) {
if (!mark[i]) return 0;
}
for (int i = 0; i < n; i++) {
mark[i] = 0; adj[i].clear();
}
return 1;
}
int construct_roads(vector<int> X, vector<int> Y) {
n = len(X);
for (int i = 0; i < n; i++) arr.pb(Mp(X[i], Y[i]));
sort(all(arr));
for (int i = 0; i < n; i++) {
int j = GI(Mp(X[i], Y[i]));
val[j] = i;
}
for (int i = 0; i < n; i++) {
if (ok(X[i], Y[i] + 2)) {
addE(X[i], Y[i], X[i], Y[i] + 2);
}
if (ok(X[i] + 2, Y[i]) && (!ok(X[i], Y[i] - 2) || !ok(X[i] + 2, Y[i] - 2))) {
addE(X[i], Y[i], X[i] + 2, Y[i]);
}
}
for (int i = 0; i < n; i++) {
if (D[i] == 4) {
if (ok(X[i] + 2, Y[i] + 2)) {
delE(X[i], Y[i], X[i] + 2, Y[i]);
addE(X[i], Y[i] + 2, X[i] + 2, Y[i] + 2);
}
else if (ok(X[i] - 2, Y[i] - 2)) {
delE(X[i], Y[i], X[i] - 2, Y[i]);
addE(X[i], Y[i] - 2, X[i] - 2, Y[i] - 2);
}
}
}
if (!checkx()) return 0;
for (auto f : E) {
int u = f.F, v = f.S; pii f1, f2;
int x = (X[u] + X[v]) / 2, y = (Y[u] + Y[v]) / 2;
if (X[u] == X[v]) {
f1 = Mp(x - 1, y); f2 = Mp(x + 1, y);
}
else {
f1 = Mp(x, y - 1); f2 = Mp(x, y + 1);
}
arrx.pb(f1); arrx.pb(f2);
}
sort(all(arrx)); arrx.resize(unique(all(arrx)) - arrx.begin());
for (auto f : E) {
int u = f.F, v = f.S; pii f1, f2;
int x = (X[u] + X[v]) / 2, y = (Y[u] + Y[v]) / 2;
if (X[u] == X[v]) {
f1 = Mp(x - 1, y); f2 = Mp(x + 1, y);
}
else {
f1 = Mp(x, y - 1); f2 = Mp(x, y + 1);
}
int u1 = GIx(f1), v1 = GIx(f2);
adj[u1].pb(Mp(v1, len(ux))); adj[v1].pb(Mp(u1, len(vx)));
ux.pb(u); vx.pb(v);
}
X1.resize(len(arrx)); Y1.resize(len(arrx));
for (int i = 0; i < len(arrx); i++) {
if (!mark[i]) res_dfs(i);
}
build(ux, vx, X1, Y1);
return 1;
}
