Indian National Olympiad in Informatics

Related:

Online Programming Contest, 25-26 March, 2006

IARCS home > OLYMPIAD

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

Sample Output