跳舞的线 - 乱拐弯

题目背景

# 线初始面对方向请自己确定 ![您可以写dp](https://cdn.luogu.com.cn/upload/pic/30733.png) 玩过了 $LCA$ 之后,Imakf 觉得甚是无聊,于是便打开了 DL。 Imakf:刺客传奇又死在 $70\%$!突然有一点弃坑的想法鸭…… Imakf 想起自己玩了 $1$ 年的 DL,卡在园林教堂混沌,肝了几个月终于过了的欣喜,却被这个刺客传奇困住,禁不住泪眼朦胧。泪眼中,他突然发现手机变成了一个一个的像素点!Imakf 非常惊喜!这样不就可以写一个程序自动通关了吗? 可是不一会,他又陷入了失望…… Imakf:我不会写啊!!

题目描述

线现在在一个地图上,它正在 $(1,1)$ 上(左上角),最终要去到 $(M,N)$ 上。它不但只能往下或往右走,还只能在整数格子上移动。 Imakf 有的时候想要炫技,又有时想偷懒,所以他会告诉你这张地图的全貌,你要告诉他到达终点的最多和最少拐弯次数。

输入输出格式

输入格式


第一行两个正整数 $M,N$,意义见题目描述。 第 $2\sim M+1$ 行,每行 $N$ 个字符。如果为 `#` 就代表这里有障碍,反之没有。

输出格式


输出两个正整数 $max,min$,$max$ 表示最多拐弯次数,$min$ 表示最少拐弯次数。 **如果到达不了就仅输出** `-1`。

输入输出样例

输入样例 #1

5 5
oooo#
ooooo
#oo#o
o#ooo
oo#oo

输出样例 #1

7 2

输入样例 #2

5 5
oooo#
ooooo
#oo##
o#o#o
oo#oo

输出样例 #2

-1

说明

样例 $1$ 说明: ![](https://cdn.luogu.com.cn/upload/pic/12623.png) 红色路线代表拐弯次数最多。 蓝色路线代表拐弯次数最少。 -------------- 样例 $2$ 说明: 显然过不去。 --- 数据范围: | 测试点 | $N$ | $M$ | | -----------: | -----------: | -----------: | | $1\sim 5$ | $\leq100$ | $\leq100$ | | $6\sim 7$ | $=200$ | 不做约定 | | $8\sim 10$ | 不做约定 |不做约定| 对于全体数据,保证 $10\le M,N\le 1000$。 感谢 @Iowa\_BattleShip 指出数据错误。