Prison Break

There is an N by M prison. Each cell is either a wall (X), an empty cell (.), or an exit (D). Every empty cell initially contains exactly one person. Every person must move to one of the exits and leave the prison.

Moving one cell up, down, left, or right takes 1 second. A single exit can let at most one person leave during each second. While people are moving, multiple people may occupy the same empty cell at the same time.

Given the prison map, find the minimum time needed for everyone to escape. The border of the prison is always made of walls or exits, and there are no exits in the interior. There may be no exits, and there is at least one empty cell.

The first line contains two integers N and M, the number of rows and columns of the prison.

Each of the next N lines contains the prison map. X means a wall, . means an empty cell, and D means an exit.

Print the minimum time needed for everyone to escape. If it is impossible for everyone to escape, print impossible.

• 3 <= N, M <= 12