Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.
Маленький пират Серёжа скачал игру с разными видами головоломок. Среди них ему понравилась лишь одна, самая сложная.
Головоломка представляет из себя таблицу из \(n\) строк и \(m\) столбцов, в ячейках которой записаны числа от \(1\) до \(n \cdot m\) по одному разу.
Чтобы собрать головоломку, нужно выбрать последовательность клеток таблицы, в которой любые две подряд идущие клетки соседние по стороне в таблице. Последовательность может иметь произвольную длину, и каждая клетка может встречаться в последовательности произвольное число раз. Для клетки со значением \(i\) рассмотрим позицию \(t_i\) — позицию первого вхождения клетки с таким значением в последовательность. Последовательность решит головоломку, если каждая клетка таблицы встречается в ней, и \(t_1 < t_2 < \dots < t_{nm}\). Другими словами, последовательность должна в первый раз посетить клетку со значением \(x\) до клетки со значением \(x + 1\) для всех \(x\).
Назовем головоломку решаемой, если для нее существует хотя бы одна подходящая последовательность.
Серёжа понял, что не любая головоломка решаемая, так как подходящей последовательности может не существовать. Ему стало интересно, можно ли немного изменить головоломку, чтобы ее можно было решить. На это Серёже не хватило таланта, поэтому ему нужна ваша помощь.
За одно действие Сережа может выбрать две произвольных клетки (не обязательно соседние по стороне) и поменять числа, записанные в них. Он хотел бы знать минимальное число действий, которое потребуется, чтобы головоломка стала решаемой, но очень нетерпелив. Поэтому найдите, равняется ли минимальное число действий \(0\), \(1\), или же не менее \(2\). В случае, когда потребуется ровно \(1\) действие, найдите также количество подходящих пар клеток для обмена чисел.
Формат входных данных
В первой строке вводятся два целых положительных числа \(n, m\) (\(1 \leq n \cdot m \leq 400\,000\)) — длины сторон таблицы.
В каждой из следующих \(n\) строках вводятся \(m\) целых чисел \(a_{i1}, a_{i2}, \dots, a_{im}\) (\(1 \le a_{ij} \le n \cdot m\)).
Гарантируется, что каждое число от \(1\) до \(n \cdot m\) встречается ровно один раз.
Формат выходных данных
Пусть \(a\) — минимальное число действий, после которых головоломка станет решаемой.
Если \(a = 0\), выведите \(0\).
Если \(a = 1\), выведите \(1\), а также количество подходящих пар клеток.
Если \(a \ge 2\), выведите \(2\).
В первом примере из условия последовательность клеток \((1, 2), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)\), \((2, 3), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (3, 2), (3, 1)\) решает головоломку, поэтому ответ \(0\).
Головоломка во втором примере из условия не решается, но будет решаться после любого из трех обменов клеток со значениями \((1, 5), (1, 6), (2, 6)\).
В третьем примере из условия потребуется не менее двух обменов, поэтому ответ равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
2 1 3
6 7 4
9 8 5
|
0
|
|
2
|
2 3
1 6 4
3 2 5
|
1 3
|
|
3
|
1 6
1 6 5 4 3 2
|
2
|