2198: 宝典2第十一章友好城市

【题目描述】友好城市（city.cpp/c/pas）

一条河从东向西流过，并把魔法世界分为南北两个部分。河的两岸各有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

5

4 5

2 4

5 2

1 3

3 1

【输出样例】

3