본섬 일주 항로

농부 John이 자신만의 크루즈 항로 사업을 시작하기로 했습니다! 지금은 배가 한 척뿐이지만, 큰 성장을 꿈꾸고 있습니다. 그는 최근에 배가 운항할 바다 구역의 지도를 얻었습니다. 지도는 아래 그림과 같으며, 높이는 $H$ ($3 \le H \le 1000$), 너비는 $W$ ($3 \le W \le 1000$) 입니다.

       ...................
       ...................
       .....A.............
       .....A..x..........
       ..x..A.....AAAA....
       .....A.....A..A....
       .....AAAAAAAA.A....
       ........A.....A....
       .xx...AAA...x.A....
       ......A............
       ...AAAAAAAAAAAAA...
       ...................

이 지도에서 . 는 바다, A 는 본섬을 이루는 칸, x 는 다른 섬에 속하는 칸을 나타냅니다.

John은 배가 본섬을 한 바퀴 완전히 돌도록 항로를 정하려고 합니다. 그런데 무역 제한 때문에, 배의 항로는 다른 어떤 섬도 둘러싸서는 안 됩니다. 예를 들어 아래의 길이 50짜리 항로는 x 로 표시된 섬을 둘러싸므로 허용되지 않습니다.

       ...................
       ....+--+...........
       ....|A.|...........
       ....|A.|x.+-----+..
       ..x.|A.+--+AAAA.|..
       ....|A.....A..A.|..
       ....|AAAAAAAA.A.|..
       ....|...A.....A.|..
       .xx.|.AAA...x.A.|..    <--- route circumnavigates 'x' -- illegal!
       ..+-+.A.........|..
       ..|AAAAAAAAAAAAA|..
       ..+-------------+..

지도가 주어질 때, 배가 다른 어떤 섬도 둘러싸지 않으면서 본섬을 한 바퀴 도는 가장 짧은 항로의 길이를 구하세요.

두 칸은 상하좌우로 바로 맞닿아 있을 때에만 인접한 것으로 봅니다(대각선은 인접하지 않습니다). 본섬은 항상 하나로 연결되어 있으며, 조건을 만족하는 항로가 반드시 존재함이 보장됩니다.

항로는 같은 칸을 두 번 이상 지날 수 있습니다. 예를 들어 위 지도의 최적 항로는 길이가 62이며, 세 칸을 다시 지납니다.

       ...................
       ....+--+...........
       ....|A.|...........
       ....|A.|x.+----+...
       ..x.|A.+--+AAAA|...
       ....|A.....A..A|...
       ....|AAAAAAAA.A|...
       ....|...A..+-+A|...
       .xx.|.AAA..|x|A|...
       ..+-+.A....+-+-++..
       ..|AAAAAAAAAAAAA|..
       ..+-------------+..

항로가 스스로 겹쳐서 위 그림은 알아보기 어렵습니다. 그래서 아래에 두 단계로 나누어 다시 그렸습니다.

       ...................            ...................
       ...................            ....+--+...........
       .....A.............            ....|A.|...........
       .....A..x..........            ....|A.|x.+----+...
       ..x..A.....AAAA....            ..x.|A.+--+AAAA|...
       .....A.....A..A....  and then  ....|A.....A..A|...
       .....AAAAAAAA.A....            ....|AAAAAAAA.A|...
       ....V...A..+>.A....            ....V...A...>+A|...
       .xx.|.AAA..|x.A....            .xx...AAA...x|A|...
       ..+-+.A....+----+..            .....A.......+-+...
       ..|AAAAAAAAAAAAA|..            ...AAAAAAAAAAAAA...
       ..+-------------+..            ...................

• 1번째 줄: 공백으로 구분된 두 정수 $H$ 와 $W$.
• 2번째 줄부터 $H+1$번째 줄까지: $i+1$번째 줄에는 지도의 $i$번째 행을 나타내는 $W$개의 문자가 주어집니다(각 문자는 ., x, A 중 하나).

• 1번째 줄: 배가 택할 수 있는 항로의 최소 길이.