Printed Circuit Board

Time limit1sMemory limit128 MB

Summary

Given N wires each connecting a bottom-edge point to a top-edge point, find the minimum number of layers so that crossing wires never share a layer, which reduces to finding the maximum count of pairwise-crossing wires.

Level: Medium5 of 10
Topics: Sorting, Binary search, Greedy
Solved: No attempts yet

Problem

On a printed circuit board, conductive wires are laid on a non-conductive base. Two conductors on the same layer cannot cross without causing a short circuit, so more complex boards use several conductive layers separated by non-conductive material. Because a board with more layers costs more, manufacturers try to assign the required conductors to layers so that as few layers as possible are used.

In this problem we consider boards on which every conductor connects two ports located on opposite edges of the board, and we want to minimize the number of layers.

Consider the board shown on the left of the figure below. If one conductor must connect A to B and another must connect D to C, both can be placed on a single layer, as shown in the middle. But a conductor connecting A to C together with one connecting D to B cannot share a layer, as shown on the right.

Write a program that, given the endpoints of the $N$ conductors on a $W \times H$ board, determines the minimum number of layers needed to accommodate all of them.

You may assume that the width of a conductor is very small compared with the distances between ports; that is, between any two conductors there is always enough room for a third one.

Input

The first line contains $N$ ( $1 \le N \le 10^5$ ), the number of conductors. Each of the next $N$ lines contains two integers $X_{i1}$ and $X_{i2}$ ( $0 \le X_{ij} \le 10^6$ ), separated by a space, meaning that the $i$ -th conductor must connect the points $(X_{i1}, 0)$ and $(X_{i2}, H)$ . You may assume that all $2N$ endpoints are distinct.

Output

Print a single integer: the minimum number of layers needed to accommodate all of the required conductors.

Examples4

Example 1
Input
```
2
1 1
3 3
```
Expected output
```
1
```
Example 2
Input
```
2
1 3
3 1
```
Expected output
```
2
```
Example 3
Input
```
1
5 10
```
Expected output
```
1
```
Example 4
Input
```
5
1 2
2 4
3 6
4 8
5 10
```
Expected output
```
1
```