#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll k = 1ll<<20;
ll h(ll x, ll y){
return x*k+y;
}
pair<int,int> rh(ll x){
return {x/k, x%k};
}
vector<int> p;
int find(int a){
if (a == p[a]) return p[a];
return p[a] = find(p[a]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
p[b] = a;
}
int construct_roads(vector<int> x, vector<int> y){
int n = x.size();
map<int,vector<pair<int,int>>> rows, cols;
for (int i=0; i<n; i++){
rows[x[i]].push_back({y[i], i});
cols[y[i]].push_back({x[i], i});
}
vector<pair<ll,ll>> btt;
map<ll,set<int>> ttb;
vector<pair<int,int>> e;
for (auto [i, v] : rows){
sort(v.begin(), v.end());
for (int j=0; j+1<v.size(); j++){
if (v[j].first+2 == v[j+1].first){
e.push_back({v[j].second, v[j+1].second});
btt.push_back({h(i-1, v[j].first+1), h(i+1, v[j].first+1)});
ttb[h(i-1, v[j].first+1)].insert((int)e.size()-1);
ttb[h(i+1, v[j].first+1)].insert((int)e.size()-1);
}
}
}
for (auto [i, v] : cols){
sort(v.begin(), v.end());
for (int j=0; j+1<v.size(); j++){
if (v[j].first+2 == v[j+1].first){
e.push_back({v[j].second, v[j+1].second});
btt.push_back({h(v[j].first+1, i-1), h(v[j].first+1, i+1)});
ttb[h(v[j].first+1, i-1)].insert((int)e.size()-1);
ttb[h(v[j].first+1, i+1)].insert((int)e.size()-1);
}
}
}
p.resize(n);
for (int i=0; i<n; i++) p[i] = i;
set<int> todo;
queue<int> ready;
for (int i=0; i<e.size(); i++){
todo.insert(i);
if (ttb[btt[i].first].size() == 1 || ttb[btt[i].second].size() == 1) ready.push(i);
}
vector<int> u, v, a, b;
while (!todo.empty()){
if (!ready.empty()){
int cur = ready.front();
ready.pop();
if (todo.find(cur) == todo.end()) continue;
todo.erase(cur);
int i = e[cur].first, j = e[cur].second;
if (find(i) != find(j)){
u.push_back(i);
v.push_back(j);
pair<int,int> tree;
if (ttb[btt[cur].first].size() == 1){
tree = rh(btt[cur].first);
ttb[btt[cur].second].erase(cur);
if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
}
else {
tree = rh(btt[cur].second);
ttb[btt[cur].first].erase(cur);
if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
}
a.push_back(tree.first);
b.push_back(tree.second);
merge(i, j);
}
else {
ttb[btt[cur].first].erase(cur);
if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
ttb[btt[cur].second].erase(cur);
if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
}
continue;
}
int cur = *todo.begin();
todo.erase(cur);
int i = e[cur].first, j = e[cur].second;
if (find(i) != find(j)){
u.push_back(i);
v.push_back(j);
if (x[i] == x[j]){
b.push_back((y[i]+y[j])/2);
int rp = ((x[i]+1)/2+b.back()/2) % 2;
if (rp){
a.push_back(x[i]+1);
ttb[btt[cur].first].erase(cur);
if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
}
else {
a.push_back(x[i]-1);
ttb[btt[cur].second].erase(cur);
if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
}
}
else {
a.push_back((x[i]+x[j])/2);
int up = ((y[i]+1)/2+a.back()/2) % 2;
if (up){
b.push_back(y[i]-1);
ttb[btt[cur].second].erase(cur);
if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
}
else {
b.push_back(y[i]+1);
ttb[btt[cur].first].erase(cur);
if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
}
}
merge(i, j);
}
else {
ttb[btt[cur].first].erase(cur);
if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
ttb[btt[cur].second].erase(cur);
if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
}
}
for (int i=0; i<n; i++){
if (find(i) != find(0)) return 0;
}
build(u, v, a, b);
return 1;
}
