#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
int ret(vector<pair<int, int>> vec1, vector<pair<int, int>> vec2) {
vector<int> a, b, c, d;
for (auto &[x, y]: vec1) a.pb(x), b.pb(y);
for (auto &[x, y]: vec2) c.pb(x), d.pb(y);
build(a, b, c, d);
return 1;
}
int n;
int construct_roads(vector<int> x, vector<int> y) {
n=sz(x);
map<pair<int, int>, int> mp; for (int i=0; i<n; i++) mp[{x[i], y[i]}]=i;
vector<pair<int, int>> bridges;
vector<bool> vis(n, 0); vis[0]=1;
queue<int> q; q.push(0);
while (!q.empty()) {
int i=q.front(); q.pop();
if (mp.count({x[i]+2, y[i]}) && !vis[mp[{x[i]+2, y[i]}]]) {
int j=mp[{x[i]+2, y[i]}];
vis[j]=1;
bridges.pb({i, j});
q.push(j);
}
if (mp.count({x[i]-2, y[i]}) && !vis[mp[{x[i]-2, y[i]}]]) {
int j=mp[{x[i]-2, y[i]}];
vis[j]=1;
bridges.pb({i, j});
q.push(j);
}
if (mp.count({x[i], y[i]+2}) && !vis[mp[{x[i], y[i]+2}]]) {
int j=mp[{x[i], y[i]+2}];
vis[j]=1;
bridges.pb({i, j});
q.push(j);
}
if (mp.count({x[i], y[i]-2}) && !vis[mp[{x[i], y[i]-2}]]) {
int j=mp[{x[i], y[i]-2}];
vis[j]=1;
bridges.pb({i, j});
q.push(j);
}
}
for (int i=0; i<n; i++) if (!vis[i]) return 0;
assert(sz(bridges)==n-1);
map<pair<int, int>, vector<int>> mpp;
vector<vector<pair<int, int>>> can;
for (int i=0; i<n-1; i++) {
int a=x[bridges[i].fi], b=y[bridges[i].fi], u=x[bridges[i].se], v=y[bridges[i].se]; can.pb({});
if (a==u) {
mpp[{a-1, (b+v)/2}].pb(i);
mpp[{a+1, (b+v)/2}].pb(i);
can.back().pb({a-1, (b+v)/2});
can.back().pb({a+1, (b+v)/2});
} else {
mpp[{(a+u)/2, b-1}].pb(i);
mpp[{(a+u)/2, b+1}].pb(i);
can.back().pb({(a+u)/2, b-1});
can.back().pb({(a+u)/2, b+1});
}
// cout << a << ' ' << b << " - " << u << ' ' << v << endl;
}
set<pair<int, int>> already;
vector<int> pos(n-1, 2);
set<pair<int, int>> st; for (int i=0; i<n-1; i++) st.insert({2, i});
vector<pair<int, int>> empls(n-1);
while (!st.empty()) {
auto i=st.begin()->se; st.erase(st.begin());
if (already.count(can[i][0])) swap(can[i][0], can[i][1]);
already.insert(can[i][0]);
empls[i]=can[i][0];
// cout << i << ": " << can[i][0].fi << ' ' << can[i][0].se << endl;
for (auto &u: mpp[can[i][0]]) if (st.count({pos[u], u})) {
st.erase({pos[u], u});
pos[u]--;
assert(pos[u]>0);
st.insert({pos[u], u});
}
}
return ret(bridges, empls);
}
