题目描述

小 Z 是一位聪明的僵尸，他打算进攻N*M个方格组成的矩形草坪，但是可恶的戴夫种植了一堆土豆地雷，如果小 Z 踩到了土豆地雷(' * ')，那么他就会爆炸。

但是小Z是一只聪明的僵尸，他不像他的兄弟们，他可是会拐弯的僵尸，但是他不能出草坪，也不能斜着走。

但是的但是：戴夫疯了，有 $300\times300$ 的草坪！

现在他想问问你，他该怎么走，才能走到门口('#')，如果能，输出最小步数，否则输出 "I can't eat brain!"。

输入格式

第一行输入由空格隔开的两个整数：n,m 表示行数和列数

接下来N行，每行输入m个字符，表示草坪，没有土豆地雷的地方为 '.' , 初始点为 'z'

输出格式

如果可以走到门口，输出最少步数（不算起点）

否则输出 'I can't eat brain!'(不带引号)

样例

3 3
.#.
***
..z

I can't eat brain!

数据范围

保证$1≤n,m≤300$