将所有航线的其中一边排序后，另一边进行类dp
定义一个数组c，c[i]表示在所有能够开通i条航线的组合中，位置序号最大的那条航线的序号的最小值
比如下面一个样例
1 3
2 4
3 1
4 2
此时对于航线左边的位置序号已经是排好序的了
那么只需要考虑右边的情况
在所有只开通1条航道的组合中
右侧出现的结果可能是{1},{2},{3},{4}
所以c[1]=1
在所有只开通2条航道的组合中
右侧出现的结果可能是{3,4},{1,2}
这里有两个组合，每个组合位置序号最大的元素分别是4和2，取小
得到c[2]=2
同时我们可以发现c数组是严格递增的
那么定义完了c数组，说下它有什么用
因为航线左端排好序，每次考虑的值都是右端序号
重新举个例子
1 4
2 5
3 1
4 2
5 3
只拿右端序列，得到dp对象为4 5 1 2 3
考虑4，得到c[1]=4，答案更新为1
考虑5，因为5>4，且左侧序号递增，所以可以得到这条航线与终点为4的航线不重叠，可以组合，所以c[2]=5，答案更新为2
考虑1，因为c数组内没有元素比1小，所以更新c[1]=1，答案不变，为2
考虑2，得到c[1]<2，所以可以和此时c[1]指代的航线组合，更新c[2]=2，答案不变，为2
考虑3，得到c[2]<3，所以可以和此时c[2]指代的2条航线组合，c[3]=3，答案更新为3
首先，答案就是能够组合在一起的最大数量，即c数组最大的下标
那么为什么可以这样更新呢？
从形式上看，更新了数组之后相当于破坏了前面的航线的结论（看上去会让前面的航线交叉）
实际上，因为每考虑到一个点的时候，可以视为前面的点能组合的都已经组合完毕
更新c数组的元素，是为了贪心让之后的点加进来后对答案贡献更大，让其后的点能有更优的组合
对于代码实现，取用lower_bound函数或者手动模拟二分查找（已知现有c数组是有序的）
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int m=;
struct line{
int a,b;
bool operator < (const line& x) const{
return a<x.a;
}
}r[m];
int c[m];
int main(){
ios::sync_with_stdio();
cin.tie();cout.tie();
int T,n,i,p,ans;
cin>>T;
while(T--){
cin>>n;
for(i=;i<=n;i++)
cin>>r[i].a>>r[i].b;
sort(r+,r++n);
memset(c,INF,sizeof c);
ans=;
for(i=;i<=n;i++){
p=lower_bound(c+,c++ans,r[i].b)-c;
ans=max(ans,p);
c[p]=r[i].b;
}
cout<<ans<<endl;
} return ;
}