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
npairs 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
xcoordinate of the start/end of the bridge.
The first line of the input contains a single integer
n(1 ≤ n ≤ 100 000).
nlines contain pairs of integer
representing the coordinates that could be connected (1 ≤ ≤ ).
The program should print a single integer - the maximum number of bridges the municipality could build.
4 2 6 5 4 8 1 10 2
6 1 3 2 4 3 5 4 6 5 1 6 2
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB