B. Инна и новая матрица конфет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Инна очень любит сладкое и игру «Матрица конфет». Сегодня она придумала новую игру — «Матрица конфет 2: перезагрузка».

Поле для новой игры представляет собой прямоугольную таблицу размера n × m. В каждой строке этой таблицы одна клетка занята фигуркой гномика, одна клетка занята конфеткой, остальные клетки строки свободны. Игра длится несколько ходов. На каждом ходе игрок должен выбрать все строки матрицы, в которых гномики не стоят в конфетах, и крикнуть: «Побежали!». После чего все гномики в выбранных строках начинают синхронно передвигаться вправо. За одну секунду каждый гномик шагает в соседнюю клетку, которая находится правее его текущей клетки. Передвижения продолжаются до тех пор пока не случится одно из событий:

  • какой-то гномик в одной из выбранных строк находится в самой правой клетке своей строки;
  • какой-то гномик в выбранных строках находится в клетке с конфетой.

Цель игры — сделать так, чтобы все гномики находились в клетках с конфетами.

Инна — большой молодец, ведь она придумала такую интересную игру. А как же вы? Ваша задача — сыграть в эту игру оптимальным образом. А именно, по заданному игровому полю сказать, какое минимальное количество ходов потребуется игроку, чтобы добиться цели игры.

Входные данные

Первая строка входных данных содержит два целых числа n и m (1 ≤ n ≤ 1000; 2 ≤ m ≤ 1000).

Следующие n строк содержат по m символов — поле для игры в «Матрица конфет 2: перезагрузка». Символ «*» обозначает свободную клеточку поля, символ «G» — фигурку гномика, а символ «S» — конфету. Других символов матрица не содержит. Гарантируется, что каждая строка содержит ровно один символ «G» и один символ «S».

Выходные данные

В единственной строке выведите целое число — минимальное количество ходов, необходимое для достижения цели игры, либо -1, если достичь ее на данном игровом поле невозможно.

Примеры
Входные данные
3 4
*G*S
G**S
*G*S
Выходные данные
2
Входные данные
1 3
S*G
Выходные данные
-1