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

    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);
    queue<int> q;
    type[0] = 1;
    q.push(0);

    while (!q.empty()) {
        int i = q.front();
        q.pop();
        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;
            to *= t;
            if (to == i) {
                continue;
            }
            if (type[to] == 0) {
                type[to] = -t;
                q.push(to);
            } else {
                assert(type[to] != t);
            }
        }
    }

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