题目描述

发生了火警，所有人员需要紧急疏散！假设每个房间是一个 $n \times m$ 的矩形区域。每个格子如果是 .，那么表示这是一块空地；如果是 X，那么表示这是一面墙，如果是 D，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。

最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。

输入格式

输入文件第一行是由空格隔开的一对正整数 $n$ 与 $m$，以下 $n$ 行 $m$ 列描述一个 $n\times m$的矩阵。其中的元素可为字符 .、X 和 D，且字符间无空格。

输出格式

只有一个整数 $k$，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出 impossible。

5 5  
XXXXX
X...D
XX.XX
X..XX
XXDXX

3

数据规模与约定

对于 $100\%$ 的数据，$3\le n \le 20$，$3\le m\le 20$，

提示

2015.1.12 新加数据一组，鸣谢 1756500824。

C++ 语言请用 scanf("%s",s) 读入！