#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
map< pair<int,int>, int > seen;
int ask(int x,int y)
{
if(seen.count({x,y}))return seen[{x,y}];
return -1;
}
int parent[nmax];
int root(int node)
{
if(node==parent[node])return node;
parent[node]=root(parent[node]);
return parent[node];
}
set< pair<int,int> > benches;
struct point
{
int x,y,id;
};
bool cmp(point a,point b)
{
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
point inp[nmax];
map<int, set< pair<int,int> > > from;
map< pair<int,int>, set<int> > to;
priority_queue< pair<int, pair<int,int> > > pq;
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n=x.size();
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
for(int i=0;i<x.size();i++)
seen[{x[i],y[i]}]=i;
for(int i=0;i<n;i++)
{
parent[i]=i;
inp[i].x=x[i];
inp[i].y=y[i];
inp[i].id=i;
}
sort(inp,inp+n,cmp);
vector<int> u={},v={},a={},b={};
for(int j=0;j<n;j++)
{
int pos=ask(inp[j].x+2,inp[j].y);
if(pos!=-1&&root(pos)!=root(inp[j].id))
{
parent[root(pos)]=root(inp[j].id);
from[u.size()].insert({inp[j].x+1,inp[j].y+1});
from[u.size()].insert({inp[j].x+1,inp[j].y-1});
to[{inp[j].x+1,inp[j].y+1}].insert(u.size());
to[{inp[j].x+1,inp[j].y-1}].insert(u.size());
u.push_back(inp[j].id);
v.push_back(pos);
a.push_back(0);
b.push_back(0);
}
pos=ask(inp[j].x,inp[j].y+2);
if(pos!=-1&&root(pos)!=root(inp[j].id))
{
parent[root(pos)]=root(inp[j].id);
from[u.size()].insert({inp[j].x+1,inp[j].y+1});
from[u.size()].insert({inp[j].x-1,inp[j].y+1});
to[{inp[j].x+1,inp[j].y+1}].insert(u.size());
to[{inp[j].x-1,inp[j].y+1}].insert(u.size());
u.push_back(inp[j].id);
v.push_back(pos);
a.push_back(0);
b.push_back(0);
}
}
for(int i=0;i<n;i++)
if(root(i)!=root(0))return 0;
for(auto w:to)
pq.push({-w.second.size(),w.first});
while(pq.size())
{
//cout<<pq.size()<<endl;
pair<int, pair<int,int> > tp=pq.top();
pq.pop();
pair<int,int> where=tp.second;
for(auto w:to[where])
{
//cout<<"w= "<<w<<endl;
if(a[w]==0)
{
//cout<<"match "<<tp.first<<" "<<tp.second.first<<" "<<tp.second.second<<" with "<<w<<endl;
a[w]=where.first;
b[w]=where.second;
while(from[w].size())
{
set< pair<int,int> >::iterator it=from[w].begin();
pair<int,int> p=(*it);
//cout<<"p= "<<p.first<<" "<<p.second<<endl;
to[p].erase(w);
from[w].erase(p);
pq.push({-to[p].size(),p});
}
while(to[where].size())
{
set< int >::iterator it=to[where].begin();
int p=(*it);
//cout<<"p= "<<p<<endl;
to[where].erase(p);
from[p].erase(where);
}
break;
}
}
to[where]={};
}
build(u,v,a,b);
return 1;
}
/*
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 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;
}
*/
