### Indian National Olympiad in Informatics

### Online Programming Contest, 25-26 March, 2006

### Advanced Division

Problem 2: Number Pairs, *(K Narayan Kumar, CMI)*

Here is a game involving a collection of pairs of numbers. You can
start the game at any pair in the collection. In each step, you are
allowed two types of moves:

- Reduce the first component of the pair, keeping the second one
fixed, so that you reach another pair in the collection.
- Reduce the second component of the pair, keeping the first one
fixed, so that you reach another pair in the collection.

Your objective is to take as many steps as possible by selecting a
suitable starting point and making an appropriate move at each
step.

For instance, suppose the collection of pairs is {(70,48),
(70,84), (48,84), (48,33), (48,48), (84,61), (61,70), (70,94)}.
Then, starting at (70,94) you can take 4 steps by the following
sequence of moves: (70,94) →(70,84) →(48,84) →(48,48)
→ (48,33). This is the maximum number of steps possible given
this collection of pairs.

Your task is to determine the maximum number of steps that can be
taken for the given collection of pairs. You may assume that there
are at most 1000 distinct numbers among the pairs.

Input format

The first line contains a single integer *N* indicating the
number of pairs. This is followed by *N* lines each containing
two integers.

Output format

A single integer indicating the maximum number of steps that can
be taken for the given collection of pairs.

Test Data:

You may assume that 1 ≤ *N* ≤ 100,000. All pairs are
distinct. The total number of distinct values in the input is bounded
by 1000.

Example:

Here is the sample input and output corresponding to the example discussed
above.

Sample Input

8
70 48
70 84
48 84
48 33
48 48
84 61
61 70
70 94

Sample Output

4