#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define pii pair<int, int>
const int mxN=200020;
typedef struct pnt{
int fir, sec, idx;
}pnt;
typedef struct edge{
int nxt, p1, p2;
}edge;
int N;
vector <pii> coor;
vector <edge> adj[mxN];
pnt A[mxN];
int par[mxN];
bool Chk[mxN];
vector <int> u, v, a, b;
bool cmp1(pnt a, pnt b)
{
if(a.fir!=b.fir) return a.fir<b.fir;
return a.sec<b.sec;
}
bool cmp2(pnt a, pnt b)
{
if(a.sec!=b.sec) return a.sec<b.sec;
return a.fir<b.fir;
}
int findpar(int a)
{
return (par[a]==a ? a : par[a]=findpar(par[a]));
}
void onion(int a, int b)
{
int p=findpar(a), q=findpar(b);
if(p!=q) par[p]=q;
}
void dfs1(int now, int pre)
{
Chk[now]=true;
for(auto ele : adj[now]) if(ele.nxt!=pre)
{
u.push_back(ele.p1); v.push_back(ele.p2);
a.push_back(coor[ele.nxt].fir); b.push_back(coor[ele.nxt].sec);
dfs1(ele.nxt, now);
}
}
void dfs2(int now, int pre, int s)
{
//printf("now=%d\n", now);
Chk[now]=true;
for(auto ele : adj[now]) if(ele.nxt!=pre)
{
u.push_back(ele.p1); v.push_back(ele.p2);
a.push_back(coor[now].fir); b.push_back(coor[now].sec);
if(ele.nxt==s) return;
dfs2(ele.nxt, now, s);
if(now==s) return;
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
N=x.size();
for(int i=0;i<N;i++) A[i].fir=x[i], A[i].sec=y[i], A[i].idx=i;
for(int i=0;i<N;i++) par[i]=i;
sort(A, A+N, cmp1);
for(int i=1;i<N;i++)
{
if(A[i-1].fir==A[i].fir && A[i-1].sec==A[i].sec-2)
{
onion(A[i-1].idx, A[i].idx);
coor.push_back({A[i].fir+1, A[i].sec-1});
coor.push_back({A[i].fir-1, A[i].sec-1});
}
}
sort(A, A+N, cmp2);
for(int i=1;i<N;i++)
{
if(A[i-1].sec==A[i].sec && A[i-1].fir==A[i].fir-2)
{
onion(A[i-1].idx, A[i].idx);
coor.push_back({A[i].fir-1, A[i].sec-1});
coor.push_back({A[i].fir-1, A[i].sec+1});
}
}
for(int i=1;i<N;i++) if(findpar(i)!=findpar(i-1)) return 0;
sort(coor.begin(), coor.end());
coor.erase(unique(coor.begin(), coor.end()), coor.end());
sort(A, A+N, cmp1);
for(int i=1;i<N;i++)
{
if(A[i-1].fir==A[i].fir && A[i-1].sec==A[i].sec-2)
{
pii tmp1={A[i].fir+1, A[i].sec-1}, tmp2={A[i].fir-1, A[i].sec-1};
int t1=lower_bound(coor.begin(), coor.end(), tmp1)-coor.begin();
int t2=lower_bound(coor.begin(), coor.end(), tmp2)-coor.begin();
adj[t1].push_back({t2, A[i-1].idx, A[i].idx});
adj[t2].push_back({t1, A[i-1].idx, A[i].idx});
}
}
sort(A, A+N, cmp2);
for(int i=1;i<N;i++)
{
if(A[i-1].sec==A[i].sec && A[i-1].fir==A[i].fir-2)
{
pii tmp1={A[i].fir-1, A[i].sec-1}, tmp2={A[i].fir-1, A[i].sec+1};
int t1=lower_bound(coor.begin(), coor.end(), tmp1)-coor.begin();
int t2=lower_bound(coor.begin(), coor.end(), tmp2)-coor.begin();
adj[t1].push_back({t2, A[i-1].idx, A[i].idx});
adj[t2].push_back({t1, A[i-1].idx, A[i].idx});
}
}
for(int i=0;i<coor.size();i++)
{
if(!Chk[i] && adj[i].size()==1)
{
dfs1(i, -1);
}
}
for(int i=0;i<coor.size();i++)
{
if(!Chk[i])
{
dfs2(i, -1, i);
}
}
build(u, v, a, b);
return 1;
}
