该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

To the greatest All-around King zsp！

题目描述

伟大的葫芦岛王子zsp正在上学的路上。

一天，zsp正准备从寝室走向n405。不幸的是，连绵的大雨淹没了部分道路。而优雅的zsp不愿触碰肮脏的污水，他想走一条不包含任何被淹没道路的路。于是他使用上帝视角得知了路面的全部情况，并向你询问他能否到达n405。

现在，你有一个n * m大小的矩阵(n为行数，m为列数)，其中元素的所有可能值为两种,分别为'.'、'~'(不包括引号)。其中，'.'表示未被淹没的路面，'~'表示被淹没的路面。

而zsp的寝室在矩阵左上角即(1,1)，目的地n405在右下角即(n,m)。每一时刻末，zsp能向上下左右四个方向移动一个单位（每次只能选择一个方向）。设zsp从时刻1初出发，如果没有一条路径满足其中路面都未被淹没，则无法到达n405，输出-1，否则，请输出最早能在哪个时刻末到达n405。

输入格式

第一行两个整数n,m,分别表示矩阵的行数和列数,1<=n,m<=1000。（保证n，m不同时为1）

接下来n行，每行m个字符，表示路面情况。(保证(1,1)和(n,m)为'.')

输出格式

若不存在满足条件的路径到达n405，则输出-1。

否则输出最早能在哪个时刻到达n405。

样例 #1

样例输入 #1

1 5
.....

样例输出 #1

4

样例 #2

样例输入 #2

2 4
..~.
..~.

样例输出 #2

-1

样例 #3

样例输入 #3

2 4
....
....

样例输出 #3

4

提示

对样例一,在第一时刻末到达(1,2),在第二时刻末到达(1,3),在第三时刻末到达(1,4),在第四时刻末到达(1,5)，输出4.

对样例二，无法到达(2,4)，输出-1