#include"parks.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
//#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define x first
#define y second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000005
#define inf 0x3f3f3f3f

int fa[maxn];
map<int,int>mp[maxn],hav[maxn];

int gf(int x){
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}

vi U,V,A,B;
void add(int u,int v,int a,int b){
	if(gf(u)==gf(v)) return;
	if(hav[a][b]) return;
//	cout<<"u,v,a,b "<<u<<" "<<v<<" "<<a<<" "<<b<<"\n";
	fa[gf(u)]=gf(v);
	U.pb(u),V.pb(v),A.pb(a),B.pb(b);
	hav[a][b]=1;
}

int construct_roads(vi X,vi Y)
{
	int n=X.size();
	vector<pii>o;
	For(i,0,n-1)o.pb(mkp(X[i],Y[i])),mp[X[i]][Y[i]]=i,fa[i]=i;
	sort(ALL(o));
	bool fir=1;
	for(int l=0,r=0;l<n;l=r+1){
		r=l;
		while(r+1<n && o[r+1].x==o[l].x) ++r;
		
		vector<pii>p;
		For(i,l,r) p.pb(o[i]);
	//	assert(p.size()==n);
		
		if(fir){
			fir=0;
			for(auto [x,y]:p)
				if(mp[x].count(y+2)) add(mp[x][y],mp[x][y+2],x-1,y+1);
			continue;
		}
		
		for(auto [x,y]:p)
			if(mp[x].count(y+2) && (x+y)%4==0)
				add(mp[x][y],mp[x][y+2],x+1,y+1);
		
		for(auto [x,y]:p)
			if(mp[x-2].count(y) && (x+y)%4==2)
				add(mp[x][y],mp[x-2][y],x-1,y-1);
				
		for(auto [x,y]:p)
			if(mp[x].count(y+2) && (x+y)%4==2)
				add(mp[x][y],mp[x][y+2],x-1,y+1);
		
		for(auto [x,y]:p)
			if(mp[x-2].count(y) && (x+y)%4==0)
				add(mp[x][y],mp[x-2][y],x-1,y+1);
	}
	For(i,1,n-1) if(gf(i)!=gf(0)) return 0;
	build(U,V,A,B);
	return 1;
}