Chell's Portal Puzzle

Chell is trapped in a puzzling room represented by an N×M matrix. Each cell is one of the following:

• A wall (denoted as #).
• The starting cell, where Chell is initially located (denoted as C).
• The finish cell, that Chell must reach to solve the puzzle (denoted as F).
• An empty cell (denoted as .).

Chell has a portal gun that can create portals on walls. In each move she can:

• Move to an adjacent non‐wall cell in one of the four directions (up, down, left, right). This move costs 1 unit of time.
• Create a new portal by shooting in one of the four directions. The shot travels until it hits a wall. When it does, a portal is created on the side of the wall being hit. Specifically, if she shoots in direction \(\vec d\), the portal is created on the wall cell at the point of impact with side \(-\vec d\). This move costs 0 time. At any moment, at most \(2\) portals can be active. If a new portal is created when 2 are already active, the older portal disappears. Also, it is not allowed to create a portal on a wall side that already has an active portal.
• If exactly 2 portals are active and Chell is in a cell adjacent to a wall that has a portal on the side facing her, she can step into the portal. She will exit from the cell which is adjacent to the other portal (in the direction indicated by that portal). This portal jump costs 1 unit of time and is only possible if the exit cell is not obstructed.

The room is always surrounded by walls, and there is exactly one C and one F in the grid. Your task is to determine the minimal amount of time needed for Chell to reach the finish cell.

inputFormat

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

This is followed by N lines, each containing M characters. Each character is one of: #, C, F, or ..

outputFormat

Output a single integer: the minimal time (in units) needed for Chell to reach the finish cell.

sample

5 5
#####
#C..#
#.#F#
#...#
#####

3