#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

int construct_roads(std::vector<int> X, std::vector<int> Y)
{
    vector<int> dx{0, 0, 2, -2}, dy{2, -2, 0, 0};
    set<pair<int, int>> locations;
    for(int i = 0; i < X.size(); i++)
    {
        locations.insert({X[i], Y[i]});
    }
    auto dfs = [&](auto self, int x, int y) -> void
    {
        locations.erase({x, y});
        for(int i = 0; i < 4; i++)
        {
            if(locations.find({x + dx[i], y + dy[i]}) != locations.end())
            {
                self(self, x + dx[i], y + dy[i]);
            }   
        }
    };
    dfs(dfs, X.front(), Y.front());

    if(!locations.empty())
    {
        return 0;
    }

    int n = X.size() - 1;
    vector<int> u(n), v(n), a(n), b(n);
    vector<tuple<int, int, int>> cord;
    for(int i = 0; i < n + 1; i++)
    {
        cord.push_back({X[i], Y[i], i});
    }
    sort(cord.begin(), cord.end());
    for(int i = 0; i < n; i++)
    {
        auto [x1, y1, f1] = cord[i];
        auto [x2, y2, f2] = cord[i + 1];
        u[i] = f1;
        v[i] = f2;
        a[i] = y2 - 1;
        b[i] = 1;
    }
    build(u, v, a, b);
    return 1;
}
// void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);