J16 实践-4 友好城市

题目描述

某国家被一条河划分为南北两部分，在南岸和北岸总共有 $N$ 对城市，每一城市在对岸都有唯一的友好城市，任何两个城市都没有相同的友好城市。每一对友好城市都希望有一条航线来往，于是他们向政府提出了申请。由于河终年有雾。政府决定允许开通的航线就互不交叉（如果两条航线交叉，将有很大机会撞船）。兴建哪些航线以使在安全条件下有最多航线可以被开通。

输入格式

第一行整数 $x,y$，$x$ 表示河的长度而 $y$ 表示宽。 第二行是一个整数 $N$，表示分布在河两岸的城市对数。接下来的 $N$ 行每行有两个由空格分隔的正数 $C,D$，描述每一对友好城市与河起点的距离，$C$ 表示北岸城市的距离而 $D$ 表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。

输出格式

一个整数，表示在安全条件下能够开通的最大航线数目。

样例输入

30 4
5
4 5
2 4
5 2
1 3
3 1

样例输出

3

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$10 \leq C,D \leq x \leq 6000;10 \leq y \leq 100;1 \leq N \leq 5000$ 。