Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的$N$个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

输入格式

第$1$行，一个整数$N$，表示城市数。

第$2$行到第$n+1$行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式

仅一行，输出一个整数，表示政府所能批准的最多申请数。

数据范围

$1≤N≤5000,$
$0≤xi≤10000$

输入样例：

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出样例：

4

首先，将所有城市按照南岸的坐标进行排序。然后使用一个数组 northEnds 来存储已选航线的最北端坐标。接着遍历排序后的城市，对于每个城市，我们查找 northEnds 中第一个大于等于当前城市北岸坐标的位置，如果找不到，则说明可以开辟一条新的航道，否则就更新相应位置的北岸坐标。最终输出 northEnds 的大小即为政府所能批准的最多申请数。

#include <iostream>
#include <algorithm>

using namespace std;

template<typename typC,typename typD> istream &operator>>(istream &cin,pair<typC,typD> &a) { return cin>>a.first>>a.second; }
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> cities(n);
    cin >> cities;

    sort(cities.begin(), cities.end());

    vector<int> northEnds; // 存储已选航线的最北端坐标
    for (int i = 0; i < n; ++i) {
        int curCityNorth = cities[i].second;
        auto it = upper_bound(northEnds.begin(), northEnds.end(), curCityNorth);
        if (it == northEnds.end()) {
            northEnds.push_back(curCityNorth);
        } else {
            *it = curCityNorth;
        }
    }

    cout << northEnds.size();

    return 0;
}