#include"parks.h"
#include<map>
#include<algorithm>
using namespace std;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
int fa[200001],n;
int get(int x){
  return fa[x]==x?x:fa[x]=get(fa[x]);
}
bool cmp(pair<int,int> x,pair<int,int> y){
  if(x.second!=y.second)return x.second>y.second;
  return x.first<y.first;
}
int construct_roads(std::vector<int> x, std::vector<int> y){
  n=x.size();
  map<pair<int,int>,int>mp,us;
  vector<pair<int,int> >v;
  vector<int>va,vb,vu,vv;
  for(int i=0;i<n;++i){
    fa[i]=i;
    mp[{x[i],y[i]}]=i;v.push_back({x[i],y[i]});
  }
  sort(v.begin(),v.end(),cmp);
  for(auto [x,y]:v){
    if(mp.count({x+2,y})){
      int u=mp[{x,y}],v=mp[{x+2,y}];
      if(get(u)!=get(v)){
        int xx=x+1,yy=y+1;
        if((xx/2+yy/2)&1)yy-=2;
        if(us.count({xx,yy}))continue;
        us[{xx,yy}]=1;
        va.push_back(u);vb.push_back(v);vu.push_back(xx);vv.push_back(yy);
        fa[get(u)]=get(v);
      }
    }
    if(mp.count({x,y-2})){
      int u=mp[{x,y}],v=mp[{x,y-2}];
      if(get(u)!=get(v)){
        int xx=x+1,yy=y-1;
        if(!((xx/2+yy/2)&1))xx-=2;
        if(us.count({xx,yy}))continue;
        us[{xx,yy}]=1;
        va.push_back(u);vb.push_back(v);vu.push_back(xx);vv.push_back(yy);
        fa[get(u)]=get(v);
      }
    }
  }
  bool flag=1;
  for(int i=1;i<n;++i)flag&=(get(0)==get(i));
  if(!flag)return 0;
  build(va,vb,vu,vv);
  return 1;
}