#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int construct_roads(vector<int> x,vector<int> y){
int n = x.size();
map<pair<int,int>,int> lookup;
set<pair<int,int>> edges;
for(int i=0;i<n;i++)lookup[{x[i],y[i]}]=i;
vector<int> u,v,a,b;
vector<vector<int>> adj(n);
for(int i=0;i<n;i++){
bool works = false;
if(lookup.count({x[i]+2,y[i]})){
works=true;
if(edges.count({i,lookup[{x[i]+2,y[i]}]}))continue;
edges.emplace(lookup[{x[i]+2,y[i]}],i);
u.emplace_back(i);
v.emplace_back(lookup[{x[i]+2,y[i]}]);
adj[i].emplace_back(lookup[{x[i]+2,y[i]}]);
adj[lookup[{x[i]+2,y[i]}]].emplace_back(i);
a.emplace_back(x[i]+1);
b.emplace_back(y[i]-1);
}
if(lookup.count({x[i]-2,y[i]})){
works = true;
if(edges.count({i,lookup[{x[i]-2,y[i]}]}))continue;
edges.emplace(lookup[{x[i]-2,y[i]}],i);
u.emplace_back(i);
v.emplace_back(lookup[{x[i]-2,y[i]}]);
adj[i].emplace_back(lookup[{x[i]-2,y[i]}]);
adj[lookup[{x[i]-2,y[i]}]].emplace_back(i);
a.emplace_back(x[i]-1);
b.emplace_back(y[i]-1);
}
if(x[i]==4 and works)continue;
if(lookup.count({x[i],y[i]+2})){
if(edges.count({i,lookup[{x[i],y[i]+2}]}))continue;
edges.emplace(lookup[{x[i],y[i]+2}],i);
u.emplace_back(i);
v.emplace_back(lookup[{x[i],y[i]+2}]);
adj[i].emplace_back(lookup[{x[i],y[i]+2}]);
adj[lookup[{x[i],y[i]+2}]].emplace_back(i);
if(x[i]==2)a.emplace_back(x[i]-1);
else a.emplace_back(x[i]+1);
b.emplace_back(y[i]+1);
}
if(lookup.count({x[i],y[i]-2})){
if(edges.count({i,lookup[{x[i],y[i]-2}]}))continue;
edges.emplace(lookup[{x[i],y[i]-2}],i);
u.emplace_back(i);
v.emplace_back(lookup[{x[i],y[i]-2}]);
adj[i].emplace_back(lookup[{x[i],y[i]-2}]);
adj[lookup[{x[i],y[i]-2}]].emplace_back(i);
if(x[i]==2)a.emplace_back(x[i]-1);
else a.emplace_back(x[i]+1);
b.emplace_back(y[i]-1);
}
}
vector<bool> visited(n);
int vis = 0;
function<void(int)> dfs = [&](int x){
if(visited[x])return;
visited[x]=true;
vis++;
for(int&i:adj[x])dfs(i);
};
dfs(0);
if(vis!=n)return 0;
build(u,v,a,b);
return 1;
}
