#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
typedef long long ll;
int construct_roads(vector<int> x,vector<int> y)
{
int n=x.size();
map<array<int,2>,int> id;
for(int i=0;i<n;i++) id[{x[i],y[i]}]=i;
map<array<int,2>,int> bench_id;
int m=0;
auto fountain_pos=[&](int a,int b)->int{return (id.find({a,b})!=id.end()?id[{a,b}]:-1);};
auto tp=[&](int a,int b)->int{return (((a+b)/2)&1);}; //color of chessboard at this bench
for(int i=0;i<n;i++)
{
int a=x[i],b=y[i];
if(fountain_pos(a+2,b)!=-1&&fountain_pos(a,b+2)!=-1&&fountain_pos(a+2,b+2)!=-1)
{
bench_id[{a+1,b+1}]=(++m);
}
}
auto bench_pos=[&](int a,int b)->int{return (bench_id.find({a,b})!=bench_id.end()?bench_id[{a,b}]:0);};
vector<array<int,3>> g[m+1]; //to,bad_a,bad_b
for(auto [p,bench]:bench_id)
{
auto [a,b]=p;
if(tp(a,b)==0)
{
for(int dy:{-2,2})
{
int t=bench_pos(a,b+dy);
g[t].push_back({bench,fountain_pos(a-1,b+dy/2),fountain_pos(a+1,b+dy/2)});
}
}
else
{
for(int dx:{-2,2})
{
int t=bench_pos(a+dx,b);
g[t].push_back({bench,fountain_pos(a+dx/2,b-1),fountain_pos(a+dx/2,b+1)});
}
}
}
set<array<int,2>> bad_edges;
vector<bool> vis(m+1,0);
function<void(int)> dfs=[&](int a)
{
vis[a]=1;
for(auto [to,bad_a,bad_b]:g[a])
{
if(!vis[to])
{
bad_edges.insert({bad_a,bad_b});
bad_edges.insert({bad_b,bad_a});
dfs(to);
}
}
};
dfs(0);
vector<int> p(n);
for(int i=0;i<n;i++) p[i]=i;
vector<int> sz(n,1);
int cc=n;
function<int(int)> find_set=[&](int a)->int
{
if(a==p[a]) return a;
else return p[a]=find_set(p[a]);
};
auto merge_sets=[&](int a,int b)->bool
{
a=find_set(a);
b=find_set(b);
if(a==b) return 0;
if(sz[a]<sz[b]) swap(a,b);
p[b]=a;
sz[a]+=sz[b];
cc--;
return 1;
};
vector<int> ru,rv,ra,rb;
for(int i=0;i<n;i++)
{
int a=x[i],b=y[i];
//horizontal
for(int dx:{2})
{
int j=fountain_pos(a+dx,b);
if(j==-1||bad_edges.find({i,j})!=bad_edges.end()) continue;
if(merge_sets(i,j))
{
ru.push_back(i);
rv.push_back(j);
int d=(tp(a+1,b+1)==0?1:-1);
ra.push_back(a+1);
rb.push_back(b+d);
}
}
//vertical
for(int dy:{2})
{
int j=fountain_pos(a,b+dy);
if(j==-1||bad_edges.find({i,j})!=bad_edges.end()) continue;
if(merge_sets(i,j))
{
ru.push_back(i);
rv.push_back(j);
int d=(tp(a+1,b+1)==1?1:-1);
ra.push_back(a+d);
rb.push_back(b+1);
}
}
}
if(cc==1) build(ru,rv,ra,rb);
return (cc==1);
}
