#include "parks.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


vector<int> uf;
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


/*
  o-^-o-v-o
  |   |   |
  >   <   >
  |   |   |
  o-v-o-^-o
  |   |   |
  <   >   <
  |   |   |
  o-^-o-v-o
  
  want:
  - path from (x, y) to (x-2, y)
  - path from (x, y) to (x, y-2)
*/

map<pair<int, int>, int> ids;
int id(int x, int y) {
  auto it = ids.find(make_pair(x, y));
  if (it != ids.end()) {
    return it->second;
  } else {
    return -1;
  }
}

int construct_roads(vector<int> X, vector<int> Y) {
  const int N = X.size();
  for (int u = 0; u < N; ++u) {
    ids[make_pair(X[u], Y[u])] = u;
  }
  
  uf.assign(N, -1);
  vector<int> U, V, A, B;
  for (const auto &kv : ids) {
    const int u = kv.second;
    const int x = X[u], y = Y[u];
    const int s = (x/2 + y/2) & 1;
    const int v = id(x-2, y);
    const int w = id(x, y-2);
    const int t = id(x-2, y-2);
    /*
      tv
      wu
    */
    if (~v && !(s == 0 && ~w && ~t)) {
      connect(u, v);
      U.push_back(u);
      V.push_back(v);
      A.push_back(x-1);
      B.push_back((s == 0) ? (y-1) : (y+1));
    }
    if (~w && !(s == 1 && ~v && ~t)) {
      connect(u, w);
      U.push_back(u);
      V.push_back(w);
      A.push_back((s == 1) ? (x-1) : (x+1));
      B.push_back(y-1);
    }
  }
  if (-uf[root(0)] == N) {
    build(U, V, A, B);
    return 1;
  } else {
    return 0;
  }
}