Horizontal and Vertical Rays

There are H horizontal rays and V vertical rays. A horizontal ray is a straight line which originates at some point and extends infinitely far to the right (towards increasing X coordinates). A vertical ray is a straight line which originates at some point and extends infinitely far down (towards decreasing Y coordinates). A horizontal ray whose origin is (X_h,Y_h) touches a vertical ray whose origin is (X_v,Y_v) if X_h<=X_v and Y_h<=Y_v.
You must choose a subset S consisting of the minimum number of vertical rays such that each horizontal ray is touched by at least one vertical ray in S. It is guaranteed that it will always be possible to choose such a subset for the given test data.

The first line of input contains an integer number T, representing the number of test cases to follow. The first line of each test case contains 2 integer numbers: H (1<=H<=100.000) and V (1<=V<=100.000). The next H lines contain 2 integers each: X and Y, representing the (X,Y) coordinates of the origins of the horizontal rays. The next V lines contain 2 integers each: X and Y, representing the (X,Y) coordinates of the origins of the vertical rays. All the X and Y coordinates in the input are in the range 0 ... 50.000.000.

For each of the T test cases, in the order given in the input, print one line containing the minimum number of vertical rays chosen.

1
3 3
1 6
4 4
6 2
3 8
5 7
9 4

2

The solution might consist of the second and third vertical rays. Another solution could be formed by the first and the third vertical rays.

Mugurel Ionut Andreica

Politehnica University of Bucharest Local Team Contest 2007