4164: 轮船问题(ship)

【问题描述】

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

【输入格式】

包括了若干组数据，每组数据格式如下：

第一行两个由空格分隔的整数x，y(10≤x≤6000，10≤y≤100)。x表示河的长度而y表示宽。

第二行是一个整数n(1≤n≤5000)，表示分布在河两岸的城市对数。接下来的n行每行有两个由空格分隔的正整数C，D(C、D≤x)，描述每一对友好城市与河起点的距离，C表示北岸城市的距离而D表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。

【输出格式】

输出每一组数据在安全条件下能够开通的最大航线数目。

【输入样例】

30 4

3

4 5

5 2

1 3

【输出样例】

2