#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, mv;
queue<int> ready;
for (int i=0; i<e.size(); i++){
todo.insert(i);
mv.insert(i);
if (ttb[btt[i].first].size() == 1 || ttb[btt[i].second].size() == 1) ready.push(i);
}
vector<int> u, v, a, b;
set<ll> done;
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);
done.insert(h(a.back(), b.back()));
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;
}
else {
bool fts = false;
int cur = *todo.begin();
if (!mv.empty()){
cur = *mv.begin();
mv.erase(cur);
fts = true;
}
if (todo.find(cur) == todo.end()) continue;
int i = e[cur].first, j = e[cur].second;
if (find(i) != find(j)){
pair<int,int> des;
if (x[i] == x[j]){
des.second = (y[i]+y[j])/2;
int rp = ((x[i]+1)/2+des.second/2) % 2;
if (rp) des.first = x[i]+1;
else des.first = x[i]-1;
}
else {
des.first = (x[i]+x[j])/2;
int up = ((y[i]+1)/2+des.first/2) % 2;
if (up) des.second = y[i]-1;
else des.second = y[i]+1;
}
if (done.find(h(des.first, des.second)) != done.end()){
if (fts) continue;
ll cringe = btt[cur].first;
if (cringe == h(des.first, des.second)) cringe = btt[cur].second;
des = rh(cringe);
}
if (done.find(h(des.first, des.second)) == done.end()){
u.push_back(i);
v.push_back(j);
a.push_back(des.first);
b.push_back(des.second);
done.insert(h(a.back(), b.back()));
merge(i, j);
todo.erase(cur);
ll tbd = btt[cur].first;
if (tbd == h(des.first, des.second)) tbd = btt[cur].second;
ttb[tbd].erase(cur);
if (ttb[tbd].size() == 1) ready.push(*ttb[tbd].begin());
}
}
else {
todo.erase(cur);
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;
}
