Delivery

Interview

Time limit2sMemory limit128 MB

Summary

Find the minimum moves in a grid from a start cell to visit two target cells, forbidding two consecutive moves in the same direction.

Level: Medium6 of 10
Topics: BFS, Shortest path, Graph, Matrix
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples5

Example 1
Input
```
2 3
SCC
...
```
Expected output
```
4
```
Example 2
Input
```
1 5
C.C.S
```
Expected output
```
-1
```
Example 3
Input
```
3 3
#.#
CSC
#.#
```
Expected output
```
5
```

Example 4

Input

10 7
#.#....
##...#.
C#...#.
.....#.
..#....
..#S.#.
.##..#.
###..##
..C.#.#
###.#..

Expected output

Example 5

Input

3 36
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#C
.................S..................
C#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

Expected output