松松和小青

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

     豆豆的朋友松松和小青刚交往不久,小青就被邪恶女巫给抓走了,并被关在了一个迷宫里。在邪恶女巫睡觉的时候,松松冒险偷来了迷宫的地图,豆豆看到地图后发现,这个迷宫很特殊,迷宫是由一个个方格构成的,在迷宫里只可以向上下左右四个方向走,每走一格就花费一个单位的时间。有些方格有陷阱是不可以走的,有些方格是安全的可以走,小青就在某一个方格内,松松可以从迷宫外任意位置进入。松松想在最短的时间内找到小青并带小青离开迷宫,如果找不到的话,松松就需要再去偷邪恶女巫的飞行扫帚。

如图:

松松最少需要花费6个时间单位才能成功(路线不唯一)。

 

Input

多组数据,第一行输入两个整数N和M (N<=100&&M<=100),表示迷宫大小,然后是N行,每行M个字符,’Q’ 表示小青所在的位置,’*’ 表示可以走的地方,’#’表示陷阱。

Output

 每组输出占一行。如果可以成功,请输出最少时间,如果不能够成功,请输出 get the flying broom!

Sample Input

5 6
**#***
**#***
*#*Q**
#*###*
****#*
3 3
###
#Q#
###

Sample Output

6
get the flying broom!

Hint

 

Source

zhangjinhu