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.
🌊
The coordinates:
You can think of the river as the OX axis of the coordinate system.
The two parts of the city are the ones above and below the X-axis. So, the coordinates represent the
x coordinate of the start/end of the bridge.Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 100 000).The next
n lines contain pairs of integer 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