#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
const int dir[4][2] = {{2, 0}, {-2, 0}, {0, 2}, {0, -2}};
const int N = 3e5 + 20;
int X[N], Y[N];
map<ar<int, 2>, int > mp;
vector<int> U, V, A, B;
bool vis[N];
void dfs(int x){
vis[x] = 1;
for(int i = 0;i < 4;i++){
if(mp.count(ar<int, 2>{X[x] + dir[i][0], Y[x] + dir[i][1]})){
int u = mp[ar<int, 2>{X[x] + dir[i][0], Y[x] + dir[i][1]}];
if(vis[u])continue;
U.push_back(x);
V.push_back(u);
if(X[x] == X[u]){
B.push_back({Y[x] + (Y[x] < Y[u] ? 1 : -1)});
if((X[u] + Y[u]) & 2)A.push_back({X[x] + (Y[x] > Y[u] ? 1 : -1)});
else A.push_back({X[x] + (Y[x] < Y[u] ? 1 : -1)});
}else{
A.push_back({X[x] + (X[x] < X[u] ? 1 : -1)});
if((X[u] + Y[u]) & 2)B.push_back({Y[x] + (X[x] > X[u] ? 1 : -1)});
else B.push_back({Y[x] + (X[x] < X[u] ? 1 : -1)});
}
dfs(u);
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
for(int i = 0;i < n;i++)X[i] = x[i], Y[i] = y[i];
for(int i = 0;i < n;i++)mp[{x[i], y[i]}] = i;
dfs(0);
for(int i = 0;i < n;i++){
if(!vis[i]){
return 0;
}
}
build(U, V, A, B);
return 1;
}
