// Be Name Khoda //
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int maxn5 = 1e6 + 10;
int n, q[maxn5], cnt[maxn5], ti, par[maxn5];
bool mark[maxn5];
vector <int> ret[2], ed[2], edg[maxn5];
vector <pair<int, int>> ver, toadd;
pair<pair <int, int>, pair<int, int>> adj[maxn5];
map <pair<int, int>, int> av, num;
bool bad(int i, int j, int x, int y){
if(i == x){
return (num[mp(i - 1, (j + y) / 2)] > 0 || num[mp(i + 1, (j + y) / 2)] > 0);
}
return (num[mp((i + x) / 2, j - 1)] > 0 || num[mp((i + x) / 2, j + 1)] > 0);
}
void dfs0(int v, int x, int y){
par[v] = ti;
av.erase(mp(x, y));
if(av.find(mp(x - 2, y)) != av.end() && !bad(x, y, x - 2, y)){
int u = av[mp(x - 2, y)];
ed[0].pb(v);
ed[1].pb(u);
num[mp(x - 1, y - 1)]++;
num[mp(x - 1, y + 1)]++;
dfs0(u, x - 2, y);
}
else if(av.find(mp(x - 2, y)) != av.end())
toadd.pb(mp(v, av[mp(x - 2, y)]));
if(av.find(mp(x + 2, y)) != av.end() && !bad(x, y, x + 2, y)){
int u = av[mp(x + 2, y)];
ed[0].pb(v);
ed[1].pb(u);
num[mp(x + 1, y - 1)]++;
num[mp(x + 1, y + 1)]++;
dfs0(u, x + 2, y);
}
else if(av.find(mp(x + 2, y)) != av.end())
toadd.pb(mp(v, av[mp(x + 2, y)]));
if(av.find(mp(x, y - 2)) != av.end() && !bad(x, y, x, y - 2)){
int u = av[mp(x, y - 2)];
ed[0].pb(v);
ed[1].pb(u);
num[mp(x - 1, y - 1)]++;
num[mp(x + 1, y - 1)]++;
dfs0(u, x, y - 2);
}
else if(av.find(mp(x, y - 2)) != av.end())
toadd.pb(mp(v, av[mp(x, y - 2)]));
if(av.find(mp(x, y + 2)) != av.end() && !bad(x, y, x, y + 2)){
int u = av[mp(x, y + 2)];
ed[0].pb(v);
ed[1].pb(u);
num[mp(x - 1, y + 1)]++;
num[mp(x + 1, y + 1)]++;
dfs0(u, x, y + 2);
}
else if(av.find(mp(x, y + 2)) != av.end())
toadd.pb(mp(v, av[mp(x, y + 2)]));
}
void dfs2(int v){
mark[v] = true;
for(auto u : edg[v]) if(!mark[u]){
mark[u] = true;
//debug(v);
//debug(u);
ret[0][v] = ver[u - (n - 1)].fi;
ret[1][v] = ver[u - (n - 1)].se;
for(auto z : edg[u]) if(!mark[z])
dfs2(z);
return;
}
}
int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}
int construct_roads(std::vector<int> x, std::vector<int> y) {
n = x.size();
for(int i = 0; i < n; i++){
av[mp(x[i], y[i])] = i;
}
for(int i = 0; i < n; i++) if(av.find(mp(x[i], y[i])) != av.end()){
ti = i;
dfs0(i, x[i], y[i]);
par[i] = -1;
}
shuffle(all(toadd), rng);
for(auto [u, v] : toadd){
int a = get_par(u);
int b = get_par(v);
if(a == b)
continue;
ed[0].pb(u);
ed[1].pb(v);
par[a] = b;
}
if(int(ed[0].size()) < n - 1)
return 0;
for(int i = 0; i < n - 1; i++){
if(x[ed[0][i]] == x[ed[1][i]]){
adj[i].fi = mp(x[ed[0][i]] - 1, (y[ed[0][i]] + y[ed[1][i]]) / 2);
adj[i].se = mp(x[ed[0][i]] + 1, (y[ed[0][i]] + y[ed[1][i]]) / 2);
}
else{
adj[i].fi = mp((x[ed[0][i]] + x[ed[1][i]]) / 2, y[ed[0][i]] - 1);
adj[i].se = mp((x[ed[0][i]] + x[ed[1][i]]) / 2, y[ed[0][i]] + 1);
}
ver.pb(adj[i].fi);
ver.pb(adj[i].se);
}
sort(all(ver));
ver.resize(unique(all(ver)) - ver.begin());
for(int i = 0; i < n - 1; i++){
int pt = lower_bound(all(ver), adj[i].fi) - ver.begin();
edg[i].pb(pt + n - 1);
pt = lower_bound(all(ver), adj[i].se) - ver.begin();
edg[i].pb(pt + n - 1);
edg[edg[i][0]].pb(i);
edg[edg[i][1]].pb(i);
cnt[edg[i][0]]++;
cnt[edg[i][1]]++;
}
/*
for(int i = 0; i < int(ver.size()) + n - 1; i++){
//debug(i);
for(auto u : edg[i])
cout << u << ' ';
cout << endl;
}
//*/
int l = 0, r = 0;
for(int i = 0; i < int(ver.size()); i++) if(edg[i + n - 1].size() == 1){
q[r++] = i + n - 1;
mark[i + n - 1] = true;
}
ret[0].resize(n - 1);
ret[1].resize(n - 1);
//debug(r);
while(l < r){
int v = q[l++];
for(auto u : edg[v]) if(!mark[u]){
mark[u] = true;
//debug(v);
//debug(u);
for(auto z : edg[u]){
cnt[z]--;
if(!mark[z] && cnt[z] == 1){
q[r++] = z;
mark[z] = true;
}
}
ret[0][u] = ver[v - (n - 1)].fi;
ret[1][u] = ver[v - (n - 1)].se;
}
}
//return 0;
//cout << ed[0].size() << ' ' << ed[1].size() << ' ' << ret[0].size() << ' ' << ret[1].size() << endl;
for(int i = 0; i < n - 1; i++) if(!mark[i])
dfs2(i);
build(ed[0], ed[1], ret[0], ret[1]);
return 1;
}
