Bridge Building
There is a city with a beautiful river crossing it right at the center. The municipality of the city decides to build bridges to connect the city. Currently, people use boats to cross the river, which is not convenient.
The city has identified n pairs of coordinates that could be connected with a bridge. Yet, they have a requirement that the bridges cannot cross each other (one bridge cannot go over the other). They can share the ending/starting points though.
Given the pairs of coordinates that could be connected, you are asked to find the maximum number of bridges the municipality can build without violating the requirements.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000).
The next n lines contain pairs of integer representing the coordinates that could be connected (1 ≤ ≤ ).
Output
The program should print a single integer - the maximum number of bridges the municipality could build.
Examples
Input | Output |
|---|---|
4 2 6 5 4 8 1 10 2 | 2 |
6 1 3 2 4 3 5 4 6 5 1 6 2 | 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB