#include "parks.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto,auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
os<<"{";
for(auto it=begin(v);it!=end(v);++it) {
if(it != begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
struct UF {
vi e;
UF(int n) : e(n, -1) {}
bool sameSet(int a, int b) { return find(a) == find(b); }
int size(int x) { return -e[find(x)]; }
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (e[a] > e[b]) swap(a, b);
e[a] += e[b]; e[b] = a;
return true;
}
};
struct Fountain {
int x, y, index;
friend bool operator<(const Fountain &a, const Fountain &b) {
return tie(a.x, a.y) < tie(b.x, b.y);
}
};
struct Bench {
int a, b;
int x, y;
friend bool operator<(const Bench &a, const Bench &b) {
return tie(a.x, a.y) < tie(b.x, b.y);
}
};
void build_from_benches(set<Bench> &benches) {
vi u, v, a, b;
for(auto bench : benches) {
u.push_back(bench.a);
v.push_back(bench.b);
a.push_back(bench.x);
b.push_back(bench.y);
}
build(u, v, a, b);
}
int construct_roads(vi x, vi y) {
int n = sz(x);
dbg(x, y);
set<Fountain> s;
rep(i,0,n) s.insert({x[i], y[i], i});
set<Bench> benches;
UF uf(n);
for(auto f : s) {
{
auto it = s.find({f.x - 2, f.y, -1});
if(it != s.end()) {
auto t = *it;
if(uf.find(f.index) != uf.find(t.index)) {
Bench b;
b.a = f.index;
b.b = t.index;
b.x = f.x - 1;
b.y = f.y - 1;
if(benches.count(b))
b.y = f.y + 1;
if(benches.count(b))
return 0;
benches.insert(b);
uf.join(f.index, t.index);
}
}
}
{
auto it = s.find({f.x, f.y - 2, -1});
if(it != s.end()) {
auto t = *it;
if(uf.find(f.index) != uf.find(t.index)) {
Bench b;
b.a = f.index;
b.b = t.index;
b.y = f.y - 1;
b.x = f.x - 1;
if(benches.count(b))
b.x = f.x + 1;
if(benches.count(b))
return 0;
benches.insert(b);
uf.join(f.index, t.index);
}
}
}
}
int index = uf.find(0);
rep(i,0,n)
if(uf.find(i) != index)
return 0;
build_from_benches(benches);
return 1;
}
