Escape

Time limit1sMemory limit128 MB

Summary

Given a grid with rocks, spreading flood water, a start and a den, compute the minimum time for the hedgehog to reach the den using multi-source BFS for water and BFS for the hedgehog while comparing arrival times.

Level: Medium5 of 10
Topics: BFS, Matrix, Simulation
Solved: No attempts yet

Problem

A flood has started in a forest. A hedgehog lives there and wants to escape as quickly as possible to the beaver's den.

The forest map is an R by C grid. An empty cell is written as ., a flooded cell as *, and a rock as X. The beaver's den is D, and the hedgehog's starting position is S.

Each minute, the hedgehog may move to one of the four cells sharing an edge with its current cell. Water also spreads every minute into adjacent empty cells. Neither the hedgehog nor water can pass through rocks, and water never enters the beaver's den.

The hedgehog cannot move into a cell that is already flooded, and it also cannot move into a cell that will flood at the next minute. If it did, it would be caught by the water as it arrived.

Given the map, find the minimum time needed for the hedgehog to reach the beaver's den safely.

Input

The first line contains two positive integers R and C. Both values are at most 50.

Each of the next R lines contains the forest map. Only the characters described above appear in the map, and D and S each appear exactly once.

Output

Print the earliest time at which the hedgehog can reach the beaver's den. If it cannot reach the den safely, print KAKTUS.

Examples4

Example 1
Input
```
3 3
D.*
...
.S.
```
Expected output
```
3
```
Example 2
Input
```
3 3
D.*
...
..S
```
Expected output
```
KAKTUS
```
Example 3
Input
```
3 6
D...*.
.X.X..
....S.
```
Expected output
```
6
```
Example 4
Input
```
5 4
.D.*
....
..X.
S.*.
....
```
Expected output
```
4
```