#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, v, a, b;
    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());
    map<pair<int, int>, bool> vis;
    int cnt = 0;
    auto dfs2 = [&](auto self, int i) -> void
    {
        auto [x, y, id] = cord[i];
        vis[{x, y}] = true;
        if (x == 2)
        {
            {
                int idx = lower_bound(cord.begin(), cord.end(), make_tuple(x, y + 2, -1)) - cord.begin();
                if (idx - 1 != n)
                {
                    auto [xx, yy, idid] = cord[idx];
                    if (xx == x and yy == y + 2)
                    {
                        if (!vis[{xx, yy}])
                        {
                            u.push_back(id);
                            v.push_back(idid);
                            a.push_back(1);
                            b.push_back(y + 1);
                            self(self, idid);
                        }
                    }
                }
            }
            {
                int idx = lower_bound(cord.begin(), cord.end(), make_tuple(x + 2, y, -1)) - cord.begin();
                if (idx - 1 != n)
                {
                    auto [xx, yy, idid] = cord[idx];
                    if (xx == x + 2 and yy == y)
                    {
                        if (!vis[{xx, yy}])
                        {
                            u.push_back(id);
                            v.push_back(idid);
                            a.push_back(3);
                            b.push_back(y - 1);
                            self(self, idid);
                        }
                    }
                }
            }
        }
        else
        {
            {
                int idx = lower_bound(cord.begin(), cord.end(), make_tuple(x, y + 2, -1)) - cord.begin();
                if (idx - 1 != n)
                {
                    auto [xx, yy, idid] = cord[idx];
                    if (xx == x and yy == y + 2)
                    {
                        if (!vis[{xx, yy}])
                        {
                            u.push_back(id);
                            v.push_back(idid);
                            a.push_back(5);
                            b.push_back(y + 1);
                            self(self, idid);
                        }
                    }
                }
            }
            
            {
                int idx = lower_bound(cord.begin(), cord.end(), make_tuple(x - 2, y, -1)) - cord.begin();
                if (idx - 1 != n)
                {
                    auto [xx, yy, idid] = cord[idx];
                    if (xx == x - 2 and yy == y)
                    {
                        if (!vis[{xx, yy}])
                        {
                            u.push_back(id);
                            v.push_back(idid);
                            a.push_back(3);
                            b.push_back(y - 1);
                            self(self, idid);
                        }
                    }
                }
            }
        }
    };
    dfs2(dfs2, 0);
    build(u, v, a, b);
    // for (int i = 0; i < u.size(); i++)
    // {
    //     cout << u[i] << ' ' << v[i] << ' ' << a[i] << ' ' << b[i] << '\n';
    // }
    return 1;
}
// void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);