题目描述

$Bob$ 梦想成真，当了一名消防员。今天接到一项“营救”任务，在一个 $h \times w$ 网格的区域营救 $num(num=1,2)$ 个人。

网格区域是由 '.' , '#' , '*' 构成的，共 $h$ 行 $w$ 列，需要营救的人的位置是 '$'。

其中： '.' 表示空格，可以自由走动。'#' 是门，但需要暴力破门。'*' 是墙，无法通过。'$' 表示要营救的人，当然营救的位置没有门，也没有墙。

网格区域四周都可以自由进入，'.' 是空格，可以自由出入的，'#' 的位置需要暴力破门，$Bob$ 的想知道至少需要暴力打开几扇门才能将 其中 $num$ 个人全部救出，当然此次营救任务比较简单，$num =1$ 或 $2$. （门暴力打来一次后，门就永久打开了）

当然如果无法完成营救任务，也就是无法将 $num$ 个人全部救出，输出 "impossible"

输入格式

第一行，两个整数 $h$ 和 $w$

接下来 $h$ 行，每行 $w$ 个字符（由‘.’，‘#’，‘*’，‘$’）构成。

输出格式

一个整数，表示将全部人营救出来，需要最少暴力破门的次数。

5 5
##*##
#####
##$#*
#####
##.##

1

5 5
##*##
##*##
#*$**
##*##
##.##

impossible

5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********

4

5 9
****#****
*..#.#..*
****.****
*$#.#.*$*
*********

impossible

5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*

0

9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********

9

样例6解释

营救路线如下图：

数据规模与约定

$subtask1 : 1\leq h,w \leq 100,num=1$ , $50$分；

$subtask2: 1\leq h,w \leq 100, num \in \{1,2 \}$ , $50$分；