#include "parks.h"
#define here cerr<<"==============================\n"
#include <bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
using namespace std;
#define maxn 200005
ll n;
pll a[maxn];
map<pll,ll> mp;
map<pll,ll> id;
vector<ll> dx = {0,0,-2,2};
vector<ll> dy = {-2,2,0,0};
ll sz[maxn];
ll dsu[maxn];
ll col[maxn];
ll dsu2[maxn];
ll root2(ll x){
while(x!=dsu2[x]){
dsu2[x] = dsu2[dsu2[x]];
x = dsu2[x];
}
return x;
}
bool con(ll x,ll y){return root2(x)==root2(y);}
ll tsz = 1;
bool ok = 1;
ll root(ll x){
while(x!=dsu[x]){
x = dsu[x];
}
return x;
}
void upd2(ll i,ll j){
i = root2(i);
j = root2(j);
dsu2[j] = dsu2[i];
}
ll getcol(ll x){
ll ans = col[x];
while(x!=dsu[x]){
x = dsu[x];
ans^=col[x];
}
return ans;
}
void upd(ll i,ll j,ll e){
e^=getcol(i)^getcol(j);
i = root(i);
j = root(j);
if(i==j){
if(e) ok = 0;
return;
}
if(sz[j]>sz[i]) swap(i,j);
sz[i]+=sz[j];
dsu[j] = i;
col[j]^=e;
}
int construct_roads(vector<int> X, vector<int> Y) {
n = X.size();
for(ll i = 1;i<=n;i++) a[i] = {X[i-1],Y[i-1]};
for(ll i = 1;i<=n;i++) mp[a[i]] = i;
iota(dsu+1,dsu+1+n,1);
iota(dsu2+1,dsu2+1+n,1);
fill(sz+1,sz+1+n,1);
vector<ll> c,d;
for(ll i = 1;i<=n;i++){
ll x = a[i].fi,y = a[i].sc;
vector<ll> v;
for(ll e = 0;e<=3;e++){
ll nx = x + dx[e];
ll ny = y + dy[e];
ll j = mp[{nx,ny}];
v.pb(j);
if(j&&!id[{i,j}]&&!con(i,j)){
c.pb(i);
d.pb(j);
upd2(i,j);
id[{i,j}] = id[{j,i}] = ++tsz;
}
}
if(v[1]&&v[3]) upd(id[{i,v[1]}],id[{i,v[3]}],1);
if(v[0]&&v[2]) upd(id[{i,v[0]}],id[{i,v[2]}],1);
if(v[1]&&v[2]) upd(id[{i,v[1]}],id[{i,v[2]}],0);
if(v[0]&&v[3]) upd(id[{i,v[0]}],id[{i,v[3]}],0);
}
if(!ok) return 0;
if(c.size()<n-1) return 0;
vector<pll> ans;
for(ll i = 0;i<n-1;i++){
ll x = c[i];
ll y = d[i];
ll j = id[{x,y}];
ll f = getcol(j);
if(a[x].fi==a[y].fi){
if(f) ans.pb({a[x].fi+1,(a[x].sc+a[y].sc)/2});
else ans.pb({a[x].fi-1,(a[x].sc+a[y].sc)/2});
}else{
if(f) ans.pb({(a[x].fi+a[y].fi)/2,a[y].sc+1});
else ans.pb({(a[x].fi+a[y].fi)/2,a[y].sc-1});
}
}
vector<ll> ansx,ansy;
for(pll p : ans){
ansx.pb(p.fi);
ansy.pb(p.sc);
}
for(ll i = 0;i<n-1;i++){
c[i]--;
d[i]--;
}
build(c,d,ansx,ansy);
return 1;
}
/**
5
4 4
4 6
6 4
4 2
2 4
**/
