Light All Bonfires

You are given a grid representing an island. Each cell in the grid is one of the following characters:

• S denotes the starting position.
• F denotes a bonfire that needs to be lit.
• . denotes an open space.
• # denotes an obstacle that cannot be passed.

From the starting position, you must move in one of the four cardinal directions (up, down, left, right) at each step. When you visit a cell containing a bonfire, it is instantly lit. The goal is to determine the minimum number of steps required so that all bonfires are lit. If it is impossible to reach some bonfires, output \(-1\).

Note: Although a single traveler cannot split, the process is modeled as a simultaneous wave propagation (i.e. a breadth-first search). In other words, the answer is equal to the maximum distance from the start position \(S\) to any reachable bonfire \(F\), if all bonfires are reachable.

Formally, if we denote the grid as a matrix \(G\) of size \(n \times m\), and let the Manhattan distance from the starting position \(S\) to a cell \((i,j)\) be \(d(i,j)\), then the answer is:

\[ \text{answer} = \max_{(i,j) \; \text{where} \; G(i,j) = F} d(i,j), \]

provided all bonfire cells are reachable; otherwise, output -1.

inputFormat

The input consists of multiple test cases. For each test case:

1. The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 1000\)) representing the number of rows and columns of the grid.
2. The next \(n\) lines each contain a string of length \(m\) representing a row of the grid.

A test case with 0 0 indicates the end of input and should not be processed.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single integer on a separate line: the minimum number of steps required to light all bonfires, or \(-1\) if not all bonfires are reachable.

Output is written to standard output (stdout).

## sample

3 3
S.F
.#.
..F
0 0

4