矩形嵌套

Grade 100 Open Time Wednesday, 17 June 2020, 9:30 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 9:30 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 9:30 PM
Input file rec.in Output file rec.out

【题目描述】矩形嵌套(recNYOJ 16

n个矩形,每个矩形可以用ab来描述,表示长和宽。矩形X(ab)可以嵌套在矩形Y(cd)中当且仅当acbd或者bcad(相当于旋转X矩形90度)。例如(15)可以嵌套在(62)内,但不能嵌套在(34)中。你的任务是选出尽可能多的矩形排成一行,使得除最后一个外,每一个矩形都可以嵌套在下一个矩形内。

【输入格式】

第一行是一个正整数N(0N10),表示测试数据组数。

每组测试数据的第一行是一个正整数n,表示该组测试数据中含有矩形的个数(n1 000)

随后的n行,每行有两个数ab(0ab100),表示矩形的长和宽。

【输出格式】

每组测试数据都输出一个数,表示最多符合条件的矩形数目,每组输出占一行。

【输入样例】

1

10

1 2

2 4

5 8

6 10

7 9

3 1

5 8

12 10

9 7

2 2

【输出样例】

5