Маленький пират Сережа недавно ограбил торговое судно с головоломками разных видов. Среди них ему понравилась лишь одна, самая сложная.
Головоломка представляет из себя таблицу из \(n\) строк и \(m\) столбцов, в клетках которой записаны числа от \(1\) до \(n \cdot m\) по одному разу.
Чтобы решить головоломку, нужно найти последовательность клеток таблицы, в которой любые две последовательные клетки соседние по стороне в таблице. Последовательность может иметь произвольную длину и должна посещать каждую клетку один или более раз. Для клетки со значением \(i\) обозначим за \(t_i\) позицию первого вхождения клетки с этим значением в последовательность. Последовательность решает головоломку, если \(t_1 < t_2 < \dots < t_{nm}\). Другими словами, последовательность должна в первый раз посетить клетку со значением \(x\) до клетки со значением \(x + 1\) для всех \(x\).
Назовем головоломку решаемой, если для нее существует хотя бы одна подходящая последовательность.
За одно действие Сережа может выбрать две произвольных клетки (не обязательно соседние по стороне) и поменять числа, записанные в них. Он хотел бы знать минимальное число действий, необходимое, чтобы сделать головоломку решаемой, но очень нетерпелив. Поэтому найдите, равняется ли минимальное число действий \(0\), \(1\), или же не менее \(2\). В случае, когда потребуется ровно \(1\) действие, найдите также количество подходящих пар клеток для обмена чисел.
Выходные данные
Пусть \(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
|