#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
int fau[N];
pair<int, int> tab[N], ntab[N];
map<pair<int, int>, int> pts;
vector<pair<int, int>> ed;
vector<pair<int, int>> ben;
vector<int> ans1, ans2, ans3, ans4;
int Find(int v)
{
return (fau[v] = (fau[v] == v ? v : Find(fau[v])));
}
void Union(int a, int b)
{
fau[Find(b)] = Find(a);
}
int Check(int x, int y)
{
if(pts.find(make_pair(x, y)) != pts.end())
return pts[make_pair(x, y)];
return -1;
}
bool Clr(pair<int, int> a)
{
return (((a.st + a.nd) / 2) % 2 == 0);
}
void MakE(int n)
{
for(int i = 0; i < n; ++i)
{
int v = Check(ntab[i].st, ntab[i].nd);
int u = Check(ntab[i].st, ntab[i].nd + 2), l = Check(ntab[i].st - 2, ntab[i].nd);
if(u != -1 && l != -1 && Check(ntab[i].st - 2, ntab[i].nd + 2) != -1)
{
//cerr << "XDKURAWdasljlsdfkjakd\n";
if(Clr(ntab[i])) ed.pb(make_pair(v, u));
else ed.pb(make_pair(v, l));
continue;
}
if(u != -1)
ed.pb(make_pair(v, u));
if(l != -1)
ed.pb(make_pair(v, l));
}
}
void SpTree()
{
vector<pair<int, int>> nxt;
for(int i = 0; i < (int)ed.size(); ++i)
{
//cerr << ed[i].st << " " << ed[i].nd << "\n";
if(Find(ed[i].st) != Find(ed[i].nd))
{
Union(ed[i].st, ed[i].nd);
nxt.pb(ed[i]);
}
}
ed = nxt;
}
void DoB()
{
for(int i = 0; i < (int)ed.size(); ++i)
{
int v = ed[i].st, u = ed[i].nd;
//cerr << "ed: " << Clr(tab[v]) << "\n";
if(tab[u].st == tab[v].st)
{
if(Clr(tab[v]))
ben.pb(make_pair(tab[v].st + 1, tab[v].nd + 1));
else
ben.pb(make_pair(tab[v].st - 1, tab[v].nd + 1));
}else
{
if(Clr(tab[v]))
ben.pb(make_pair(tab[v].st - 1, tab[v].nd + 1));
else
ben.pb(make_pair(tab[v].st - 1, tab[v].nd - 1));
}
}
}
void ConstructAnswer()
{
for(int i = 0; i < (int)ed.size(); ++i)
{
ans1.pb(ed[i].st); ans2.pb(ed[i].nd);
ans3.pb(ben[i].st); ans4.pb(ben[i].nd);
}
}
int construct_roads(vector<int> _x, vector<int> _y)
{
int n = _x.size();
//cerr << "Input " << "\n";
for(int i = 0; i < n; ++i)
{
tab[i] = make_pair(_x[i], _y[i]);
//cerr << i << " " << tab[i].st << " " << tab[i].nd << "\n";
pts[tab[i]] = i;
fau[i] = i;
ntab[i] = tab[i];
}
sort(ntab, ntab + n);
MakE(n);
//cerr << "xd\n";
SpTree();
//cerr << "xd\n";
if((int)ed.size() < n - 1) return 0;
DoB();
ConstructAnswer();
build(ans1, ans2, ans3, ans4);
return 1;
}
