#include <bits/stdc++.h>
using namespace std;

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

struct UnionFind{
  vector<int> v;
  UnionFind(int n) : v(n, -1) {}
  void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }
  int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (-v[x] < -v[y]) swap(x, y);
    v[x] += v[y]; v[y] = x;
    return true;
  }
  bool root(int x) { return v[x] < 0; }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -v[find(x)]; }
};

int n,h,w;
vector<P> ah[100010],aw[100010];
set<int> ps,hs[4];

int main(){
	cin.sync_with_stdio(false);
  cin>>n>>w>>h;
  UnionFind uf(n);
  rep(i,n){
    int x,y;
    cin>>x>>y;
    x--; y--;
    ah[y].push_back(P(x,i)); 
    aw[x].push_back(P(y,i));
  }
  rep(i,100001){
    sort(all(ah[i]));
    sort(all(aw[i]));
  }
  rep(i,h){
    rep(j,ah[i].size()-1){
      uf.unite(ah[i][j].se,ah[i][j+1].se);
    }
  }
  rep(i,w){
    rep(j,aw[i].size()-1){
      uf.unite(aw[i][j].se,aw[i][j+1].se);
    }
  }
  if(uf.size(0)==n){
    cout<<n-1<<endl;
    return 0;
  }
  rep(i,h){
    rep(j,ah[i].size()){
      ps.insert(uf.find(ah[i][j].se));
      if(ah[i][j].fi==0)hs[0].insert(uf.find(ah[i][j].se));
      if(ah[i][j].fi==w-1)hs[1].insert(uf.find(ah[i][j].se));
    }
  }

  rep(i,w){
    rep(j,aw[i].size()){
      ps.insert(uf.find(aw[i][j].se));
      if(aw[i][j].fi==0)hs[2].insert(uf.find(aw[i][j].se));
      if(aw[i][j].fi==h-1)hs[3].insert(uf.find(aw[i][j].se));
    }
  }
  int res=INF;
  int sum=0;
  each(it,ps){
    sum+=uf.size(it)-1;
  }
  rep(k,4){
    minch(res,sum+ps.size()*2-1-hs[k].size());
  }
  cout<<res<<endl;
  return 0; 
}
### Prompt

Your challenge is to write 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 unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

struct UnionFind{
  vector<int> v;
  UnionFind(int n) : v(n, -1) {}
  void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }
  int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (-v[x] < -v[y]) swap(x, y);
    v[x] += v[y]; v[y] = x;
    return true;
  }
  bool root(int x) { return v[x] < 0; }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -v[find(x)]; }
};

int n,h,w;
vector<P> ah[100010],aw[100010];
set<int> ps,hs[4];

int main(){
	cin.sync_with_stdio(false);
  cin>>n>>w>>h;
  UnionFind uf(n);
  rep(i,n){
    int x,y;
    cin>>x>>y;
    x--; y--;
    ah[y].push_back(P(x,i)); 
    aw[x].push_back(P(y,i));
  }
  rep(i,100001){
    sort(all(ah[i]));
    sort(all(aw[i]));
  }
  rep(i,h){
    rep(j,ah[i].size()-1){
      uf.unite(ah[i][j].se,ah[i][j+1].se);
    }
  }
  rep(i,w){
    rep(j,aw[i].size()-1){
      uf.unite(aw[i][j].se,aw[i][j+1].se);
    }
  }
  if(uf.size(0)==n){
    cout<<n-1<<endl;
    return 0;
  }
  rep(i,h){
    rep(j,ah[i].size()){
      ps.insert(uf.find(ah[i][j].se));
      if(ah[i][j].fi==0)hs[0].insert(uf.find(ah[i][j].se));
      if(ah[i][j].fi==w-1)hs[1].insert(uf.find(ah[i][j].se));
    }
  }

  rep(i,w){
    rep(j,aw[i].size()){
      ps.insert(uf.find(aw[i][j].se));
      if(aw[i][j].fi==0)hs[2].insert(uf.find(aw[i][j].se));
      if(aw[i][j].fi==h-1)hs[3].insert(uf.find(aw[i][j].se));
    }
  }
  int res=INF;
  int sum=0;
  each(it,ps){
    sum+=uf.size(it)-1;
  }
  rep(k,4){
    minch(res,sum+ps.size()*2-1-hs[k].size());
  }
  cout<<res<<endl;
  return 0; 
}
```