#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=200007;
map<int,int>id[N];
map<int,int>id1[N];
vector<int>G[3*N];
bool odw[3*N];
int Pair[3*N];
int r[N];
int Find(int v)
{
if(r[v]==v) return v;
return r[v]=Find(r[v]);
}
void Union(int u,int v)
{
r[u]=v;
}
int dx[4]={2,-2,0,0};
int dy[4]={0,0,2,-2};
void edge(int u,int v)
{
G[u].pb(v);
G[v].pb(u);
}
bool match(int v)
{
if(odw[v]) return 0;
odw[v]=1;
for(auto u:G[v])
{
if(!Pair[u]&&!odw[u])
{
Pair[u]=v;
Pair[v]=u;
return 1;
}
}
for(auto u:G[v])
{
if(!odw[u]&&match(Pair[u]))
{
Pair[u]=v;
Pair[v]=u;
return 1;
}
}
return 0;
}
/*
void build(vector<int>u,vector<int>v,vector<int>a,vector<int>b)
{
for(int i=0;i<sz(u);i++)
{
cout<<u[i]<<" "<<v[i]<<" "<<a[i]<<" "<<b[i]<<endl;
}
}
*/
int construct_roads(vector<int>x,vector<int>y)
{
int n=sz(x);
for(int i=0;i<n;i++)
{
id[x[i]][y[i]]=i+1;
r[i+1]=i+1;
}
int cnt=0,it=n-1;
vector<int>U,V,A,B;
vector<pair<int,int>>Q;
for(int i=0;i<n;i++)
{
for(int j=0;j<4;j++)
{
int nx=x[i]+dx[j],ny=y[i]+dy[j];
if(id[nx][ny]>0&&Find(id[nx][ny])!=Find(i+1))
{
cnt++;
U.pb(id[nx][ny]-1);
V.pb(i);
Union(Find(id[nx][ny]),Find(i+1));
int X=min(x[i],x[id[nx][ny]-1]),Y=min(y[i],y[id[nx][ny]-1]);
if(x[i]==x[id[nx][ny]-1])
{
if(id1[X+1][Y+1]==0)
{
id1[X+1][Y+1]=++it;
Q.pb({X+1,Y+1});
}
if(id1[X-1][Y+1]==0)
{
id1[X-1][Y+1]=++it;
Q.pb({X-1,Y+1});
}
edge(id1[X+1][Y+1],cnt);
edge(id1[X-1][Y+1],cnt);
}
else
{
if(id1[X+1][Y+1]==0)
{
id1[X+1][Y+1]=++it;
Q.pb({X+1,Y+1});
}
if(id1[X+1][Y-1]==0)
{
id1[X+1][Y-1]=++it;
Q.pb({X+1,Y-1});
}
edge(id1[X+1][Y+1],cnt);
edge(id1[X+1][Y-1],cnt);
}
}
}
}
if(cnt!=n-1) return 0;
while(true)
{
memset(odw,0,sizeof odw);
bool xd=0;
for(int i=1;i<=it;i++) if(!Pair[i]) xd|=match(i);
if(!xd) break;
}
for(int i=1;i<=n-1;i++)
{
A.pb(Q[Pair[i]-n].st);
B.pb(Q[Pair[i]-n].nd);
// if(Pair[i]==0) return 2137;
}
build(U,V,A,B);
return 1;
}
/*
int main()
{
construct_roads({2, 2, 4, 4}, {2, 4, 2, 4});
return 0;
}
*/
