#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> vid;
int di[2] = {2, 0};
int dj[2] = {0, 2};
struct edge {
int i1, j1, i2, j2;
};
vector<edge> edges;
const int N = 2e5+6;
struct DSU {
int p[N]={};
int sz[N];
DSU() {
iota(p, p+N, 0);
fill(sz, sz+N, 1);
}
int get(int a) {
return p[a] = (a == p[a] ? a : get(p[a]));
}
void merge(int a, int b) {
int x = get(a), y = get(b);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
}
};
vector<edge> horizontal, vertical;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
bool try_build() {
// srand(69420);
//0 - up(hor) (from road: -1;+1)
//1 - down(hor) (from road: +1;+1)
//2 - left(ver) (from road: +1;-1)
//3 - right(ver)(from road: +1;+1)
vector<int> tlx = {-1, 1, 1, 1};
vector<int> tly = {1, 1, -1, 1};
vector<int> dx = {0, 0, 2, 2};
vector<int> dy = {2, 2, 0, 0};
map<pair<int, int>, int> bench_dir;
for (const auto& e : horizontal) {
bench_dir[{e.i1-1, e.j1+1}] = 0;
}
auto sieve_down = [&] (int bi, int bj) -> void {
bench_dir.erase({bi, bj});
bi += 2;
while (bench_dir.count({bi, bj})) {
bench_dir[{bi, bj}] = 1;
bi += 2;
}
bench_dir[{bi, bj}] = 1;
};
for (const auto& e : vertical) {
int wi_left = e.i1+1;
int wj_left = e.j1-1;
int wi_right = e.i1+1;
int wj_right = e.j1+1;
if (bench_dir.count({wi_left, wj_left})) {
if (!bench_dir.count({wi_right, wj_right})) {
bench_dir[{wi_right, wj_right}] = 3;
continue;
}
int prev_dir = bench_dir[{wi_left, wj_left}];
if (prev_dir == 0) {
sieve_down(wi_left, wj_left);
bench_dir[{wi_left, wj_left}] = 2;
continue;
}
if (prev_dir == 1) {
int prev_dir2 = bench_dir[{wi_right, wj_right}];
if (prev_dir2 == 1) {
return false;
}
sieve_down(wi_right, wj_right);
bench_dir[{wi_right, wj_right}] = 3;
}
else if (prev_dir == 3) return false;
}
else {
bench_dir[{wi_left, wj_left}] = 2;
}
}
map<array<int, 4>, pair<int, int>> road_to_bench;
for (const auto& [x, y] : bench_dir) {
int tx = x.first-tlx[y];
int ty = x.second-tly[y];
int bx = tx+dx[y];
int by = ty+dy[y];
road_to_bench[{tx, ty, bx, by}] = {x.first, x.second};
}
vector<int> u, v, a, b;
for (const auto& e : horizontal) {
u.push_back(vid[{e.i1, e.j1}]);
v.push_back(vid[{e.i2, e.j2}]);
a.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].first);
b.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].second);
}
for (const auto& e : vertical) {
u.push_back(vid[{e.i1, e.j1}]);
v.push_back(vid[{e.i2, e.j2}]);
a.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].first);
b.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].second);
}
build(u, v, a, b);
return true;
}
int construct_roads(vector<int> x, vector<int> y) {
const int n = x.size();
for (int i = 0; i < n; ++i) {
vid[{x[i], y[i]}] = i;
}
vector<edge> all_vert;
vector<edge> all_hor;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
int ni = x[i] + di[j];
int nj = y[i] + dj[j];
auto it = vid.find({ni, nj});
if (it == vid.end()) continue;
edges.push_back({x[i], y[i], ni, nj});
bool hor = ni == x[i];
if (!hor) all_vert.push_back({x[i], y[i], ni, nj});
else all_hor.push_back({x[i], y[i], ni, nj});
}
}
for (int z = 0; z < 10; ++z) {
random_shuffle(all_hor.begin(), all_hor.end());
random_shuffle(all_vert.begin(), all_vert.end());
vertical.clear();
horizontal.clear();
DSU d;
auto add_vert = [&] (int vert_ind) -> void {
const edge& e = all_vert[vert_ind];
int id1 = vid[{e.i1, e.j1}];
int id2 = vid[{e.i2, e.j2}];
if (d.get(id1) == d.get(id2)) return;
d.merge(id1, id2);
vertical.push_back(e);
};
auto add_hor = [&] (int hor_ind) -> void {
const edge& e = all_hor[hor_ind];
int id1 = vid[{e.i1, e.j1}];
int id2 = vid[{e.i2, e.j2}];
if (d.get(id1) == d.get(id2)) return;
d.merge(id1, id2);
horizontal.push_back(e);
};
int vptr = 0;
int hptr = 0;
for (int i = 0; i < edges.size(); ++i) {
if (vptr == all_vert.size()) {
add_hor(hptr++);
continue;
}
if (hptr == all_hor.size()) {
add_vert(vptr++);
continue;
}
int r = rand() % 4;
if (r != 0) {
add_vert(vptr++);
}
else {
add_hor(hptr++);
}
}
if (d.sz[d.get(0)] != n) return 0;
sort(vertical.begin(), vertical.end(), [&](const edge& a, const edge& b) {
if (a.i1 != b.i1) return a.i1 < b.i1;
return a.j1 < b.j1;
});
int j = try_build();
if (j == 1) return true;
}
return false;
}
