#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
#define i128 __int128
using namespace std;
const int N = 1e6 + 7, mod = 1e9 + 7;
map<int,int>mp[N];
set<int> ex[N], ey[N];
void construct_roads(vi x, vi y) {
L(i, 0, sz(x) - 1) {
mp[x[i]][y[i]] = i;
}
L(i, 0, sz(x) - 1) {
if(mp[x[i]].count(y[i] + 2)) {
ex[x[i]].insert(y[i]);
}
}
L(i, 0, sz(x) - 1) {
if(mp[x[i] + 2].count(y[i])) {
ey[y[i]].insert(x[i]);
}
}
L(i, 0, sz(x) - 1) {
if(mp[x[i]].count(y[i] + 2) && mp[x[i] + 2].count(y[i]) && mp[x[i] + 2].count(y[i] + 2)) {
int op = ((x[i] + y[i]) / 2) & 1;
if(op == 0) ex[x[i]].erase(y[i]);
else ey[y[i]].erase(x[i]);
}
}
vi U, V, A, B;
L(x, 0, N - 1) {
for(auto&y : ex[x]) {
U.pb(mp[x][y]);
V.pb(mp[x][y + 2]);
if((((x + y) / 2) & 1) == 0)
A.pb(x + 1), B.pb(y + 1);
else
A.pb(x - 1), B.pb(y + 1);
}
}
L(y, 0, N - 1) {
for(auto&x : ey[y]) {
U.pb(mp[x][y]);
V.pb(mp[x + 2][y]);
if((((x + y) / 2) & 1) == 1)
A.pb(x + 1), B.pb(y + 1);
else
A.pb(x + 1), B.pb(y - 1);
}
}
build(U, V, A, B);
}
// int main() {
// construct_roads(vi{4, 4, 6, 4, 2}, vi{4, 6, 4, 2, 4});
// return 0;
// }