Minimum Moves to Reach End

You are given a grid with M rows and N columns. Each cell of the grid is either empty (E) or blocked (O). Starting from the top-left cell (position (1,1)), you can only move either right or down. Your task is to determine the minimum number of moves required to reach the bottom-right cell (position (M,N)).

If either the starting cell or the ending cell is blocked, or if there is no valid path to reach the destination using only rightward and downward moves, output -1.

The moves count is the number of steps taken. If the grid consists of a single cell (1,1) and it is empty, then 0 moves are required.

The movement can be mathematically described as follows: Let \( (i,j) \) denote the current cell and the available moves are to \( (i+1,j) \) and \( (i,j+1) \). Determine the minimum \( k \) such that a valid sequence of moves leads from \( (1,1) \) to \( (M,N) \).

inputFormat

The first line of input contains two space-separated integers M and N, denoting the number of rows and columns respectively.

This is followed by M lines where each line is a string of length N consisting of characters E (empty) and O (obstacle).

outputFormat

Output a single integer which is the minimum number of moves required to reach the bottom-right cell from the top-left cell. If it is impossible, output -1.

## sample

3 4
EEEE
EEOE
EEEE

5

</p>