15005 - 排座椅

上课时总会有一些同学和前后左右的人交头接耳,这一现象令班主任十分头疼。不过,班主任小哈发现了一些有趣的现象,只有有限的D对同学上课时会交头接耳。教室中座位是M行N列的,坐在第i 行第j 列的同学的位置是(i, j),为了方便同学们进出,还设置了K条横向的通道,L条纵向的通道。 
于是,小哈想到一个可以减少上课时学生交头接耳的办法:他打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了2个会交头接耳的同学,那么他们就不会交头接耳了。请你帮忙给小哈编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生的对数最少。

 

样例理解:

16548395341666.png
  • 用符号*、⋇、+ 标出了3 对会交头接耳的学生的位置 
  • 图中3 条粗线的位置表示通道,图示划分方案是唯一的最 
    佳方案

输入

第一行有5 个用空格隔开的整数,分别是M, N, K, L, D(2 ≤ N, M ≤ 1000, 0 ≤ K < M, 0 ≤ L < N, D ≤ 2000)。 
接下来的D 行,每行有4 个用空格隔开的整数。第i 行的4个整数Xi, Yi, Pi, Qi,表示坐在位置(Xi, Yi) 与(Pi, Qi) 的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。 
输入数据保证最优方案的唯一性

输出

共两行。第一行包含K 个整数a1, a2, . . . , aK,表示第a1 行和a1 + 1 行之间、第a2 行和a2 + 1 行之间、⋯ 、第aK 行和第aK + 1 行之间要开辟通道,其中ai < ai+1,每两个整数之间用空格隔开(行尾没有空格)。第二行包含L个整数b1, b2, . . . , bL,表示第b1 列和b1 + 1 列之间、第b2列和b2 + 1 列之间、⋯、第bL 列和第bL + 1 列之间要开辟通道,其中bi < bi+1,每两个整数之间用空格隔开(列尾没有空格)

样例

输入

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

输出

2
2 4
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题