Вам задана прямоугольная таблица из \(n\) строк и \(m\) столбцов. Некоторые ее клетки покрашены в черный цвет, остальные — белые.
За одну операцию вы выбираете некоторую черную клетку и выполняете ровно один пункт из следующих:
- красите все клетки в ее строке в черный цвет, или
- красите все клетки в ее столбце в черный цвет.
Вам заданы два целых числа \(r\) и \(c\). Найдите минимальное количество операций, чтобы сделать клетку в \(r\)-й строке \(c\)-м столбце черной, или определите, что это невозможно.
Выходные данные
Для каждого набора входных данных, если невозможно сделать клетку в \(r\)-й строке \(c\)-м столбце черной, выведите \(-1\).
В противном случае выведите одно целое число — минимальное количество операций, необходимое для того, чтобы сделать клетку в строке \(r\) столбце \(c\) черной.
Примечание
Изображение первого набора входных данных представлено ниже.
В первом наборе входных данных мы можем выбрать черную клетку в строке \(1\) столбце \(2\) и сделать все клетки в ее строке черными. Таким образом, клетка в строке \(1\) столбце \(4\) станет черной.
Во втором наборе входных данных примера клетка в строке \(2\) столбце \(1\) уже черная.
В третьем наборе входных данных примера невозможно сделать клетку в строке \(2\) столбце \(2\) чёрной.
Изображение четвертого набора входных данных представлено ниже.
В четвертом наборе входных данных мы можем выбрать черную клетку в строке \(2\) столбце \(2\) и сделать черными все клетки столбца.
После этого мы можем выбрать клетку в строке \(1\) столбце \(2\) и сделать сделать всю ее строку черной.
Таким образом, клетка в строке \(1\) столбце \(1\) станет черной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
3 5 1 4
WBWWW
BBBWB
WWBBB
4 3 2 1
BWW
BBW
WBB
WWB
2 3 2 2
WWW
WWW
2 2 1 1
WW
WB
5 9 5 9
WWWWWWWWW
WBWBWBBBW
WBBBWWBWW
WBWBWBBBW
WWWWWWWWW
1 1 1 1
B
1 1 1 1
W
1 2 1 1
WB
2 1 1 1
W
B
|
1
0
-1
2
2
0
-1
1
1
|