Лабиринт в виде прямоугольника размером m × n поделен на квадратные ячейки размером 1 × 1 прямыми, параллельными сторонам лабиринта. Каждая ячейка лабиринта или свободна, или непроходима. Можно перемещаться между свободными ячейками лабиринта, имеющими общую сторону. При этом нельзя выходить за границы лабиринта. Лабиринт устроен специальным образом: для любых двух свободных ячеек существует единственный путь из одной в другую.

Где-то в лабиринте есть две специальные ячейки, в центре каждой из которых расположен крюк. Если вы привяжете нить к крюкам в этих ячейках, автоматически откроется секретная дверь. Ваша задача — зная схему лабиринта, приготовить нить как можно меньшей длины, которой гарантированно хватит для соединения двух специальных ячеек, где бы они ни находились.

В первой строке записаны целые числа n и m (3 ≤ n, m ≤ 820). В следующих m строках описана схема лабиринта. Каждая из них содержит n символов. Каждый символ — это или "#" (обозначает непроходимую ячейку), или "." (обозначает свободную ячейку). В лабиринте не менее двух свободных ячеек.

Выведите минимально возможную необходимую длину нити, принимая за единицу измерения длину стороны ячейки.