有n個矩形，每個矩形可以用a,b來描述，表示長和寬。矩形X(a,b)可以嵌套在矩形Y(c,d)中當且僅當a<c,b<d或者b<c,a<d（相當于旋轉X90度）。例如（1,5）可以嵌套在（6,2）内，但

.

#include<stdio.h>

02.

#include<string.h>

03.

#include<algorithm>

04.

using

namespace

std;

05.

struct

stu

06.

{

07.

int

a,b;

08.

}s[1020];

09.

int

dp[1020];

10.

int

cmp(stu x,stu y)

11.

{

12.

if

(x.a<y.a)

13.

return

1;

14.

else

if

(x.a==y.a&&x.b<y.b)

15.

return

1;

16.

else

17.

return

0;

18.

}

19.

int

main()

20.

{

21.

int

t,i;

22.

scanf

(

"%d"

,&t);

23.

while

(t--)

24.

{

25.

int

n,j,ans;

26.

scanf

(

"%d"

,&n);

27.

for

(i=0;i<n;i++)

28.

{

29.

scanf

(

"%d%d"

,&s[i].a,&s[i].b);

30.

if

(s[i].a<s[i].b)

31.

swap(s[i].a,s[i].b);

32.

}

33.

sort(s,s+n,cmp);

34.

ans=0;

35.

for

(i=0;i<n;i++)

36.

{

37.

dp[i]=1;

38.

for

(j=0;j<i;j++)

39.

{

40.

if

(s[j].a<s[i].a&&s[j].b<s[i].b)

41.

dp[i]=max(dp[i],dp[j]+1);

42.

}

43.

ans=max(ans,dp[i]);

44.

}

45.

printf

(

"%d\n"

,ans);

46.

}

47.

return

0;

48.

}