Inna likes sweets and a game called the "Candy Matrix". Today, she came up with the new game "Candy Matrix 2: Reload".

The field for the new game is a rectangle table of size n × m. Each line of the table contains one cell with a dwarf figurine, one cell with a candy, the other cells of the line are empty. The game lasts for several moves. During each move the player should choose all lines of the matrix where dwarf is not on the cell with candy and shout "Let's go!". After that, all the dwarves from the chosen lines start to simultaneously move to the right. During each second, each dwarf goes to the adjacent cell that is located to the right of its current cell. The movement continues until one of the following events occurs:

  some dwarf in one of the chosen lines is located in the rightmost cell of his row;  some dwarf in the chosen lines is located in the cell with the candy. 

The point of the game is to transport all the dwarves to the candy cells.

Inna is fabulous, as she came up with such an interesting game. But what about you? Your task is to play this game optimally well. Specifically, you should say by the given game field what minimum number of moves the player needs to reach the goal of the game.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n ≤ 1000; 2 ≤ m ≤ 1000). 

Next n lines each contain m characters — the game field for the "Candy Martix 2: Reload". Character "*" represents an empty cell of the field, character "G" represents a dwarf and character "S" represents a candy. The matrix doesn't contain other characters. It is guaranteed that each line contains exactly one character "G" and one character "S".


-----Output-----

In a single line print a single integer — either the minimum number of moves needed to achieve the aim of the game, or -1, if the aim cannot be achieved on the given game field.


-----Examples-----
Input
3 4
*G*S
G**S
*G*S

Output
2

Input
1 3
S*G

Output
-1

Difficulty: interview

Starter code:

Solutions:
import sys

H, W = list(map(int, input().split()))
L = set()
for y in range(H):
    row = input().strip()
    i_sweet = row.find('S')
    i_gnome = row.find('G')
    if i_sweet == -1 or i_gnome > i_sweet:
        print(-1)
        return
    L.add(i_sweet - i_gnome)
print(len(L))


#!/usr/bin/env python3

def read_ints():
	return list(map(int, input().strip().split()))

n, m = read_ints()

best = 0
opts = set()

for _ in range(n):
	x = input()
	g = x.find('G')
	s = x.find('S')

	if s<g:
		best = float('inf')
		break
	else:
		opts.add(max(best, s-g))

if best == float('inf'):
	print(-1)
else:
	print(len(opts))



n, m = map(int, input().split())
dist_w = 2001
dist_s = -1
flag = False
ans = set()
for i in range(n): 
    s = input()
    gnome = s.find("G")
    sweet = s.find("S")
    if gnome > sweet:
        flag = True
        break
    ans.add(sweet - gnome)
if flag:
    print(-1)
else:
    print(len(ans))

n, m = map(int, input().split())
c = 0
g = 0
t = set()
f = False
for i in range(n):
    s = input().strip()
    for j in range(len(s)):
        if s[j] == 'G':
            g = j
        elif s[j] == 'S':
            c = j
    if g - c > 0:
        print(-1)
        f = True
        break
    t.add(c - g)
if not f:
    print(len(t))

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n, m = list(map(int, input().split(' ')))
distances = [0] * 1000

for l in [input() for _ in range(n)]:
    distance = l.index('S') - l.index('G')
    if distance < 0:
        print(-1)
        return
    distances[distance] = 1

print(distances.count(1))


N = 1000
dis = set([])
n, m = list(map(int, input().split(' ')))
f = False
for i in range(n):
    s = input()
    dist = s.index('S') - s.index('G')
    #print(dist)
    if dist < 0:
        f = True
        break
    if dist not in dis:
        dis.add(dist)
if f:
    print(-1)
else:
    print(len(dis))


def dist(s):
  return s.find("S") - s.find("G") - 1

a, b = map(int, input().split())
dists = [dist(input()) for i in range(a)]
if min(dists) < 0:
  print(-1)
else:
  print(len(set(dists)))

n, m = list(map(int, input().split()))
d = [0] * m
for i in range(n):
    t = input()
    d[t[t.find('G') + 1: ].find('S')] = 1
if d[-1]: print(-1)
else: print(sum(d))


import sys

try:
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
except:
    pass

n, m = (int(i) for i in input().split())
str = [input() for i in range(0, n)]
arr = []
for i in range(0, n):
    t1, t2 = 0, 0
    for j in range(0, m):
        if str[i][j] == 'G':
            t1 = j
        elif str[i][j] == 'S':
            t2 = j
    if t1 > t2:
        print(-1)
        return
    if t1 < t2:
        arr.append(t2 - t1)
arr.sort()
answer = 0
if (len(arr) > 0):
    answer += 1
for i in range(1, len(arr)):
    if arr[i] != arr[i - 1]:
        answer += 1
print(answer)

h, w = list(map(int, input().split()))

ans = set()
good = True
for i in range(h):
    s = input()
    pg = -1
    ps = -1
    for j in range(w):
        if s[j] == 'G':
            pg = j
        elif s[j] == 'S':
            ps = j
    if ps < pg:
        good = False
    ans.add(ps - pg)
    
if not good:
    print(-1)
else:
    print(len(ans))


n,m=list(map(int,input().split()))

li=[0]*1002
for i in range(0,n):
    a=input()
    pG=0
    pS=0
    for j in range(0,m):
        if a[j]=='G':
            pG=j
        elif a[j]=='S':
            pS=j
    if pS<pG:
        print(-1)
        break
    li[pS-pG]=1;
else:
    ans=0
    for i in range(1,1002):
        ans+=li[i]
    print(ans)
    


n, m = map(int, input().split())
c = set(s.find("S") - s.find("G") for s in (input() for _ in range(n)))
if all(a >= 0 for a in c):
  c.discard(0)
  print(len(c))
else:
  print(-1)

n, m = map(int, input().split())
c = set(s.find("S") - s.find("G") for s in (input() for _ in range(n)))
print(-1 if any(a < 0 for a in c) else len(c))

ds = set()
n, m = map(int, input().split())
for i in range(n):
    r = input()
    d = r.index('S') - r.index('G')
    if d < 0:
        print(-1)
        return
    ds.add(d)
print(len(ds))

n, m = (int(x) for x in input().split())
st = set()
for i in range(n):
	s = input()
	g = s.index('G')
	s = s.index('S')
	if g > s:
		print(-1)
		return
	st.add(s - g)
print(len(st))


def main():
    n, _ = list(map(int, input().split()))
    res = set()
    for _ in range(n):
        a = input()
        s, g = a.find("S"), a.find("G")
        if s < g:
            print(-1)
            return
        res.add(s - g)
    print(len(res))


def __starting_point():
    main()

__starting_point()

s=set()
n,m=input().split(" ")
n=int(n)
m=int(m)
for i in range(n):
    test=input()
    if(test.find("S")-test.find("G")<0):
        print(-1)
        return
        break
    else:
        s.add(int(test.find('S')-test.find("G")))
print(len(s))

'''
Created on 27.4.2016

@author: Ivan
'''
import sys
def main():
    line = input()
    parts = line.split(" ")
    a = int(parts[0])
    b = int(parts[1])
    list = []
    for i in range(0, a):
        list.append(input())
    pairs = []
    res = 0
    for l in list:
        x = l.find("G")
        y = l.find("S")
        print()
        if y < x:
            print("-1")
            return
        pairs.append((y - x))
    pairs = set(pairs)
    print(str(len(pairs)))
def __starting_point():
    main()
__starting_point()

n,m=list(map(int,input().split()))
sol=True
dst=set()
for _ in range(n):
  l=input()
  g=s=0
  for j in range(m):
    if l[j]=='G':
      g=j
    if l[j]=='S':
      s=j
  if s<g:
    sol=False
  else:
    dst.add(g-s)
print(len(dst) if sol else -1)


n,m=list(map(int,input().split()))
dst=set()
for _ in range(n):
  l=input()
  s=l.find('S')
  g=l.find('G')
  if s<g:
    print(-1)
    return
  else:
    dst.add(g-s)
print(len(dst))


n, m = list(map(int, input().split()))
bad = False
d = set()
for i in range(n):
  inp = list(input())
  s = inp.index("S")
  g = inp.index("G")
  if s < g:
    bad = True
  else:
    d.add(s - g)

if bad:
  print(-1)
else:
  print(len(d))


n,m=list(map(int,input().split()))
s=[]
for i in range(n):
	p=input()
	for i in range(len(p)):
		if p[i]=='G':
			x=i
		elif p[i]=='S':
			y=i
	s.append([x,y])
ans=0
p=[]
for i in s:
	if i[0]>i[1]:
		print(-1)
		return
	elif i[0]<i[1]:
		p.append(i[1]-i[0])
t=0
p=set(p)
print(len(p)) 


n, m = map(int, input().split())
c = set(s.find("S") - s.find("G") for s in (input() for _ in range(n)))
print(-1 if any(a < 0 for a in c) else len(c))

import math
def solution():
	n,m = [int(x) for x in input().split(' ')]
	matrix = []
	s = []
	for i in range(n):
		line = list(input())
		matrix.append(line)
		coo = line.index('S') - line.index('G')
		if coo<0:
			return -1
		s.append(coo)
	s = set(s)
	return len(s)

print(solution())

n, m = map(int, input().split())

distances_map = {}
num_distances = 0

for i in range(n):
  line = input()
  indexG = 0
  indexS = 0
  for j in range(len(line)):
    if (line[j] == "G"):
      indexG = j
    elif (line[j] == "S"):
      indexS = j

  dist = indexS - indexG
  if (dist < 0):
    num_distances = -1
    break
  elif (dist not in distances_map):
    distances_map[dist] = 1
    num_distances += 1

print (num_distances)