#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < (ll)cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;
/*
static void check(bool cond, string message) {
if (!cond) {
printf("%s\n", message.c_str());
fclose(stdout);
exit(0);
}
}
static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
check(!build_called, "build is called more than once");
build_called = true;
m = u.size();
check(int(v.size()) == m, "u.size() != v.size()");
check(int(a.size()) == m, "u.size() != a.size()");
check(int(b.size()) == m, "u.size() != b.size()");
_u = u;
_v = v;
_a = a;
_b = b;
}
*/
int construct_roads(std::vector<int> x, std::vector<int> y){
vector<pair<pll, ll>> coords;
vector<int> a, b, u, v;
map<pll, pll> mp;
ll n = x.size();
map<pll, bool> existe;
ff(i, 0, n){
existe[{y[i], x[i]}] = true;
coords.pb({{y[i], x[i]}, i});
}
sort(all(coords));
ff(i, 0, n){
mp[{y[i], x[i]}] = {0, i};
}
if(n == 1){
build(u, v, a, b);
return 1;
}
ff(i, 0, n){
ll cury = coords[i].fi.fi, curx = coords[i].fi.se, num = coords[i].se;
if(!existe[{cury-2, curx}] && !existe[{cury+2, curx}] && !existe[{cury, curx-2}] && !existe[{cury, curx+2}]){
//cout << "NOEXISTE " << curx << " " << cury << ed;
return 0;
}
//horizontal
if(curx == 2){
if(existe[{cury, curx+2}]){
if(mp[{cury, curx+2}].fi == 0){
u.pb(mp[{cury, curx+2}].se);
v.pb(num);
mp[{cury, curx+2}].fi++;
mp[{cury, curx}].fi++;
a.pb(curx+1);
b.pb(cury-1);
}
}
}
else{
if(existe[{cury, curx-2}]){
if(mp[{cury, curx-2}].fi == 0){
u.pb(mp[{cury, curx-2}].se);
v.pb(num);
mp[{cury, curx-2}].fi++;
mp[{cury, curx}].fi++;
a.pb(curx-1);
b.pb(cury-1);
}
}
}
//vertical
if(existe[{cury+2, curx}]){
u.pb(mp[{cury+2, curx}].se);
v.pb(num);
mp[{cury+2, curx}].fi++;
mp[{cury, curx}].fi++;
if(curx == 2){
a.pb(curx-1);
b.pb(cury+1);
}
else{
a.pb(curx+1);
b.pb(cury+1);
}
}
}
if(a.size() != n-1){
return 0;
}
build(u, v, a, b);
return 1;
}
/*
int main() {
assert(scanf("%d", &n) == 1);
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
build_called = false;
const int possible = construct_roads(x, y);
check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
if (possible == 1) {
check(build_called, "construct_roads() returned 1 without calling build()");
} else {
check(!build_called, "construct_roads() called build() but returned 0");
}
printf("%d\n", possible);
if (possible == 1) {
printf("%d\n", m);
for (int j = 0; j < m; j++) {
printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
}
}
fclose(stdout);
return 0;
}
*/
