#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> mp;
vector<bool> vis;
vector<int> dx = {-2, 2, 0, 0};
vector<int> dy = {0, 0, -2, 2};
vector<pair<int, int>> roads;
void dfs(int x, int y){
int u = mp[make_pair(x, y)];
for(int i = 0; i < 4; i++){
int x2 = x+dx[i], y2 = y+dy[i];
if(mp.count(make_pair(x2, y2))){
int v = mp[make_pair(x2, y2)];
if(!vis[v]){
vis[v] = true;
dfs(x2, y2);
roads.emplace_back(u, v);
}
}
}
}
pair<pair<int, int>, pair<int, int>> getBench(int x1, int y1, int x2, int y2){
if(x1 == x2) return {{x1+1, (y1+y2)/2}, {x1-1, (y1+y2)/2}};
else return {{(x1+x2)/2, y1+1}, {(x1+x2)/2, y1-1}};
}
vector<vector<int>> g;
vector<int> match;
bool find_path(int u){
for(int v : g[u]){
if(!vis[v]){
vis[v] = true;
if(match[v] == -1 || find_path(match[v])){
match[v] = u;
match[u] = v;
return true;
}
}
}
return false;
}
int construct_roads(vector<int> x, vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = (int)x.size();
for(int i = 0; i < n; i++){
mp.emplace(make_pair(x[i], y[i]), i);
}
vis.resize(n);
vis[0] = true;
dfs(x[0], y[0]);
for(int i = 0; i < n; i++){
if(!vis[i]) return 0;
}
g.resize(n-1);
vector<pair<int, int>> benches;
map<pair<int, int>, int> ind;
for(int i = 0; i < n-1; i++){
int u = roads[i].first, v = roads[i].second;
auto [a, b] = getBench(x[u], y[u], x[v], y[v]);
if(!ind.count(a)){
ind[a] = (int)benches.size();
benches.push_back(a);
}
if(!ind.count(b)){
ind[b] = (int)benches.size();
benches.push_back(b);
}
g[i].push_back(ind[a]+n-1);
g[i].push_back(ind[b]+n-1);
}
int m = n+(int)ind.size();
match.assign(m, -1);
int sz = 0;
while(true){
int old = sz;
vis.assign(m, false);
for(int u = 0; u < n-1; u++){
if(match[u] == -1) sz += find_path(u);
}
if(sz == old) break;
}
assert(sz == n-1);
vector<int> u, v, a, b;
for(int i = 0; i < n-1; i++){
u.push_back(roads[i].first);
v.push_back(roads[i].second);
a.push_back(benches[match[i]-n+1].first);
b.push_back(benches[match[i]-n+1].second);
}
build(u, v, a, b);
return 1;
}
