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

int construct_roads(std::vector<int> x, std::vector<int> y)
{
    map<pair<int, int>, int> found, vis;
    for(int i = 0; i < x.size(); i++)
    {
        found[{x[i], y[i]}] = i;
    }
    queue<pair<int, int>> q;
    q.push({x[0], y[0]});
    vector<int> u, v, a, b;
    while(!q.empty())
    {
        auto [x1, y1] = q.front();
        q.pop();

        vis[{x1, y1}] = true;
        if(found[{x1, y1 + 2}] and !vis[{x1, y1 + 2}])
        {
            if(!vis[{x1 - 1, y1 + 1}])
            {
                u.push_back(found[{x1, y1}]);
                v.push_back(found[{x1, y1 + 2}]);
                a.push_back(x1 - 1);
                b.push_back(y1 + 1);
                q.push({x1, y1 + 2});
            }
            else if(!vis[{x1 + 1, y1 + 1}])
            {
                u.push_back(found[{x1, y1}]);
                v.push_back(found[{x1, y1 + 2}]);
                a.push_back(x1 + 1);
                b.push_back(y1 + 1);
                q.push({x1, y1 + 2});
            }
        }
        else if(found[{x1, y1 - 2}] and !vis[{x1, y1 - 2}])
        {
            if(!vis[{x1 - 1, y1 - 1}])
            {
                u.push_back(found[{x1, y1}]);
                v.push_back(found[{x1, y1 - 2}]);
                a.push_back(x1 - 1);
                b.push_back(y1 - 1);
                q.push({x1, y1 - 2});
            }
            else if(!vis[{x1 + 1, y1 - 1}])
            {
                u.push_back(found[{x1, y1}]);
                v.push_back(found[{x1, y1 - 2}]);
                a.push_back(x1 + 1);
                b.push_back(y1 - 1);
                q.push({x1, y1 - 2});
            }
        }
    }

    if(u.size() != x.size() - 1)
    {
        return 0;
    }

    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);