#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 build(vi A, vi B, vi C, vi D);
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;
// }