#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
class UnionFind {
    vector<int> par, h;
public:
    UnionFind(int size) {
        par.assign(size, 0);
        h.assign(size, 0);
        REP(i, size) par[i] = i;
    }
    void unite(int u, int v) {
        u = root(u), v = root(v);
        if (u == v) return;
        if (h[u] > h[v]) {
            par[v] = u;
        }
        else if (h[u] < h[v]) {
            par[u] = v;
        }
        else {
            ++h[u];
            par[v] = u;
        }
    }
    bool isUnited(int u, int v) {
        return root(u) == root(v);
    }
    int root(int v) {
        if (par[v] == v) return v;
        return par[v] = root(par[v]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, h, w; cin >> n >> w >> h;
    vector<ll> X(n), Y(n);
    rep(i, n) {
		cin >> X[i] >> Y[i];
		--X[i], --Y[i];
	}
	vector<vector<ll>> g1(h), g2(w);
	rep(i, n) {
		g1[Y[i]].pb(i);
		g2[X[i]].pb(i);
	}
	UnionFind uf(n);
	rep(i, h) {
		rep(j, 1, g1[i].size()) {
			uf.unite(g1[i][j-1], g1[i][j]);
		}
	}
	rep(i, w) {
		rep(j, 1, g2[i].size()) {
			uf.unite(g2[i][j-1], g2[i][j]);
		}
	}
	set<ll> s;
	rep(i, n) s.insert(uf.root(i));
	ll ans = linf;
	if (s.size() == 1) {
		ans = n-1;
	}
	else {
		ans = n + s.size() - 1;
		set<ll> sl, sr, su, sd;
		rep(i, n) {
			ll id = uf.root(i);
			if (X[i] == 0) sl.insert(id);
			if (X[i] == w-1) sr.insert(id);
			if (Y[i] == 0) su.insert(id);
			if (Y[i] == h-1) sd.insert(id);
		}
		ans -= max(max(sl.size(), sr.size()), max(su.size(), sd.size()));
	}
	cout << ans << endl;
}
### Prompt

Generate a Cpp solution to the following problem:

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
class UnionFind {
    vector<int> par, h;
public:
    UnionFind(int size) {
        par.assign(size, 0);
        h.assign(size, 0);
        REP(i, size) par[i] = i;
    }
    void unite(int u, int v) {
        u = root(u), v = root(v);
        if (u == v) return;
        if (h[u] > h[v]) {
            par[v] = u;
        }
        else if (h[u] < h[v]) {
            par[u] = v;
        }
        else {
            ++h[u];
            par[v] = u;
        }
    }
    bool isUnited(int u, int v) {
        return root(u) == root(v);
    }
    int root(int v) {
        if (par[v] == v) return v;
        return par[v] = root(par[v]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, h, w; cin >> n >> w >> h;
    vector<ll> X(n), Y(n);
    rep(i, n) {
		cin >> X[i] >> Y[i];
		--X[i], --Y[i];
	}
	vector<vector<ll>> g1(h), g2(w);
	rep(i, n) {
		g1[Y[i]].pb(i);
		g2[X[i]].pb(i);
	}
	UnionFind uf(n);
	rep(i, h) {
		rep(j, 1, g1[i].size()) {
			uf.unite(g1[i][j-1], g1[i][j]);
		}
	}
	rep(i, w) {
		rep(j, 1, g2[i].size()) {
			uf.unite(g2[i][j-1], g2[i][j]);
		}
	}
	set<ll> s;
	rep(i, n) s.insert(uf.root(i));
	ll ans = linf;
	if (s.size() == 1) {
		ans = n-1;
	}
	else {
		ans = n + s.size() - 1;
		set<ll> sl, sr, su, sd;
		rep(i, n) {
			ll id = uf.root(i);
			if (X[i] == 0) sl.insert(id);
			if (X[i] == w-1) sr.insert(id);
			if (Y[i] == 0) su.insert(id);
			if (Y[i] == h-1) sd.insert(id);
		}
		ans -= max(max(sl.size(), sr.size()), max(su.size(), sd.size()));
	}
	cout << ans << endl;
}
```