#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
const int M = 2e5;
set<int> nei[M];
bool vis[M];
void dfs(int u)
{
vis[u]=true;
for (int i:nei[u])
if (!vis[i])
dfs(i);
}
int construct_roads(vector<int> x, vector<int> y)
{
int n=x.size();
map<pair<int,int>,int> ind;
for (int i=0;i<n;i++)
ind[{x[i],y[i]}]=i;
for (int i=0;i<n;i++)
for (int j=-2;j<=2;j+=2)
for (int k=-2;k<=2;k+=2)
{
if ((j==0)==(k==0))
continue;
if (ind.find({x[i]+j,y[i]+k})!=ind.end())
nei[i].insert(ind[{x[i]+j,y[i]+k}]);
}
dfs(0);
for (int i=0;i<n;i++)
if (!vis[i])
return 0;
set<pair<int,int>> se;
vector<int> u,v,a,b;
for (int i=0;i<n;i++)
{
bool o=true;
for (int j=-2;j<=2 and o;j+=2)
for (int k=-2;k<=2 and o;k+=2)
{
if ((j==0)==(k==0))
continue;
if (ind.find({x[i]+j,y[i]+k})==ind.end())
o=false;
}
if (o)
{
u.push_back(i),v.push_back(ind[{x[i],y[i]-2}]);
a.push_back(x[i]-1),b.push_back(y[i]-1);
se.insert({a.back(),b.back()});
u.push_back(i),v.push_back(ind[{x[i]-2,y[i]}]);
a.push_back(x[i]-1),b.push_back(y[i]+1);
se.insert({a.back(),b.back()});
u.push_back(i),v.push_back(ind[{x[i],y[i]+2}]);
a.push_back(x[i]+1),b.push_back(y[i]+1);
se.insert({a.back(),b.back()});
u.push_back(i),v.push_back(ind[{x[i]+2,y[i]}]);
a.push_back(x[i]+1),b.push_back(y[i]-1);
se.insert({a.back(),b.back()});
nei[i].erase(ind[{x[i],y[i]-2}]),nei[ind[{x[i],y[i]-2}]].erase(i);
nei[i].erase(ind[{x[i]-2,y[i]}]),nei[ind[{x[i]-2,y[i]}]].erase(i);
nei[i].erase(ind[{x[i],y[i]+2}]),nei[ind[{x[i],y[i]+2}]].erase(i);
nei[i].erase(ind[{x[i]+2,y[i]}]),nei[ind[{x[i]+2,y[i]}]].erase(i);
}
}
for (int i=0;i<n;i++)
for (int j:nei[i])
{
if (x[i]==x[j])
{
int avg=(y[i]+y[j])/2;
if (se.find({x[i]-1,avg})==se.end())
{
u.push_back(i),v.push_back(j);
a.push_back(x[i]-1),b.push_back(avg);
se.insert({a.back(),b.back()});
}
else
{
u.push_back(i),v.push_back(j);
a.push_back(x[i]+1),b.push_back(avg);
se.insert({a.back(),b.back()});
}
}
else
{
int avg=(x[i]+x[j])/2;
if (se.find({avg,y[i]-1})==se.end())
{
u.push_back(i),v.push_back(j);
a.push_back(avg),b.push_back(y[i]-1);
se.insert({a.back(),b.back()});
}
else
{
u.push_back(i),v.push_back(j);
a.push_back(avg),b.push_back(y[i]+1);
se.insert({a.back(),b.back()});
}
}
nei[j].erase(i);
}
build(u,v,a,b);
return 1;
}
