King Slime

Time limit8sMemory limit512 MB

Summary

Given N slimes on a W by H grid that slide until they hit a slime or a wall, find the fewest moves needed to merge them all into one.

Level: Medium7 of 10
Topics: Minimum spanning tree, Union-find, Sorting
Solved: No attempts yet

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 moves east, west, south, or north until it enters a cell occupied by another slime or hits the surrounding wall. When two slimes come together, they unite and become a new slime.

Write a program that calculates the minimum number of moves needed for all the slimes to unite and become a King Slime. The slimes move one by one, and they never move simultaneously.

Input

The first line contains three integers N, W, and H (2 ≤ N ≤ 40000, 1 ≤ W, H ≤ 100000), where N is the number of slimes and W and H are the width and height of the grid.

The next 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 are the coordinates of the i-th slime. All coordinates are 1-based.

You may assume that each cell holds at most one slime initially.

Output

Output the minimum number of moves needed for all the slimes to unite and become a King Slime.

Examples4

Example 1
Input
```
4 3 3
1 1
1 3
3 1
3 3
```
Expected output
```
3
```
Example 2
Input
```
2 3 3
2 2
3 3
```
Expected output
```
2
```
Example 3
Input
```
2 4 4
2 2
3 3
```
Expected output
```
3
```
Example 4
Input
```
2 4 4
2 2
2 3
```
Expected output
```
1
```