#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]);
}
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;
}
vector<int>x,y,U,V,A,B;
vector<pair<int,int>>Q;
int cnt,it;
void Union(int u,int v)
{
r[Find(u)]=Find(v);
cnt++;
U.pb(u-1);
V.pb(v-1);
int X=min(x[u-1],x[v-1]),Y=min(y[u-1],y[v-1]);
if(x[u-1]==x[v-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);
}
}
/*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>xx,vector<int>yy)
{
x=xx;
y=yy;
int n=sz(x);
for(int i=0;i<n;i++)
{
id[x[i]][y[i]]=i+1;
r[i+1]=i+1;
}
it=n-1;
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))
{
int u=id[nx][ny],v=i+1,c=0;
int X=min(x[u-1],x[v-1]),Y=min(y[u-1],y[v-1]);
if(x[u-1]==x[v-1])
{
if(id[X-2][Y]>0&&id[X-2][Y+2]>0) c++;
if(id[X+2][Y]>0&&id[X+2][Y+2]>0) c++;
}
else
{
if(id[X][Y-2]>0&&id[X+2][Y-2]>0) c++;
if(id[X][Y+2]>0&&id[X+2][Y+2]>0) c++;
}
if(c==1) Union(u,v);
}
}
}
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))
{
Union(id[nx][ny],i+1);
}
}
}
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++)
{
if(Pair[i]==0) return 0;
A.pb(Q[Pair[i]-n].st);
B.pb(Q[Pair[i]-n].nd);
}
build(U,V,A,B);
return 1;
}
/*
int main()
{
construct_roads({2, 2, 4, 4}, {2, 4, 2, 4});
return 0;
}*/
