贪心 · 例4-排座椅
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 50 M，其他语言100 M
64bit IO Format: %lld

题目描述

\hspace{15pt}教室内共有 n 行 m 列座位，坐在第 i 行第 j 列同学的位置记为 (i,j)。

\hspace{15pt}为了方便进出，班主任计划设置 k 条横向通道（贯穿整列的水平通道）与 l 条纵向通道（贯穿整行的竖直通道）。通道位于相邻两行（或两列）之间。

\hspace{15pt}班主任记录了 d 对经常交头接耳的同学，他们的位置 (x_i,y_i) 与 (p_i,q_i) 保证相邻（上下或左右）。她希望通过合理放置通道，使尽可能多的"交头接耳"对被通道隔开。

\hspace{15pt}现请你输出唯一的最优方案，在该方案下，仍未被通道隔开的"交头接耳"对的数量最少。

输入描述:

\hspace{15pt}第一行输入五个整数 n,m,k,l,d\left(2\leqq n,m\leqq 10^3;\ 0<k<n;\ 0<l<m;\ 0< d \leqq 2\times\min\{n\times m,2\times10^3\}\right)。

\hspace{15pt}接下来 d 行，每行输入四个整数 x_i,y_i,p_i,q_i，表示坐标 (x_i,y_i) 与 (p_i,q_i) 的两位同学会交头接耳，且两坐标上下相邻或左右相邻。

\hspace{15pt}保证最优方案存在且唯一。

输出描述:

\hspace{15pt}第一行输出 k 个严格递增的整数 a_1,a_2,\dots,a_k\left(1\leqq a_1<\dots<a_k\leqq n-1\right)，在行 a_i 与 a_i+1 之间设置横向通道。

\hspace{15pt}第二行输出 l 个严格递增的整数 b_1,b_2,\dots,b_l\left(1\leqq b_1<\dots<b_l\leqq m-1\right)，在列 b_i 与 b_i+1 之间设置纵向通道。
示例1

输入

复制 
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

输出

复制 
2
2 4

说明

\hspace{15pt}该样例如下图所示，蓝底斜线方格为第一对交头接耳的同学，绿底带叉方格为第二对交头接耳的同学，粉底带星方格为第三对交头接耳的同学。粗线代表通道。该划分方案为唯一最优方案。

示例2

输入

复制 
2 2 1 1 4
1 1 1 2
1 1 2 1
2 1 2 2
1 2 2 2

输出

复制 
1
1