0x00基本算法（0x05 排序）例题3：七夕祭

P10453 七夕祭

题目描述

给出一个 $N \times M$ 的01矩阵。其中有 T 个位置为 1 ，其余为 0。

为了使得每一行的 1 一样多 ，并且每一列的 1 也一样多，可以多次交换任意两个相邻的位置的值（上下或左右，每一行或每一列的第一个位置和最后一个位置也算作相邻）。

求每一行和每一列的 1 一样多这两个要求能满足多少个？ 在此前提下，至少需要交换多少次摊点。

输入格式

第一行三个整数 $N 、M、T$。

下来 $T$ 行，每行两个整数 $x, y$，表示 在第 $x$ 行第 $y$ 列的值为 1。

输出格式

首先输出一个字符串。

如果能满足全部两个要求，输出 both；

如果通过调整只能使得各行中 1 一样多，输出 row；

如果只能使各列中 1 一样多，输出 column；

如果均不能满足，输出 impossible。

如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

输入输出样例 #1

输入 #1

2 3 4
1 3
2 1
2 2
2 3

输出 #1

row 1

输入输出样例 #2

输入 #2

3 3 3
1 3
2 2
2 3

输出 #2

both 2

说明/提示

对于 $30\%$ 的数据，$N,M \le 100$。

对于 $70\%$ 的数据，$N,M \le 1000$。

对于 $100\%$ 的数据，$1 \le N,M \le 100000$，$0 \le T \le \min(N\times M,100000)$，$1 \le x \le N$，$1 \le y \le M$。