Minimum Time to Electrify All Plots

You are given a grid with n rows and m columns. Each cell of the grid is one of the following:

• P: a power station
• E: an empty plot that requires electricity
• O: an obstacle that cannot be passed

The electricity from each power station spreads to its adjacent (up, down, left, right) plots in 1 unit of time. Once an empty plot receives electricity, it becomes powered and can further spread the power to its adjacent empty plots in the subsequent time units.

Your task is to determine the minimum amount of time required to cover all empty plots (E) with electricity. If it is impossible to cover all empty plots, output -1.

Note: If there are no empty plots in the grid initially, the answer is 0.

The process can be mathematically described using the following recurrence:

\(time_{next} = time_{current} + 1\)

inputFormat

The input is read from stdin and has the following format:

 n m
 row1
 row2
 ...
 row_n

Here:

• n and m are integers representing the number of rows and columns, respectively.
• Each of the following n lines contains a string of exactly m characters. Each character is either P, E, or O.

outputFormat

Output a single integer to stdout representing the minimum time required to electrify all empty plots, or -1 if it is impossible.

## sample

4 5
PEEOE
EOEEE
EEPOE
EOEEE

3