Имеется прямоугольный лабиринт размером \(n\times m\). Обозначим \((r,c)\) как клетку в \(r\)-й строке сверху и \(c\)-м столбце слева. Две клетки называются соседними, если они имеют общую сторону. Путь — это последовательность пустых клеток, в которой любые две подряд идущие клетки являются соседними.
Каждая клетка изначально пуста. Li Hua может выбрать несколько клеток (кроме \((x_1, y_1)\) и \((x_2, y_2)\)) и поместить в каждую из них препятствие. Он хочет узнать минимальное количество препятствий, которые нужно поставить, чтобы не существовало пути из \((x_1, y_1)\) в \((x_2, y_2)\).
Предположим, что вы Li Hua. Пожалуйста, решите эту задачу.
Выходные данные
Для каждого набора входных данных выведите минимальное количество препятствий, которое нужно поставить на поле, чтобы не существовало пути из \((x_1, y_1)\) в \((x_2, y_2)\).
Примечание
В первом наборе входных данных можно поставить препятствия на \((1,3), (2,3), (3,2), (4,2)\). Тогда путь из \((2,2)\) в \((3,3)\) не будет существовать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6
|
4
2
3
|