Maximum Non-Crossing Bridges

You are given a list of potential bridges connecting two cities. Each bridge connects a point in city Alpha to a point in city Beta. Two bridges cross if and only if the order of their connecting points is inverted between the two cities. Your task is to determine the maximum number of bridges that can be built such that no two bridges cross.

This problem can be reduced to finding the longest increasing subsequence (LIS) of the second city points after sorting the bridges by the first city points. In mathematical terms, if after sorting we obtain a sequence \(b_1, b_2, \dots, b_n\), then you need to compute

$$ \text{LIS}(\{b_i\}) $$

which represents the maximum set of non-crossing bridges.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n representing the number of potential bridges.
• Each of the following n lines contains two space‐separated integers a and b where a is the connection point in city Alpha and b is the connection point in city Beta.

outputFormat

Output a single integer to stdout, which is the maximum number of bridges that can be constructed without any crossings.

## sample

5
5 6
1 2
2 3
3 4
4 5

5

</p>