#include <iostream>
#include <vector>
#include "parks.h"
using namespace std;
const int N = 1<<18;
int pt[10][N];
vector<int> nei[N][2];
int Sz, X, seen[N];
void dfs(int u){
Sz++;
seen[u] = 1;
for (int i : nei[u][0])
if (!seen[i])
dfs(i);
}
void Add(int a, int b, int k = 0){
nei[a][k].push_back(b);
nei[b][k].push_back(a);
}
int construct_roads(vector<int> x, vector<int> y){
int n = x.size();
for (int i=0;i<n;i++){
pt[x[i]][y[i]] = i+1;
X = max(X, x[i]);
}
for (int i=2;i<=6;i+=2){
for (int j=2;j<N;j+=2){
if (pt[i][j] and pt[i+2][j])
Add(pt[i][j], pt[i+2][j]);
if (pt[i][j] and pt[i][j+2]){
Add(pt[i][j], pt[i][j+2]);
Add(pt[i][j], pt[i][j+2], 1);
}
}
}
dfs(1);
if (Sz != n)
return 0;
vector<int> A(n-1), B(n-1), C(n-1), D(n-1);
if (X <= 4){
for (int y=2, l = -2, r = -2, s = 0;y < N; y += 2){
if (pt[2][y] and pt[2][y-2])
A[s] = pt[2][y-2], B[s] = pt[2][y], C[s] = 1, D[s] = y - 1, s++;
if (pt[4][y] and pt[4][y-2])
A[s] = pt[4][y-2], B[s] = pt[4][y], C[s] = 5, D[s] = y - 1, s++;
if (pt[2][y] and pt[4][y] and (l < y - 2 or r < y - 2))
A[s] = pt[2][y], B[s] = pt[4][y], C[s] = 3, D[s] = y - 1, s++;
if (pt[2][y])
l = y;
if (pt[4][y])
r = y;
}
for (int i=0;i<n;i++)
A[i]--, B[i]--;
build(A, B, C, D);
}
return 1;
}
