题目描述
有一个国家被一条河划分为南北两部分,在南岸和北岸总共有N个城镇,每一城镇在对岸都有唯一的友好城镇.任何两个城镇都没有相同的友好城镇.每一对友好城镇都希望有一条航线来往.于是他们向政府提出了申请.由于河中年有雾,政府决定不允许有任何两条航线交叉(如果两条航线交叉,将有很大机会撞船).
你的任务是编写一个程序来帮助官员决定他们应拨款兴建哪些航线以使得没有出现交叉得航线最多.
输入
输入数据包括若干组,每组数据格式如下:
第一行两个由空格分隔的整数x,y, 10<=x<=6000, 10<=y<=100. x表示河的长度而y表示宽.
第二行是一个整数N(1<=N<=5000),表示分布在河两岸的城镇对数.
接下来的N行每行有两个空格分隔的正数C,D(0
30 4
5
4 5
2 4
5 2
1 3
3 1