#include "parks.h"

#include <bits/stdc++.h>
using namespace std;

const int MX=2e5+5;

// bawah kiri atas kanan
const int dx[4]={-1,-1,-1,1},dy[4]={-1,-1,1,-1},ddx[4]={1,-1,1,1},ddy[4]={-1,1,1,1};

struct dsu {
        int par[MX];

        int find(int v) {
                return par[v]==v?v:par[v]=find(par[v]);
        }

        bool merge(int u, int v) {
                u=find(u),v=find(v);
                if(u==v) return false;
                par[u]=v;
                return true;
        }

        void prep() {
                for(int i=0;i<MX;i++) {
                        par[i]=i;
                }
        }
} ds;

vector<pair<int,int>> pos[MX];
set<int> st[MX];
vector<pair<int,int>> adj[MX];
vector<int> a,b,u,v;

map<array<int,4>,int> getId;
set<array<int,4>> edge;

map<pair<int,int>, int> cnt;
set<array<int,3>> S;

void add(int id, int x, int y) {
        assert(st[y].count(x));
        st[y].erase(x);
        a[id]=x;
        b[id]=y;
}

void upd(int x, int y, int coef) {
        if(st[y].count(x)) {
                S.erase({cnt[{x,y}],x,y});
                cnt[{x,y}]+=coef;
                S.insert({cnt[{x,y}],x,y});
        }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {

        int N=x.size();
        int id=0;

        for(int i=0;i<N;i++) {
                pos[y[i]].push_back({x[i],i});
        }

        ds.prep();
        for(int i=0;i+2<MX;i+=2) {
                sort(pos[i].begin(),pos[i].end());

                for(int j=0;j+1<pos[i].size();j++) {
                        if(pos[i][j].first+2==pos[i][j+1].first) {
                                if(ds.merge(pos[i][j].second,pos[i][j+1].second)) {
                                        if(i>0) {
                                                st[i-1].insert(pos[i][j].first+1);
                                        }
                                        if(i+1<MX) {
                                                st[i+1].insert(pos[i][j].first+1);
                                        }
                                        adj[pos[i][j].second].push_back({pos[i][j+1].second,id});
                                        adj[pos[i][j+1].second].push_back({pos[i][j].second,id});
                                        id++;
                                }
                        }
                }

                if(!i) continue;
                if((i/2)&1) {
                        for(int j=pos[i].size()-1;j>=0;j--) {
                                auto it=lower_bound(pos[i-2].begin(),pos[i-2].end(),make_pair(pos[i][j].first,0));
                                if(it!=pos[i-2].end() && it->first==pos[i][j].first) {
                                        if(ds.merge(pos[i][j].second,it->second)) {
                                                st[i-1].insert(it->first-1);
                                                st[i-1].insert(it->first+1);
                                                adj[pos[i][j].second].push_back({it->second,id});
                                                adj[it->second].push_back({pos[i][j].second,id});
                                                id++;
                                        }
                                }
                        }
                } else {
                        for(int j=0;j<pos[i].size();j++) {
                                auto it=lower_bound(pos[i-2].begin(),pos[i-2].end(),make_pair(pos[i][j].first,0));
                                if(it!=pos[i-2].end() && it->first==pos[i][j].first) {
                                        if(ds.merge(pos[i][j].second,it->second)) {
                                                st[i-1].insert(it->first-1);
                                                st[i-1].insert(it->first+1);
                                                adj[pos[i][j].second].push_back({it->second,id});
                                                adj[it->second].push_back({pos[i][j].second,id});
                                                id++;
                                        }
                                }
                        }
                }
        }

        for(int i=0;i<N;i++) {
                if(ds.find(i)!=ds.find(0)) return 0;
        }

        a.assign(id,-1);
        b.assign(id,-1);
        u.assign(id,-1);
        v.assign(id,-1);

        for(int i=0;i<N;i++) {
                for(auto [j,id]:adj[i]) {
                        if(i>j) continue;
                        u[id]=i;
                        v[id]=j;
                        getId[{min(x[i],x[j]),max(x[i],x[j]),min(y[i],y[j]),max(y[i],y[j])}]=id;
                        edge.insert({min(x[i],x[j]),max(x[i],x[j]),min(y[i],y[j]),max(y[i],y[j])});
                }
        }

        for(int i=0;i<N;i++) {
                if(adj[i].size()==4) {
                        for(auto [j,id]:adj[i]) {
                                if(x[j]==x[i]-2) {
                                        add(id,x[i]-1,y[i]-1);
                                }
                                if(y[j]==y[i]+2) {
                                        add(id,x[i]-1,y[i]+1);
                                }
                                if(x[j]==x[i]+2) {
                                        add(id,x[i]+1,y[i]+1);
                                }
                                if(y[j]==y[i]-2) {
                                        add(id,x[i]+1,y[i]-1);
                                }       
                                edge.erase({min(x[i],x[j]),max(x[i],x[j]),min(y[i],y[j]),max(y[i],y[j])});
                        }

                }
        }

        for(int i=0;i<MX;i++) {
                for(auto j:st[i]) {
                        S.insert({0,j,i});
                }
        }

        for(auto [ax,bx,ay,by]:edge) {
                if(ax==bx) {
                        upd(ax-1,ay+1,1);
                        upd(ax+1,ay+1,1);
                } else {
                        upd(ax+1,ay+1,1);
                        upd(ax+1,ay-1,1);
                }
        }

        while(S.size()) {
                auto [c,x,y]=*S.begin();
                S.erase(S.begin());

                for(int k=0;k<4;k++) {
                        int ax=x+dx[k],bx=x+ddx[k],ay=y+dy[k],by=y+ddy[k];
                        if(ax>bx) swap(ax,bx);
                        if(ay>by) swap(ay,by);

                        if(edge.count({ax,bx,ay,by})) {
                                edge.erase({ax,bx,ay,by});
                                add(getId[{ax,bx,ay,by}],x,y);

                                if(ax==bx) {
                                        upd(ax-1,ay+1,-1);
                                        upd(ax+1,ay+1,-1);
                                } else {
                                        upd(ax+1,ay+1,-1);
                                        upd(ax+1,ay-1,-1);
                                }
                                break;
                        }
                }

                if(st[y].count(x)) st[y].erase(x);
        }

        build(u, v, a, b);
        return 1;
}