#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include "parks.h"
using namespace std;
const int N = 1<<18;
int Par[N], Sz[N];
map<int, int> seen[N], pt[N];
vector<int> X, Y, v1, v2, v3, v4;
int root(int v){
return (Par[v] == 0 ? v : Par[v] = root(Par[v]));
}
void merge(int a, int b){
if (min(a, b) == 0 or root(a) == root(b))
return;
int px, py;
if (Y[a] == Y[b]){
px = X[a]+1, py = Y[a]-1;
if ((X[a] & 2) ^ (Y[a] & 2))
py += 2;
}
else{
px = X[a] - 1, py = Y[a]+1;
if ((px & 2) ^ (py & 2))
px += 2;
}
if (seen[px][py])
return;
seen[px][py] = 1;
Sz[root(b)] += Sz[root(a)];
Par[root(a)] = root(b);
v1.push_back(a-1);
v2.push_back(b-1);
v3.push_back(px);
v4.push_back(py);
}
int construct_roads(vector<int> A, vector<int> B){
X = A, Y = B;
int n = X.size();
X.insert(X.begin(), 0);
Y.insert(Y.begin(), 0);
vector<pair<int, int>> vc;
for (int i=1;i<=n;i++){
vc.push_back({X[i], Y[i]});
pt[X[i]][Y[i]] = i;
Sz[i] = 1;
}
sort(begin(vc), end(vc));
for (auto [x, y] : vc){
merge(pt[x][y], pt[x][y+2]);
merge(pt[x][y], pt[x+2][y]);
}
if (Sz[root(1)] == n)
return build(v1, v2, v3, v4), 1;
return 0;
}
