POJ 1065

#include <iostream>
#include <algorithm>
#define MAXN  5005 
using namespace std;

struct node
{
    int l;
    int w;
    int len;
    bool lower_than(node a)
    {
        if(l < a.l || w < a.w)
        {
            return true;
        }
        return false;
    }
};

node _node[MAXN];

bool op(node a,node b)
{
    if(a.l == b.l)
    {
        return a.w < b.w;
    }
    else
    {
        return a.l < b.l;
    }
}

bool op_1(node a,node b)
{
    if(a.w == b.w)
    {
        return a.l < b.l;
    }
    else
    {
        return a.w < b.w;
    }
}

int main()
{
    //freopen("acm.acm","r",stdin);
    int test;
    int n;
    int i;
    int j;
    int max;
    cin>>test;
    while(test --)
    {
        //cin>>n;
        scanf("%d",&n);
        max = -1;
        for(i = 0; i < n; ++ i)
        {
            //cin>>_node[i].l;
            scanf("%d",&_node[i].l);
            scanf("%d",&_node[i].w);
            //cin>>_node[i].w;
            _node[i].len = 1;
        }
        sort(_node,_node+n,op);
        for(i = 0; i < n; ++ i)
        {
            for(j = 0; j < i; ++ j)
            {
                if(_node[i].lower_than(_node[j]))
                {
                    if(_node[i].len < _node[j].len + 1)
                    {
                        _node[i].len = _node[j].len + 1;
                    }
                }
            }
        }

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

            if(_node[i].len > max)
            {
                max = _node[i].len;

            }
        }

        sort(_node,_node+n,op_1);
        
        for(i = 0; i < n; ++ i)
        {
            _node[i].len = 1;
        }


        for(i = 0; i < n; ++ i)
        {
            for(j = 0; j < i; ++ j)
            {
                if(_node[i].lower_than(_node[j]))
                {
                    if(_node[i].len < _node[j].len + 1)
                    {
                        _node[i].len = _node[j].len + 1;
                    }
                }
            }
        }


        int max_1 = -1;
        for(i = 0; i < n; ++ i)
        {
            if(_node[i].len > max_1)
            {
                max_1 = _node[i].len;
            }
        }
        if(max > max_1)
        {
            max = max_1;
        }
        cout<<max<<endl;
    }
}