Your Maths professor is a very nice guy, but he sometimes comes up with not so funny tasks. Today is one such day. The professor drew a bunch of parallel line segments on the board and asked the following question: "How many of these segments can be touched, even on their edges, by exactly two lines perpendicular to them?"
After a few seconds, he spoke again: "Let's make it more interesting. I will give you the starting and the ending points of ~N~ segments over the X's axis; today's homework will be to answer the question I asked you above for any set of such segments". Right after the professor's words, one guy asked: "Is there any restriction over the segments' location?", and the professor replied: "Not really, they are just segments, so they can overlap in all the ways you may imagine."
Everybody started thinking of the weird and unexpected task, without getting a convincing result. Some time later, the class got over and before leaving the classroom, the professor said: "Just to take this to the ultimate limits, your final qualification will depend entirely on this task. Good luck and please, don't try to cheat, I will know if you try to do so." So, that was it! Your final Maths qualification was hooked to some play on segments stuff.
Input consists of several test cases. The first line in the input is an integer, ~T~, denoting the number of test cases. ~T~ test cases follow, each one with the following format:
A single line with an integer, ~N~, denoting the number of segments.
~N~ lines, each defining a segment with two integers, ~a~ and ~b~, separated by a single white space, meaning that there is a segment going from ~a~ to ~b~.
~1 \le T \le 5~
~1 \le N \le 10^5~
~0 \le a < b \le 10^9~
For each test case the output should follow the following format:
- A single line with
Case #: answerwhere # is the serial number of the current test case (start the numbering from 1) and answer is the maximum number of segments you can touch as described above.
See the sample output for more details.
4 5 2 3 1 3 1 5 3 4 4 5 5 1 2 1 3 2 3 1 4 1 5 4 1 5 1 6 1 7 8 10 3 1 2 3 4 5 6
Case 1: 5 Case 2: 5 Case 3: 4 Case 4: 2
Explanation of Output for Sample Input
- Case 1: We will draw two lines (parallel to Y-axis) crossing X-axis at point ~2~ and ~4~. These two lines will touch all the five segments.
- Case 2: We can touch all the points even with one line crossing X-axis at ~2~.
- Case 3: We will draw first line at any point in range ~[1,5]~ so that it can touch first three lines. We will draw second line crossing X-axis at any of the points in range ~[8,10]~ and it will touch the last line.
- Case 4: It is not possible to touch more than two lines in this case.
Original Problem Author: shaka_shadows; Problem Resource: Hackerrank