#include "parks.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 200005;
int n, par[nmax];
vector<pair<int,int>>vertex;
map <pair<int,int>, int>varfuri, banci;
vector<int>u, v, assigned_a, assigned_b;
int findpar(int x){
if(x != par[x]){
par[x] = findpar(par[x]);
}
return par[x];
}
void join(int x, int y){
x = findpar(x);
y = findpar(y);
par[x] = y;
}
int construct_roads(vector<int> x, vector<int> y) {
n = (int)x.size();
for(int i=0;i<n;i++){
vertex.push_back({x[i], y[i]});
varfuri[{x[i], y[i]}] = i;
}
sort(all(vertex));
for(auto it : vertex){
if(varfuri.count({it.fr - 2, it.sc})){
if(it.fr % 4 == 0){
if(it.sc % 4 == 2){
if(!banci.count({it.fr - 1, it.sc - 1})){
banci[{it.fr-1, it.sc-1}] = 1;
u.push_back(varfuri[{it.fr, it.sc}]);
v.push_back(varfuri[{it.fr - 2, it.sc}]);
assigned_a.push_back(it.fr - 1);
assigned_b.push_back(it.sc - 1);
}
}
else{
if(!banci.count({it.fr - 1, it.sc + 1})){
banci[{it.fr-1, it.sc + 1}] = 1;
u.push_back(varfuri[{it.fr, it.sc}]);
v.push_back(varfuri[{it.fr - 2, it.sc}]);
assigned_a.push_back(it.fr - 1);
assigned_b.push_back(it.sc + 1);
}
}
}
else{
if(it.sc % 4 == 2){
if(!banci.count({it.fr - 1, it.sc + 1})){
banci[{it.fr-1, it.sc+1}] = 1;
u.push_back(varfuri[{it.fr, it.sc}]);
v.push_back(varfuri[{it.fr - 2, it.sc}]);
assigned_a.push_back(it.fr - 1);
assigned_b.push_back(it.sc + 1);
}
}
else{
if(!banci.count({it.fr - 1, it.sc - 1})){
banci[{it.fr-1, it.sc-1}] = 1;
u.push_back(varfuri[{it.fr, it.sc}]);
v.push_back(varfuri[{it.fr - 2, it.sc}]);
assigned_a.push_back(it.fr - 1);
assigned_b.push_back(it.sc - 1);
}
}
}
}
if(varfuri.count({it.fr, it.sc - 2})){
if(it.fr % 4 == 0){
if(it.sc % 4 == 2){
if(!banci.count({it.fr + 1, it.sc - 1})){
banci[{it.fr + 1, it.sc - 1}] = 1;
u.push_back(varfuri[{it.fr, it.sc}]);
v.push_back(varfuri[{it.fr, it.sc - 2}]);
assigned_a.push_back(it.fr + 1);
assigned_b.push_back(it.sc - 1);
}
}
else{
if(!banci.count({it.fr - 1, it.sc - 1})){
banci[{it.fr-1, it.sc - 1}] = 1;
u.push_back(varfuri[{it.fr, it.sc}]);
v.push_back(varfuri[{it.fr, it.sc - 2}]);
assigned_a.push_back(it.fr - 1);
assigned_b.push_back(it.sc - 1);
}
}
}
else{
if(it.sc % 4 == 2){
if(!banci.count({it.fr - 1, it.sc - 1})){
banci[{it.fr-1, it.sc-1}] = 1;
u.push_back(varfuri[{it.fr, it.sc}]);
v.push_back(varfuri[{it.fr, it.sc - 2}]);
assigned_a.push_back(it.fr - 1);
assigned_b.push_back(it.sc - 1);
}
}
else{
if(!banci.count({it.fr + 1, it.sc - 1})){
banci[{it.fr+1, it.sc-1}] = 1;
u.push_back(varfuri[{it.fr, it.sc}]);
v.push_back(varfuri[{it.fr, it.sc - 2}]);
assigned_a.push_back(it.fr + 1);
assigned_b.push_back(it.sc - 1);
}
}
}
}
}
for(int i=0;i<n;i++) par[i] = i;
for(int i=0;i<(int)u.size();i++){
join(u[i], v[i]);
}
for(int i=0;i<n;i++){
findpar(i);
}
for(int i=0;i<n-1;i++){
if(par[i] != par[i + 1]) return 0;
}
build(u, v, assigned_a, assigned_b);
return 1;
}
