/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */
/* union_find.cpp {{{ */
class UnionFind {
public:
  UnionFind(int n = 0): cnt(n), data(n, -1){}
  int root(int x) const { return data[x] < 0 ? x : (data[x] = root(data[x])); }
  bool same(int x, int y) const { return root(x) == root(y); }
  bool unite(int x, int y){
    if ((x = root(x)) == (y = root(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    cnt--;
    return true;
  }
  int count() const { return cnt; }
  int size(int x) const { return -data[root(x)]; }
private:
  int cnt;
  mutable vector<int> data;
};
/* }}} */

int n, w, h;
int x[40000], y[40000];
vector<tuple<int, int, int>> v, u;
bool f[40000][4];

int main(){
  cin >> n >> w >> h;
  rep(i, n) cin >> x[i] >> y[i];
  rep(i, n){
    if (x[i] == 1) f[i][0] = true;
    if (x[i] == w) f[i][1] = true;
    if (y[i] == 1) f[i][2] = true;
    if (y[i] == h) f[i][3] = true;
  }
  rep(i, n) v.emplace_back(x[i], y[i], i);
  rep(i, n) u.emplace_back(y[i], x[i], i);
  sort(all(v)), sort(all(u));
  UnionFind tr(n);
  rep(i, n - 1){
    int ax, ay, ai, bx, by, bi;
    tie(ax, ay, ai) = v[i];
    tie(bx, by, bi) = v[i + 1];
    if (ax == bx){
      rep(i, 4) f[tr.root(bi)][i] |= f[tr.root(ai)][i];
      rep(i, 4) f[tr.root(ai)][i] |= f[tr.root(bi)][i];
      tr.unite(ai, bi);
    }
  }
  rep(i, n - 1){
    int ay, ax, ai, by, bx, bi;
    tie(ay, ax, ai) = u[i];
    tie(by, bx, bi) = u[i + 1];
    if (ay == by){
      rep(i, 4) f[tr.root(bi)][i] |= f[tr.root(ai)][i];
      rep(i, 4) f[tr.root(ai)][i] |= f[tr.root(bi)][i];
      tr.unite(ai, bi);
    }
  }
  int mn = inf;
  rep(i, 4){
    int res = n + tr.count() - 1;
    rep(j, n) if (tr.root(j) == j && f[j][i]) res--;
    chmin(mn, res);
  }
  if (tr.count() == 1) chmin(mn, n - 1);
  cout << mn << endl;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

There is a grid of size W × H surrounded by walls. Some cells in the grid are occupied by slimes. The slimes want to unite with each other and become a "King Slime".

In each move, a slime can move to east, west, south and north direction until it enters a cell occupied by another slime or hit the surrounding wall. If two slimes come together, they unite and become a new slime.

Your task is write a program which calculates the minimum number of moves that all the slimes unite and become a King Slime. Suppose slimes move one by one and they never move simultaneously.



Input

The first line contains three integers N (2 ≤ N ≤ 40,000), W and H (1 ≤ W, H ≤ 100,000), which denote the number of slimes, the width and the height of the grid respectively.

The following N lines describe the initial coordinates of the slimes. The i-th line contains two integers xi (1 ≤ xi ≤ W) and yi (1 ≤ yi ≤ H), which indicate the coordinates of the i-th slime . All the coordinates are 1-based.

You may assume that each cell is occupied by at most one slime initially.

Output

Output the minimum number of moves that all the slimes unite and become a King Slime.

Examples

Input

4 3 3
1 1
1 3
3 1
3 3


Output

3


Input

2 3 3
2 2
3 3


Output

2


Input

2 4 4
2 2
3 3


Output

3


Input

2 4 4
2 2
2 3


Output

1

### Response

```cpp
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */
/* union_find.cpp {{{ */
class UnionFind {
public:
  UnionFind(int n = 0): cnt(n), data(n, -1){}
  int root(int x) const { return data[x] < 0 ? x : (data[x] = root(data[x])); }
  bool same(int x, int y) const { return root(x) == root(y); }
  bool unite(int x, int y){
    if ((x = root(x)) == (y = root(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    cnt--;
    return true;
  }
  int count() const { return cnt; }
  int size(int x) const { return -data[root(x)]; }
private:
  int cnt;
  mutable vector<int> data;
};
/* }}} */

int n, w, h;
int x[40000], y[40000];
vector<tuple<int, int, int>> v, u;
bool f[40000][4];

int main(){
  cin >> n >> w >> h;
  rep(i, n) cin >> x[i] >> y[i];
  rep(i, n){
    if (x[i] == 1) f[i][0] = true;
    if (x[i] == w) f[i][1] = true;
    if (y[i] == 1) f[i][2] = true;
    if (y[i] == h) f[i][3] = true;
  }
  rep(i, n) v.emplace_back(x[i], y[i], i);
  rep(i, n) u.emplace_back(y[i], x[i], i);
  sort(all(v)), sort(all(u));
  UnionFind tr(n);
  rep(i, n - 1){
    int ax, ay, ai, bx, by, bi;
    tie(ax, ay, ai) = v[i];
    tie(bx, by, bi) = v[i + 1];
    if (ax == bx){
      rep(i, 4) f[tr.root(bi)][i] |= f[tr.root(ai)][i];
      rep(i, 4) f[tr.root(ai)][i] |= f[tr.root(bi)][i];
      tr.unite(ai, bi);
    }
  }
  rep(i, n - 1){
    int ay, ax, ai, by, bx, bi;
    tie(ay, ax, ai) = u[i];
    tie(by, bx, bi) = u[i + 1];
    if (ay == by){
      rep(i, 4) f[tr.root(bi)][i] |= f[tr.root(ai)][i];
      rep(i, 4) f[tr.root(ai)][i] |= f[tr.root(bi)][i];
      tr.unite(ai, bi);
    }
  }
  int mn = inf;
  rep(i, 4){
    int res = n + tr.count() - 1;
    rep(j, n) if (tr.root(j) == j && f[j][i]) res--;
    chmin(mn, res);
  }
  if (tr.count() == 1) chmin(mn, n - 1);
  cout << mn << endl;
}
```