黑白点的匹配问题描述.txt

黑白点匹配问题

黑白点的匹配
 
Time Limit: 1 Seconds     Memory Limit: 32768 K

Total Submit:196     Accepted:41

--------------------------------------------------------------------------------
 
Description

设平面上分布着n个白点和n个黑点，每个点用一对坐标（x, y）表示。一个黑点b=（xb,yb）支配一个白点w=(xw, yw)当且仅当xb>=xw和yb>=yw。若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对）。在一个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求n个白点和n个黑点的最大匹配对数。 

Input

输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含1个正整数n；第二行含2n个实数xb1, yb1,xb2, yb2,…, xbn, ybn， (xbi, ybi)，i=1, 2, …, n表示n个黑点的坐标；第三行含2n个实数xw1, yw1,xw2, yw2,…, xwn, ywn，(xwi, ywi)，i=1, 2, …, n表示n个白点的坐标。同一行的实数之间用一个空格隔开。

Output

对于每个测试例输出一行，含一个整数，表示n个白点和n个黑点的最大匹配对数。

Sample Input


1
3
5.0 3.0 5.0 -1.0 4.0 4.0
2.0 3.5 2.0 2.0 -2.0 -2.0

Sample Output


3
Source

算法设计作业