#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
map<pii, int> id, got;
vector<int> dsu, U, V, A, B;
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
void merge(int aa, int bb, int x, int y){
int a=fp(aa), b=fp(bb);
if (a==b||got[mp(x, y)])return;
dsu[a]=b;
A.pb(x-1);
B.pb(y-1);
U.pb(aa);
V.pb(bb);
got[mp(x, y)]=1;
}
int construct_roads(vector<int> x, vector<int> y){
int n=x.size();
dsu.resize(n+1, -1);
vector<pii> ord;
for (int i=1; i<=n; ++i){
id[mp(x[i-1], y[i-1])]=i;
ord.pb(mp(x[i-1], y[i-1]));
}
sort(ord.begin(), ord.end());
for (auto c:ord){
int temp=(c.fi+c.se)%4;
if (id[mp(c.fi, c.se-2)])merge(id[mp(c.fi, c.se-2)], id[mp(c.fi, c.se)], c.fi+(temp?1:-1), c.se-1);
if (id[mp(c.fi-2, c.se)])merge(id[mp(c.fi-2, c.se)], id[mp(c.fi, c.se)], c.fi-1, c.se+(temp?-1:1));
}
int cc=0;
for (int i=1; i<=n; ++i)if (dsu[i]==-1)++cc;
if (cc>1)return 0;
build(U, V, A, B);
return 1;
}
