// 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;
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;
vector <int> ret[2], ed[2];
map <pair<int, int>, int> av, cnt, idof;
set <pair<pair<int, int>, pair<int, int>>> rem;
void dfs(int v, int x, int y){
av.erase(mp(x, y));
if(av.find(mp(x - 2, y)) != av.end()){
int u = av[mp(x - 2, y)];
dfs(u, x - 2, y);
}
if(av.find(mp(x + 2, y)) != av.end()){
int u = av[mp(x + 2, y)];
dfs(u, x + 2, y);
}
if(av.find(mp(x, y - 2)) != av.end()){
int u = av[mp(x, y - 2)];
dfs(u, x, y - 2);
}
if(av.find(mp(x, y + 2)) != av.end()){
int u = av[mp(x, y + 2)];
dfs(u, x, y + 2);
}
}
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;
dfs(0, x[0], y[0]);
if(av.size())
return 0;
for(int i = 0; i < n; i++){
cnt[mp(x[i] - 1, y[i] - 1)]++;
cnt[mp(x[i] + 1, y[i] - 1)]++;
cnt[mp(x[i] - 1, y[i] + 1)]++;
cnt[mp(x[i] + 1, y[i] + 1)]++;
idof[mp(x[i], y[i])] = i;
}
for(auto it = cnt.begin(); it != cnt.end(); it++) if(it -> se == 4){
int x = (it -> fi).fi, y = (it -> fi).se;
x--; y--;
if(((x / 2) + (y / 2)) % 2){ // is black
rem.insert({{x, y}, {x + 2, y}});
}
else{ // is white
rem.insert({{x, y}, {x, y + 2}});
}
}
for(int i = 0; i < n; i++){
if(idof.find(mp(x[i] + 2, y[i])) != idof.end() &&
rem.find(mp(mp(x[i], y[i]), mp(x[i] + 2, y[i]))) == rem.end()){
ed[0].pb(i);
ed[1].pb(idof[mp(x[i] + 2, y[i])]);
ret[0].pb(x[i] + 1);
if(((x[i] / 2) + (y[i] / 2)) % 2)
ret[1].pb(y[i] + 1);
else
ret[1].pb(y[i] - 1);
}
if(idof.find(mp(x[i], y[i] + 2)) != idof.end() &&
rem.find(mp(mp(x[i], y[i]), mp(x[i], y[i] + 2))) == rem.end()){
ed[0].pb(i);
ed[1].pb(idof[mp(x[i], y[i] + 2)]);
ret[1].pb(y[i] + 1);
if(((x[i] / 2) + (y[i] / 2)) % 2)
ret[0].pb(x[i] + 1);
else
ret[0].pb(x[i] - 1);
}
}
build(ed[0], ed[1], ret[0], ret[1]);
return 1;
}
