#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;
map<pi,pi> p;
map<pi,int> s,num,used;
pi parent(pi x){
if(p[x]==x)return x;
return p[x]=parent(p[x]);
}
void join(pi x,pi y){
x=parent(x);
y=parent(y);
if(x==y)return;
if(s[x]<s[y])swap(x,y);
s[x]+=s[y];
p[y]=x;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n=x.size();
int mx=0;
REP(i,0,n)mx=max(mx,x[i]);
if(mx==2){
pii a;
REP(i,0,n)a.PB({y[i],i});
sort(a.begin(),a.end());
vii ans(4);
REP(i,0,n-1){
if(a[i].F+2!=a[i+1].F)return 0;
ans[0].PB(a[i].S);
ans[1].PB(a[i+1].S);
ans[2].PB(3);
ans[3].PB(a[i].F+1);
}
build(ans[0],ans[1],ans[2],ans[3]);
return 1;
}
if(mx==4){
REP(i,0,n)s[{x[i],y[i]}]=1;
REP(i,0,n)p[{x[i],y[i]}]={x[i],y[i]};
REP(i,0,n)num[{x[i],y[i]}]=i;
vii ans(4);
REP(i,2,5){
REP(j,2,200001){
if(j<200000&&s[{i,j}]>0&&s[{i,j+2}]>0){
join({i,j},{i,j+2});
ans[0].PB(num[{i,j}]);
ans[1].PB(num[{i,j+2}]);
if(i==2)ans[2].PB(i-1);
else ans[2].PB(i+1);
ans[3].PB(j+1);
}
if(i==2&&s[{i,j}]>0&&s[{i+2,j}]>0){
join({i,j},{i+2,j});
ans[0].PB(num[{i,j}]);
ans[1].PB(num[{i+2,j}]);
ans[2].PB(i+1);
ans[3].PB(j-1);
}
j++;
}
i++;
}
pi t=parent({x[0],y[0]});
bool flag=1;
REP(i,0,n)if(parent({x[i],y[i]})!=t)flag=0;
if(flag){
build(ans[0],ans[1],ans[2],ans[3]);
return 1;
}
return 0;
}
if(mx==6){
REP(i,0,n)s[{x[i],y[i]}]=1;
REP(i,0,n)p[{x[i],y[i]}]={x[i],y[i]};
REP(i,0,n)num[{x[i],y[i]}]=i;
vii ans(4);
REP(i,2,7){
REP(j,2,200000){
if(s[{i,j}]>0&&s[{i,j+2}]>0){
join({i,j},{i,j+2});
ans[0].PB(num[{i,j}]);
ans[1].PB(num[{i,j+2}]);
if(i==2)ans[2].PB(i-1);
else if(i==6)ans[2].PB(i+1);
else if(i==4){
if((j/2)%2==0)ans[2].PB(i+1);
else ans[2].PB(i-1);
}
ans[3].PB(j+1);
used[{ans[2].back(),ans[3].back()}]=1;
}
j++;
}
i++;
}
REP(i,2,5){
REP(j,2,200001){
if(s[{i,j}]>0&&s[{i+2,j}]>0&&parent({i,j})!=parent({i+2,j})){
if(used[{i+1,j-1}]==1&&used[{i+1,j+1}])return 0;
join({i,j},{i+2,j});
ans[0].PB(num[{i,j}]);
ans[1].PB(num[{i+2,j}]);
if(used[{i+1,j-1}]==1){
ans[2].PB(i+1);
ans[3].PB(j+1);
}
else{
ans[2].PB(i+1);
ans[3].PB(j-1);
}
}
j++;
}
i++;
}
pi t=parent({x[0],y[0]});
bool flag=1;
REP(i,0,n)if(parent({x[i],y[i]})!=t)flag=0;
if(flag){
build(ans[0],ans[1],ans[2],ans[3]);
return 1;
}
return 0;
}
REP(i,0,n)s[{x[i],y[i]}]=1;
REP(i,0,n)p[{x[i],y[i]}]={x[i],y[i]};
REP(i,0,n)num[{x[i],y[i]}]=i;
vii ans(4);
pii loc={{0,2},{0,-2},{2,0},{-2,0}};
REP(i,0,n){
REP(j,0,4)if(s[{x[i]+loc[j].F,y[i]+loc[j].S}]>0&&parent({x[i],y[i]})!=parent({x[i]+loc[j].F,y[i]+loc[j].S})){
join({x[i],y[i]},{x[i]+loc[j].F,y[i]+loc[j].S});
ans[0].PB(num[{x[i],y[i]}]);
ans[1].PB(num[{x[i]+loc[j].F,y[i]+loc[j].S}]);
if(loc[j].F==0){
if((x[i]/2)%2==0){
if((min(y[i],y[i]+loc[j].S)/2)%2==1)ans[2].PB(x[i]+1);
else ans[2].PB(x[i]-1);
}
else{
if((min(y[i],y[i]+loc[j].S)/2)%2==1)ans[2].PB(x[i]-1);
else ans[2].PB(x[i]+1);
}
ans[3].PB(min(y[i],y[i]+loc[j].S)+1);
}
else{
ans[2].PB(min(x[i],x[i]+loc[j].F)+1);
if((y[i]/2)%2==0){
if((min(x[i],x[i]+loc[j].F)/2)%2==1)ans[3].PB(y[i]-1);
else ans[3].PB(y[i]+1);
}
else{
if((min(x[i],x[i]+loc[j].F)/2)%2==1)ans[3].PB(y[i]+1);
else ans[3].PB(y[i]-1);
}
}
}
}
pi t=parent({x[0],y[0]});
bool flag=1;
REP(i,0,n)if(parent({x[i],y[i]})!=t)flag=0;
if(flag){
build(ans[0],ans[1],ans[2],ans[3]);
return 1;
}
return 0;
}
