#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define maxn 200005
#define pb push_back
typedef pair<int,int> ii;
int dx[2]={2,0},dy[2]={0,2};
bool vis[maxn],bad[4*maxn],weird[maxn];
vector<ii> squares;
map<ii,int> fid,sid,eid,use;
vector<int> AL[maxn],par[maxn];
int p[maxn],rnk[maxn];
int fp(int i){return (p[i]==i)?i:p[i]=fp(p[i]);}
void join(int x,int y){
x=fp(x),y=fp(y);
if(x==y)return;
if(rnk[x]<rnk[y])p[x]=y;
else p[y]=x;
if(rnk[x]==rnk[y])++rnk[x];
}
inline bool fin(int x,int y){
return fid.find(ii(x,y))!=fid.end();
}
inline bool sin(int x,int y){
return sid.find(ii(x,y))!=sid.end();
}
inline bool ein(int x,int y){
return eid.find(ii(x,y))!=eid.end();
}
void dfs(int u,int p){
//printf("dfs: %d %d\n",u,p);
if(p!=-1){
auto[x,y]=squares[u];
ii f1,f2;
if(p==par[u][0]){
if((x+y)%4==0){//vertical
f1={x-1,y-1},f2={x-1,y+1};
}
else{//horizontal
f1={x-1,y-1},f2={x+1,y-1};
}
}
else{
if((x+y)%4==0){//vertical
f1={x+1,y-1},f2={x+1,y+1};
}
else{//horizontal
f1={x-1,y+1},f2={x+1,y+1};
}
}
int i1=fid[f1],i2=fid[f2];
if(ein(i1,i2))bad[eid[{i1,i2}]]=true;
else bad[eid[{i2,i1}]]=true;
}
for(int v:AL[u]){
if(vis[v])continue;
vis[v]=true;
dfs(v,u);
}
}
int construct_roads(vector<int> x,vector<int> y){
int n=x.size();
for(int i=0;i<n;++i){
fid[{x[i],y[i]}]=i;
}
int scnt=0,ecnt=0;
for(int i=0;i<n;++i){
if(fin(x[i]+2,y[i])&&fin(x[i],y[i]+2)&&fin(x[i]+2,y[i]+2)){
sid[{x[i]+1,y[i]+1}]=scnt++;
squares.push_back({x[i]+1,y[i]+1});
}
for(int j=0;j<2;++j){
int nx=x[i]+dx[j],ny=y[i]+dy[j];
if(fin(nx,ny))eid[{i,fid[{nx,ny}]}]=ecnt++;
}
}
for(auto it=sid.begin();it!=sid.end();++it){
auto[x,y]=it->fi;
assert(it->se!=scnt);
if((x+y)%4==0){//vertical
for(int dx:{-2,2}){
if(sin(x+dx,y)){
AL[sid[{x+dx,y}]].push_back(it->se);
par[it->se].push_back(sid[{x+dx,y}]);
}
else{
AL[scnt].push_back(it->se);
par[it->se].push_back(scnt);
}
}
}
else{//horizontal
for(int dy:{-2,2}){
if(sin(x,y+dy)){
AL[sid[{x,y+dy}]].push_back(it->se);
par[it->se].push_back(sid[{x,y+dy}]);
}
else{
AL[scnt].push_back(it->se);
par[it->se].push_back(scnt);
}
}
}
}
vis[scnt]=true;
dfs(scnt,-1);
/*
for(auto it=sid.begin();it!=sid.end();++it){
auto[x,y]=it->fi;
if((x+y)%4==0){//vertical
int cnt=0;
for(int dx:{-1,1}){
ii f1={x+dx,y-1},f2={x+dx,y+1};
int i1=fid[f1],i2=fid[f2];
if(ein(i1,i2)&&!bad[eid[{i1,i2}]])++cnt;
else if(ein(i2,i1)&&!bad[eid[{i2,i1}]])++cnt;
}
if(cnt==2)assert(false);
}
else{//horizontal
int cnt=0;
for(int dy:{-1,1}){
ii f1={x-1,y+dy},f2={x+1,y+dy};
int i1=fid[f1],i2=fid[f2];
if(ein(i1,i2)&&!bad[eid[{i1,i2}]])++cnt;
else if(ein(i2,i1)&&!bad[eid[{i2,i1}]])++cnt;
}
if(cnt==2)assert(false);
}
}
*/
for(int i=0;i<n;++i)p[i]=i;
vector<int> u,v,a,b;
for(auto it=eid.begin();it!=eid.end();++it){
if(bad[it->se])continue;
auto[i,j]=it->fi;
if(fp(i)==fp(j))continue;
join(i,j);
int x1=x[i],x2=x[j],y1=y[i],y2=y[j];
int bx,by;
if(x1==x2){
if((x1-1+(y1+y2)/2)%4==0)bx=x1-1,by=(y1+y2)/2;
else bx=x1+1,by=(y1+y2)/2;
}
else{
if(((x1+x2)/2+y1-1)%4!=0)bx=(x1+x2)/2,by=y1-1;
else bx=(x1+x2)/2,by=y1+1;
}
u.pb(i),v.pb(j),a.pb(bx),b.pb(by);
int idk=use[{bx,by}];
use[{bx,by}]=true;
}
for(int i=0;i<n;++i){
if(fp(i)!=fp(0))return 0;
}
build(u,v,a,b);
return 1;
}
