Delivery

Minsik wants to deliver packed gifts to two places inside a classroom. The classroom is a rectangular grid with N rows and M columns, and every cell is a square of the same size.

The map uses the following characters.

• S: Minsik's starting cell. There is exactly one such cell.
• C: A cell where a gift must be delivered. There are exactly two such cells.
• #: A cell that cannot be entered.
• .: A cell that can be entered freely.

In one minute, Minsik can move one cell up, down, left, or right, and he cannot leave the classroom. When he enters a C cell, the delivery at that cell is completed immediately and takes no extra time.

Every minute, Minsik must move in a direction different from the direction of his previous move. Therefore, he cannot move in the same direction twice in a row. Find the minimum time needed to visit both C cells.

The first line contains the classroom height N and width M. Both N and M are positive integers not greater than 50.

The next N lines contain the classroom map.

Print the minimum time needed to visit both delivery locations. If it is impossible, print -1.