Description:


给出一个 \(R\times C\) 的矩阵,其中有N个敌人,你可以一次清除一行的敌人或者一列的敌人,求最小的清除次数,以及分别在哪几行和哪几列清除。

Input:


输入文件包含几个测试样例。
每个测试用例的第一行包含3个整数:
表示矩阵大小的R(0 \<R \<1001),C(0 \<C \<1001)和敌人数N(0 \<N \<1000001)
之后,有N行,每行包含2个表示位置的整数表示该位置有一个敌人。
每个测试用例后跟一个新行(除了最后一行)。当R = C = N = 0时终止。

Output:


对于每个测试样例,首先打印最少清除次数m。
然后打印m个位置,可以清除那几行和那几列。
对于行打印'r'后跟行号,对于列打印'c'后跟列号。
如果有多个解决方案,任何一个都被接受。

Sample Input:


Sample Output:


题解:


这道题建模想到了还是挺好做的。
我们对于每一行建一个节点表示,每一列建一个节点表示。
当(u, v)有一个敌人时,我们对于行节点u连一条到列节点v的边。

题目即求二分图的最小点覆盖,转化为二分图最大匹配。
然后从为匹配列节点dfs一遍,求得哪一些点是最小点覆盖中的点。

两次dfs完全可以合成一次,因为懒,就不改了~~~