#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) cerr << "line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#include "parks.h"
map<pii, int> mp;
set<pii> occ;
vector<pii> es;
vector<int> x, y;
vector<int> dirx = {0, 0, 2, -2};
vector<int> diry = {2, -2, 0, 0};
namespace dsu {
int n, cnt;
vector<int> par, rk;
void init_(int _n) {
n = _n, cnt = n;
print(n, cnt);
par.assign(n, 0);
rk.assign(n, 0);
rep(i, 0, n - 1) par[i] = i;
}
int find_par(int x) {
if(par[par[x]] == par[x]) return par[x];
else return par[x] = find_par(par[x]);
}
void unite(int a, int b) {
int aa = find_par(a);
int bb = find_par(b);
if(aa == bb) return;
cnt --;
if(rk[aa] > rk[bb]) par[bb] = aa;
else if(rk[bb] > rk[aa]) par[aa] = bb;
else rk[aa] ++, par[bb] = aa;
}
bool same(int a, int b) {return find_par(a) == find_par(b);}
};
int type(pii c) {
int a = c.first, b = c.second;
if(x[a] == x[b] && abs(y[a] - y[b]) == 2) return 1;
else if(y[a] == y[b] && abs(x[a] - x[b]) == 2) return 2;
else return 0;
}
int construct_roads(vector<int> _x, vector<int> _y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
x = _x, y = _y;
int n = x.size();
mp.clear(), occ.clear();
es.clear();
dsu::init_(n);
rep(i, 0, n - 1) {
mp[pii(x[i], y[i])] = i;
rep(j, 0, 3) {
pii cur = {x[i] + dirx[j], y[i] + diry[j]};
if(mp.find(cur) == mp.end()) continue;
es.push_back({mp[cur], i});
}
}
vector<int> u, v, a, b;
vector<pii> use;
for(auto i : es) {
if(!dsu::same(i.first, i.second)) {
dsu::unite(i.first, i.second);
if(pii(x[i.first], y[i.first])
> pii(x[i.second], y[i.second])) swap(i.first, i.second);
use.push_back(i);
}
}
sort(use.begin(), use.end(), [](pii a, pii b){
pii aa = {x[a.first], y[a.first]};
pii bb = {x[b.first], y[b.first]};
if(aa == bb) return type(a) > type(b);
return aa < bb;
});
if(dsu::cnt != 1) return 0;
for(auto i : use) {
int xx = x[i.first], yy = y[i.first];
int tx, ty;
if(type(i) == 1) {
if(occ.find(pii(xx - 1, yy + 1)) == occ.end()) tx = xx - 1, ty = yy + 1;
else tx = xx + 1, ty = yy + 1;
}
else {
if(occ.find(pii(xx + 1, yy - 1)) == occ.end()) tx = xx + 1, ty = yy - 1;
else tx = xx + 1,ty = yy + 1;
}
u.push_back(i.first);
v.push_back(i.second);
a.push_back(tx);
b.push_back(ty);
occ.insert(pii(tx,ty));
}
build(u, v, a, b);
return 1;
}
