#include "parks.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct DSU {
    vector<int> fa;

    void init(int n) {
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
    }

    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) {
            return false;
        }
        fa[y] = x;
        return true;
    }
};

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n = size(x);

    if (n == 1) {
        build({}, {}, {}, {});
        return 1;
    }

    map<pair<int, int>, int> mp;
    map<pair<int, int>, vector<int>> adj;

    for (int i = 0; i < n; ++i) {
        mp[{x[i], y[i]}] = i;
    }

    DSU dsu;
    dsu.init(n);
    vector<pair<int, int>> e, f;

    for (int i = 0; i < n; ++i) {
        for (int t : {0, 1}) {
            for (int d : {-2, 2}) {
                int nx = x[i] + t * d;
                int ny = y[i] + (1 - t) * d;
                if (mp.count({nx, ny})) {
                    int j = mp[{nx, ny}];
                    if (dsu.unite(i, j)) {
                        e.emplace_back(i, j);
                    }
                }
            }
        }
    }

    if (size(e) != n - 1) {
        return false;
    }

    for (int i = 0; i < size(e); ++i) {
        int nx = x[e[i].first] + x[e[i].second] >> 1;
        int ny = y[e[i].first] + y[e[i].second] >> 1;
        if (nx % 2 == 0) {
            adj[{nx - 1, ny}].push_back(~i);
            adj[{nx + 1, ny}].push_back(i);
        } else {
            adj[{nx, ny - 1}].push_back(~i);
            adj[{nx, ny + 1}].push_back(i);
        }
    }

    vector<int> type(n - 1);
    for (int k = 0; k < n - 1; ++k) {
        if (type[k] == 0) {
            type[k] = 1;
            auto dfs = [&](auto dfs, int i) -> void { 
                int nx = x[e[i].first] + x[e[i].second] >> 1;
                int ny = y[e[i].first] + y[e[i].second] >> 1;
                if (nx % 2 == 0) {
                    nx += type[i];
                } else {
                    ny += type[i];
                }
                for (int to: adj[{nx, ny}]) {
                    int t = to >= 0 ? 1 : -1;
                    if (t == -1) {
                        to = ~to;
                    }
                    if (to == i) {
                        continue;
                    }
                    if (type[to] == 0) {
                        type[to] = -t;
                        dfs(dfs, to);
                    } else {
                        assert(type[to] != t);
                    }
                }
            };
            dfs(dfs, k);
        }
    }

    vector<int> u(n - 1), v(n - 1), a(n - 1), b(n - 1);

    for (int i = 0; i < size(e); ++i) {
        u[i] = e[i].first;
        v[i] = e[i].second;
        a[i] = x[u[i]] + x[v[i]] >> 1;
        b[i] = y[u[i]] + y[v[i]] >> 1;
        if (a[i] % 2 == 0) {
            a[i] += type[i];
        } else {
            b[i] += type[i];
        }
    }

    build(u, v, a, b);

    return 1;
}