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

Source: codeforces | Difficulty: EASY
Tags: Implementation

Complete search


Solutions:
(n, m) = 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
(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))


(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)
		exit(0)
	st.add(s - g)
print(len(st))


(n, m) = map(int, input().split(' '))
a = set()
tag = True
for i in range(n):
	x = input()
	indexG = x.index('G')
	indexS = x.index('S')
	if indexS < indexG:
		print(-1)
		tag = False
		break
	else:
		a.add(indexS - indexG)
if tag:
	print(len(a))
else:
	pass


(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append(input())
(l1, l2, ansl) = ([], [], [])
for i in range(n):
	l1.append(l[i].index('G'))
	l2.append(l[i].index('S'))
ans = -1
for i in range(n):
	if l1[i] < l2[i]:
		ansl.append(l2[i] - l1[i] - 1)
		ans = max(ans, l2[i] - l1[i] - 1)
	elif l1[i] > l2[i]:
		ansl.append(-1)
if -1 in ansl:
	print(-1)
else:
	print(len(set(ansl)))


(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))


from collections import Counter
(n, m) = map(int, input().split())
can_happen = True
dist = [0] * n
max_dist = 0
for i in range(n):
	strr = input()
	g = strr.index('G')
	s = strr.index('S')
	if g > s:
		can_happen = False
	dist[i] = s - g
counter = Counter(dist)
print(len(counter) if can_happen else -1)


(lines, columns) = map(int, input().split())
lines_info = []
while lines > 0:
	line = input()
	gnome = line.index('G')
	sweet = line.index('S')
	if sweet - gnome <= 0:
		print(-1)
		exit(0)
	lines_info.append([gnome, sweet])
	lines -= 1
count = 0
while lines_info:
	min_different = 9999
	for line_info in lines_info:
		if line_info[1] - line_info[0] < min_different:
			min_different = line_info[1] - line_info[0]
	del_indexes = []
	for i in range(len(lines_info)):
		lines_info[i][0] += min_different
		if lines_info[i][0] == lines_info[i][1]:
			del_indexes.append(i - len(del_indexes))
	for i in del_indexes:
		del lines_info[i]
	count += 1
print(count)


from itertools import product
from math import ceil, gcd, sqrt
import string
from decimal import Decimal

def binary_table(string_with_all_characters, length_to_make):
	return [''.join(x) for x in product(string_with_all_characters, repeat=length_to_make)]

def all_possible_substrings(string):
	return [int(string[i:j]) for i in range(len(string)) for j in range(i + 1, len(string) + 1)]

def number_of_substrings(length):
	return int(length * (length + 1) / 2)
(height, width) = map(int, input().split())
gnomes_positions = []
val = []
num = 0
for i in range(height):
	inp = input()
	gnome_pos = inp.index('G')
	candy_pos = inp.index('S')
	if gnome_pos > candy_pos:
		print(-1)
		exit()
	gnomes_positions.append([gnome_pos, candy_pos])
while True:
	pos = [0] * len(gnomes_positions)
	cur = False
	for i in range(len(gnomes_positions)):
		poss_ = gnomes_positions[i][0] == gnomes_positions[i][1]
		if poss_:
			pos[i] = 1
			continue
		gnomes_positions[i][0] += 1
		poss_ = gnomes_positions[i][0] == gnomes_positions[i][1]
		if poss_ and (not cur):
			num += 1
			pos[i] = 1
			cur = True
	if set(pos) == {1}:
		break
print(num)


(n, m) = map(int, input().split())
diffs = set()
for _ in range(n):
	line = input()
	diff = line.find('S') - line.find('G')
	if diff < 0:
		print(-1)
		exit()
	diffs.add(diff)
print(len(diffs))


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(a, b) = r()
arr = [input() for _ in ' ' * a]
x = set()
for i in arr:
	(a, b) = (i.index('G'), i.index('S'))
	if b < a:
		print(-1)
		exit()
	x.add(b - a)
print(len(x))


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


(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())
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) = 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) = list(map(int, input().split()))
a = []
ans = set()
for i in range(n):
	a.append(input())
	ind_G = a[i].index('G')
	ind_S = a[i].index('S')
	if ind_S < ind_G:
		print(-1)
		exit()
	ans.add(ind_S - ind_G)
print(len(ans))


(n, m) = map(int, input().split())
st = set()
for i in range(n):
	s = input()
	st.add(s.find('S') - s.find('G'))
print(-1 if any((a < 0 for a in st)) else len(st))


(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))


def main():
	(n, _) = 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))
main()


(n, m) = [int(y) for y in input().split()]
a = set()
found = False
for _ in range(n):
	s = input()
	for i in range(m):
		if s[i] == 'G':
			g = i
		if s[i] == 'S':
			c = i
	if c < g:
		print(-1)
		found = True
		break
	else:
		a.add(c - g)
if not found:
	print(len(a))


(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)
		exit(0)
	elif i[0] < i[1]:
		p.append(i[1] - i[0])
t = 0
p = set(p)
print(len(p))


def get_dis(row):
	dwarf = row.index('G')
	candy = row.index('S')
	if dwarf > candy:
		return False
	return True

def solve():
	(n, m) = map(int, input().split())
	field = []
	ans = True
	for _ in range(n):
		tmp = input()
		dwarf = tmp.index('G')
		candy = tmp.index('S')
		if dwarf > candy:
			ans = False
		if candy - dwarf not in field:
			field.append(candy - dwarf)
	if ans:
		print(len(field))
	else:
		print(-1)
solve()


from sys import stdin

def get_ints():
	return list(map(int, stdin.readline().strip().split()))
(n, m) = get_ints()
arr = []
dists = set()
mx = 0
for _ in range(n):
	x = input()
	arr.append(x)
	dis = x.find('S') - x.find('G')
	if dis < 0:
		print(-1)
		exit()
	dists.add(dis)
print(len(dists))


dic = {}
(n, m) = list(map(int, input().split()))
for i in range(n):
	s = list(input())
	G = s.index('G')
	S = s.index('S')
	distance = S - G
	if distance < 0:
		print(-1)
		exit()
	else:
		dic[distance] = None
print(len(dic))


(n, m) = map(int, input().split())
a = []
r = set()
for l in range(n):
	s = input()[:m]
	a.append(list(s))
f = 0
z = 0
for k in range(n):
	x1 = a[k].index('G')
	x2 = a[k].index('S')
	if x2 > x1:
		f = x2 - x1
		r.add(f)
		z = 1
	else:
		z = 0
		break
if z == 0:
	print(-1)
else:
	print(len(r))


(n, m) = map(int, input().split())
r = []
for i in range(n):
	a = list(input())
	fg = 0
	d = 0
	for j in range(m):
		if a[j] == 'G':
			fg = j + 1
		elif fg == 0 and a[j] == 'S':
			fg = -1
			break
		elif fg != 0 and a[j] == 'S':
			d += 1
			break
		elif fg != 0:
			d += 1
	if fg == -1:
		print(-1)
		break
	r.append(d)
if fg != -1:
	print(len(set(r)))


(n, m) = map(int, input().split())
dp = []
for i in range(n):
	x = input()
	dp.append(x)
ans = -1
l = 0
d = set()
for i in range(n):
	for j in range(m):
		if dp[i][j] == 'G':
			p = j
		if dp[i][j] == 'S':
			q = j
	if p > q:
		l = 1
		print(-1)
		break
	else:
		d.add(q - p - 1)
if l == 0:
	print(len(d))


def solve_tip(n, m):
	sol = set()
	for _ in range(n):
		line = input()
		g = line.find('G')
		s = line.find('S')
		if s < g:
			return -1
		sol.add(s - g)
	return len(sol)
(n, m) = [int(x) for x in input().split()]
print(solve_tip(n, m))


(n, m) = input().strip().split(' ')
(n, m) = (int(n), int(m))
array_S = []
for i in range(n):
	row = list(input().strip())
	(p1, p2) = (0, 0)
	for j in range(m):
		if row[j] == 'G':
			p1 = j
		elif row[j] == 'S':
			p2 = j
	array_S.append(p2 - p1)
if min(array_S) < 0:
	print(-1)
else:
	count = 0
	while max(array_S) > 0:
		no0 = list(filter(lambda x: x != 0, array_S))
		dis = min(no0)
		for i in range(n):
			if array_S[i] != 0:
				array_S[i] -= dis
		count += 1
	print(count)


(n, m) = map(int, input().split())
s = set()
for i in range(n):
	x = input()
	s.add(x.find('S') - x.find('G'))
b = 0
ans = len(s)
for i in s:
	if i < 0:
		b = 1
if b:
	ans = -1
print(ans)


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))


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()


def mingrid():
	for _ in range(int(input())):
		n = int(input())
		segcost = input().split()
		minodd = int(segcost[0])
		mineven = int(segcost[1])
		sumodd = minodd
		sumeven = mineven
		codd = 1
		ceven = 1
		res = sumodd + minodd * (n - codd) + sumeven + mineven * (n - ceven)
		for i in range(2, n):
			now = int(segcost[i])
			if (i + 1) % 2:
				minodd = min(minodd, now)
				sumodd += now
				codd += 1
			else:
				mineven = min(mineven, now)
				sumeven += now
				ceven += 1
			res = min(res, sumodd + minodd * (n - codd) + sumeven + mineven * (n - ceven))
		print(res)

def numofpairs():
	n = (10 * 2) ** 7 + 1
	l = [False] * n
	primes = []
	for i in range(2, n):
		if not l[i]:
			for i1 in range(i + i, n, i):
				l[i1] = True
			primes.append(i)
			l[i] = True
	tol = [0, 0]
	for i in range(2, n):
		pos = 0
		t = 0
		while i:
			val = primes[pos]
			if not i:
				tol.append(t)
				break
			elif i < val:
				tol.append(t + 1)
				break
			elif not i % val:
				i //= val
			else:
				pos += 1
				t += 1
	for _ in range(int(input())):
		(c, d, x) = map(int, input().split())
		lim = int(math.sqrt(x)) + 1
		ans = 0
		for i in range(1, lim):
			thing = i + d
			if thing % c:
				continue
			ans += 2 ** tol[thing // c]
		print(ans)

def restoremod():
	for _ in range(int(input())):
		length = int(input()) - 1
		l = input().split()
		t = False
		ife = False
		for i in range(length):
			if int(l[i]) == int(l[i + 1]):
				if i > 0:
					print(-1)
					t = True
					break
				else:
					ife = True
			elif ife:
				print(-1)
				t = True
				break
		if not t:
			posc = 0
			negc = 0
			res = int(l[1]) - int(l[0])
			if res > 0:
				posc = res
			else:
				negc = res
			if not negc:
				for i in range(1, length):
					now = int(l[i]) - int(l[i + 1])
					if now > 0:
						negc = now
						break
			if not posc:
				for i in range(1, length):
					change = int(l[i + 1]) - int(l[i])
					if change > 0:
						posc = change
						break
			if posc and negc:
				mod = posc + negc
			else:
				mod = 0
			c = posc if posc else -negc
			larnum = 0
			for i in range(length):
				nowi = int(l[i])
				larnum = max(larnum, nowi)
				if larnum > mod and mod:
					print(-1)
					t = True
					break
				res = int(l[i + 1]) - nowi
				if res < 0:
					if res != -(mod - c):
						print(-1)
						t = True
						break
				if res > 0:
					if res != c:
						t = True
						print(-1)
						break
			if not t:
				if mod:
					print(mod, c, sep=' ')
				else:
					print(mod)

def restoremod1():
	for _ in range(int(input())):
		num = int(input())
		...

def cells():
	for _ in range(int(input())):
		(row, col, num) = map(int, input().split())
		nr = (num - 1) % row
		nc = (num - 1) // row + 1
		print(nr * col + nc)

def replacement():
	for _ in range(int(input())):
		(l, k) = map(int, input().split())
		s = input()
		(left, righ) = (s.find('*'), s.rfind('*'))
		if righ - left <= k:
			print(2 if righ != left else 1)
		else:
			pos = left
			c = 2
			while righ - pos > k:
				pos = pos + k
				while pos < l and s[pos] != '*':
					pos -= 1
				c += 1
			print(c)
import math
import sys
input = sys.stdin.readline

def string():
	for _ in range(int(input())):
		s = input().rstrip()
		s1 = input().rstrip()
		maxl = 0
		p1 = [0, 0]
		p = [0, 0]
		for i in range(len(s)):
			for i1 in range(i + 1, len(s) + 1):
				pos = s1.find(s[i:i1])
				if pos == -1:
					break
				elif i1 - i <= maxl:
					continue
				elif i1 - i > maxl:
					maxl = i1 - i
					p1 = [pos, pos + maxl]
					p = [i, i + maxl]
		print(p[0] + len(s) - p[1] + (p1[0] + len(s1) - p1[1]) if maxl else len(s) + len(s1))
import collections

def trans(l):
	pos = 0
	while pos < len(l) - 1:
		avg = l[pos] // (len(l) - pos - 1)
		rem = l[pos] % (len(l) - pos - 1)
		l[pos] = 0
		for i in range(pos + 1, len(l)):
			l[i] -= avg
			if l[i] < 0:
				rem += -l[i]
				l[i] = 0
		while pos + 1 < len(l) and l[pos + 1] <= rem:
			rem -= l.pop(pos + 1)
		if pos + 1 < len(l):
			l[pos + 1] -= rem
		else:
			l[0] = rem
		pos += 1
	return sum(l)

def trans1(l):
	pos = 0
	lenl = len(l)
	pos1 = pos + 1
	while pos1 < lenl and pos < lenl:
		while pos1 < lenl and l[pos] - l[pos1] >= 0:
			l[pos] -= l[pos1]
			l[pos1] = 0
			pos1 += 1
		if pos1 < lenl:
			l[pos1] -= l[pos]
			l[pos] = 0
			pos = pos1
			pos1 += 1
	return sum(l)

def main():
	for _ in range(int(input())):
		num = input()
		l = sorted(list(collections.Counter(input().split()).values()), reverse=True)
		ans = trans(l[:])
		if ans:
			print(min(ans, trans1(l)))
		else:
			print(0)

def transrep():
	for _ in range(int(input())):
		num = int(input())
		l = list(collections.Counter(input().split()).values())
		ml = max(l)
		if ml > num - ml:
			print(ml - num + ml)
		else:
			print(num % 2)

def resmod():

	def solve():
		posc = -1
		negc = 1
		num = int(input())
		l = input().split()
		ifz = False
		maxi = int(l[0])
		for i in range(num - 1):
			maxi = max(maxi, int(l[i + 1]))
			c = int(l[i + 1]) - int(l[i])
			if c == 0:
				if not i:
					ifz = True
					continue
				elif not ifz:
					return -1
			elif ifz:
				return -1
			elif c < 0:
				if negc == 1:
					negc = c
				elif negc != c:
					return -1
			elif c > 0:
				if posc == -1:
					posc = c
				elif posc != c:
					return -1
		if posc == -1 or negc == 1:
			return 0
		mod = posc + -negc
		if mod <= maxi:
			return -1
		return '{0} {1}'.format(mod, posc)
	for _ in range(int(input())):
		print(solve())

def basicdep():

	def findmax(l):
		ans = 0
		res = 0
		for (i, v) in enumerate(l):
			if ans < v:
				res = i
				ans = v
		return [res + 1, ans]

	def roundup(num):
		s = num / 2
		if s != int(s):
			return int(s) + 1
		return int(s)
	for _ in range(int(input())):
		days = []
		(f, d) = map(int, input().split())
		friends = [0] * f
		for i in range(d):
			nowfs = input().split()
			nowff = int(nowfs[1])
			friends[nowff - 1] += 1
			if int(nowfs[0]) > 1:
				days.append([nowff, int(nowfs[2])])
			else:
				days.append([nowff, []])
		maxl = findmax(friends)
		goal = roundup(d)
		if maxl[1] < goal:
			print('YES')
			print(*[i[0] for i in days], sep=' ')
		else:
			pos = 0
			while pos < d and maxl[1] > goal:
				if days[pos][0] == maxl[0] and days[pos][1]:
					days[pos][0] = days[pos][1]
					maxl[1] -= 1
				pos += 1
			if maxl[1] > goal:
				print('NO')
			else:
				print('YES')
				print(*[i[0] for i in days], sep=' ')

def playlist():

	def nextsong(pos):
		while pos + 1 in ans and len(ans) != num:
			pos += 1
			if pos == num:
				pos = 0
		return pos

	def gcf(n, n1):
		if not n:
			return n1
		return gcf(n1, n % n1) if n1 else n
	for _ in range(int(input())):
		num = int(input())
		l = input().split()
		deletel = collections.deque()
		for i in range(num - 1):
			(a, b) = (int(l[i]), int(l[i + 1]))
			if gcf(a, b) == 1:
				deletel.append((i, i + 1))
		if gcf(int(l[-1]), int(l[0])) == 1:
			deletel.append((num - 1, 0))
		ans = dict()
		while deletel and len(ans) != num:
			(a, b) = deletel.popleft()
			if a + 1 in ans or b + 1 in ans:
				continue
			ans[b + 1] = True
			if deletel:
				if deletel[0][0] == b:
					deletel.popleft()
			if b == num - 1:
				n = nextsong(0)
				if gcf(int(l[a]), int(l[n])) == 1:
					deletel.append((a, n))
			else:
				n = nextsong(b + 1)
				if gcf(int(l[a]), int(l[n])) == 1:
					deletel.append((a, n))
		print(len(ans), *ans.keys(), sep=' ')

def shoesandst():
	(students, laces) = map(int, input().split())
	d = collections.defaultdict(list)
	rems = set()
	for _ in range(laces):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)
		lisa = d[a]
		lisb = d[b]
		la = len(lisa)
		lb = len(lisb)
		if la == 2:
			rems.discard((a, lisa[0]))
		elif la == 1:
			rems.add((a, b))
		if lb == 2:
			rems.discard((b, lisb[0]))
		elif lb == 1:
			rems.add((b, a))
	c = 0
	nextans = set()
	while rems or nextans:
		nextans.clear()
		while rems:
			(a, b) = rems.pop()
			nextans.discard((a, b))
			nextans.discard((b, a))
			d[a].pop()
			d[b].remove(a)
			lb = len(d[b])
			if not lb:
				rems.discard((b, a))
			if lb == 1:
				nextans.add((b, d[b][0]))
		rems = nextans.copy()
		c += 1
	return c
import heapq

def restoreperm():
	for _ in range(int(input())):
		length = int(input())
		maxselect = []
		minselect = []
		ansma = []
		ansmi = []
		last = 0
		for i in input().split():
			i = int(i)
			if i == last:
				ansma.append(-heapq.heappop(maxselect))
				ansmi.append(heapq.heappop(minselect))
			else:
				ansma.append(i)
				ansmi.append(i)
				for num in range(last + 1, i):
					heapq.heappush(maxselect, -num)
					heapq.heappush(minselect, num)
				last = i
		print(*ansmi, sep=' ')
		print(*ansma, sep=' ')

def maxthestring():

	def check(l):
		return tcharacters.issubset(l)
	for _ in range(int(input())):
		s = input().rstrip()
		tcharacters = set(s)
		lsc = len(tcharacters)
		t = ''
		ts = set()
		remainings = collections.deque(s)
		while len(t) < lsc:
			maxc = ''
			for i in range(len(remainings)):
				charac = remainings.popleft()
				if maxc < charac and charac not in ts:
					maxn = remainings.copy()
					maxc = charac
				if check(remainings):
					continue
				t += maxc
				ts.add(maxc)
				break
			remainings = maxn
			tcharacters.discard(maxc)
		print(t)

def maxthestring2():

	def filout(letter, s):
		iff = False
		ans = ''
		for i in s:
			if i != letter and iff:
				ans += i
			elif i == letter:
				iff = True
		return ans
	for _ in range(int(input())):
		s = input().rstrip()
		tcharacters = set(s)
		lsc = len(tcharacters)
		ans = ''
		while lsc:
			maxc = ''
			for i in tcharacters:
				news = filout(i, s)
				if len(set(news)) == lsc - 1 and maxc < i:
					maxc = i
					save = news
			tcharacters.discard(maxc)
			ans += maxc
			s = save
			lsc -= 1
		print(ans)

def maxthestring3():
	for _ in range(int(input())):
		s = input().rstrip()
		lastpos = {v: i for (i, v) in enumerate(s)}
		queue = []
		his = set()
		for i in range(len(s)):
			nowl = s[i]
			if nowl not in his:
				if queue:
					while queue[-1] < nowl and lastpos[queue[-1]] > i:
						his.discard(queue.pop())
						if not queue:
							break
					queue.append(nowl)
					his.add(nowl)
				else:
					queue.append(nowl)
					his.add(nowl)
		print(''.join(queue))

def gcdsum():

	def calc(num):
		dsum = 0
		for i in str(nownum):
			dsum += int(i)
		return dsum

	def gcd(a, b):
		if not a:
			return b
		if not b:
			return a
		return gcd(b, a % b)
	for _ in range(int(input())):
		nownum = int(input())
		dsum = calc(nownum)
		while gcd(dsum, nownum) == 1:
			nownum += 1
			dsum = calc(nownum)
		print(nownum)

def fitbox():
	for _ in range(int(input())):
		(bnum, wid) = map(int, input().split())
		boxes = sorted(list(collections.Counter(input().split()).items()), key=lambda x: int(x[0]), reverse=True)
		ans = 0
		while bnum:
			nwid = wid
			for i in range(len(boxes)):
				boxes[i] = list(boxes[i])
				(w, c) = boxes[i]
				w = int(w)
				while nwid - w >= 0 and c:
					nwid -= w
					c -= 1
					bnum -= 1
				boxes[i][1] = c
			ans += 1
		print(ans)
import sys
sys.setrecursionlimit(10000)

def reflect():

	def recur(cur, plane, dir):
		if cur == 1:
			return 1
		now = l[cur][plane][dir]
		if now != -1:
			return now
		ans = 2
		if dir:
			if cur > 1 and plane > 1:
				ans += recur(cur - 1, plane - 1, 0) - 1
			ans %= num
			if plane < planes:
				ans += recur(cur, plane + 1, 1) - 1
			ans %= num
		else:
			if cur > 1 and plane < planes:
				ans += recur(cur - 1, plane + 1, 1) - 1
			ans %= num
			if plane > 1:
				ans += recur(cur, plane - 1, 0) - 1
			ans %= num
		l[cur][plane][dir] = ans
		return ans
	num = int(1000000000.0 + 7)
	for _ in range(int(input())):
		(planes, begin) = map(int, input().split())
		l = [[[-1] * 2 for _ in range(planes + 1)] for _ in range(begin + 1)]
		print(recur(begin, 1, 1) % num)
mod = int(1000000000.0 + 7)

def iter_solver(N, K):
	dp = [[[-1 for _ in range(2)] for __ in range(K + 1)] for ___ in range(N + 1)]
	for i in range(1, N + 1):
		dp[i][1][0] = dp[i][1][1] = 1
	for k in range(2, K + 1):
		for n in range(N, 0, -1):
			ans = 2
			if n < N:
				ans += dp[n + 1][k][0] - 1
				ans %= mod
			if n > 1:
				ans += dp[n - 1][k - 1][1] - 1
				ans %= mod
			dp[n][k][0] = ans
		for n in range(1, N + 1):
			ans = 2
			if n < N:
				ans += dp[n + 1][k - 1][0] - 1
				ans %= mod
			if n > 1:
				ans += dp[n - 1][k][1] - 1
				ans %= mod
			dp[n][k][1] = ans
	return dp[1][K][0]

def dejavu():
	for _ in range(int(input())):
		s = input().rstrip()
		l = len(s)
		temp = s + 'a'
		if temp[::-1] != temp:
			print('YES')
			print(temp)
			continue
		if l == 1:
			if s == 'a':
				print('NO')
			else:
				print('YES')
				print(s + 'a')
			continue
		for i in range(l - 1, l // 2 - 1, -1):
			d = l - i
			if s[d] != 'a':
				print('YES')
				print(s[:i] + 'a' + s[i:])
				break
		else:
			print('NO')

def bits():
	for _ in range(int(input())):
		num = int(input())
		a = [i for i in input()]
		c1 = a.count('1')
		b = input()
		for i in range(num - 1, -1, -1):
			if a[i] != b[i]:
				if c1 != i + 1 - c1:
					print('NO')
					break
				for i1 in range(i, -1, -1):
					if a[i1] == '1':
						a[i1] = '0'
					else:
						a[i1] = '1'
			if a[i] == '1':
				c1 -= 1
		else:
			print('YES')

def bitsrec():

	def tran(s, num):
		if num % 2:
			if s == '1':
				return '0'
			return '1'
		return s
	for _ in range(int(input())):
		num = int(input())
		a = input()
		b = input()
		flips = 0
		ones = a.count('1')
		for i in range(num - 1, -1, -1):
			if tran(a[i], flips) != b[i]:
				if ones != i - ones + 1:
					print('NO')
					break
				flips += 1
			if tran(a[i], flips) == '1':
				ones -= 1
		else:
			print('YES')

def balance():
	for _ in range(int(input())):
		l = int(input())
		s = input()
		ans = ''
		ans1 = ''
		open = 0
		for i in range(l):
			if not i % 2:
				ans += '('
				if s[i] == '0':
					ans1 += ')'
					open -= 1
				else:
					ans1 += '('
					open += 1
			else:
				ans += ')'
				if s[i] == '0':
					ans1 += '('
					open += 1
				else:
					ans1 += ')'
					open -= 1
			if open < 0:
				print('NO')
				break
		else:
			if not open:
				print('YES')
				print(ans)
				print(ans1)
			else:
				print('NO')

def balanceres():
	for _ in range(int(input())):
		num = int(input())
		s = [i for i in input().rstrip()]
		ones = 0
		ol = []
		zl = []
		for i in range(len(s)):
			if s[i] == '1':
				ones += 1
				ol.append(i)
			else:
				zl.append(i)
		zeros = num - ones
		if zeros % 2 or ones % 2 or s[0] == '0' or (s[-1] == '0'):
			print('NO')
		else:
			pl = ones // 2
			for i in range(ones):
				if i >= pl:
					s[ol[i]] = ')'
				else:
					s[ol[i]] = '('
			diffans = s[:]
			for i in range(zeros):
				p = zl[i]
				if i % 2:
					diffans[p] = '('
					s[p] = ')'
				else:
					diffans[p] = ')'
					s[p] = '('
			print('YES')
			print(*s, sep='')
			print(*diffans, sep='')
import sys

def coloring():
	n = int(input())
	blacks = set()
	whites = set()
	for i1 in range(n):
		for i in range(n):
			if (i + i1) % 2:
				blacks.add((i1 + 1, i + 1))
			else:
				whites.add((i1 + 1, i + 1))
	for i in range(n * n):
		colortochoose = int(input())
		if colortochoose == 1:
			if blacks:
				print(2, *blacks.pop())
			else:
				print(3, *whites.pop())
		elif colortochoose == 2:
			if whites:
				print(1, *whites.pop())
			else:
				print(3, *blacks.pop())
		elif whites:
			print(1, *whites.pop())
		else:
			print(2, *blacks.pop())
		sys.stdout.flush()

def isratedans():
	while True:
		try:
			q = input()
		except EOFError:
			break
		print('NO')
		sys.stdout.flush()

def reflectres():
	for _ in range(int(input())):
		(planes, energy) = map(int, input().split())
		count = [1] * planes
		ans = 1
		energy -= 1
		dir = 1
		while energy:
			if dir:
				cur = 0
				for i in range(planes - 1, -1, -1):
					temp = cur
					cur = (cur + count[i]) % mod
					count[i] = temp
			else:
				cur = 0
				for i in range(planes):
					temp = cur
					cur = cur + count[i] % mod
					count[i] = temp
			ans = (ans + cur) % mod
			dir = 1 - dir
			energy -= 1
		print(ans)

def possible():
	s = input().rstrip()
	compare = 0
	for i in s:
		if i == '+':
			compare += 1
		else:
			compare -= 1
	s1 = input()
	todo = [(0, 0)]
	totc = 0
	ans = 0
	while todo:
		(c, pos) = todo.pop()
		if pos >= len(s):
			totc += 1
			if compare == c:
				ans += 1
			continue
		if s1[pos] == '?':
			todo.append((c + 1, pos + 1))
			todo.append((c - 1, pos + 1))
		elif s1[pos] == '+':
			todo.append((c + 1, pos + 1))
		elif s1[pos] == '-':
			todo.append((c - 1, pos + 1))
	print(ans / totc)

def chat_online():
	(p, q, start, end) = map(int, input().split())
	pl = [list(map(int, input().split())) for _ in range(p)][::-1]
	counter = [False] * 2000
	for _ in range(q):
		now = list(map(int, input().split()))
		for i in pl:
			if i[0] >= now[0]:
				pos = max(0, i[0] - now[1])
				length = i[1] - i[0] + (now[1] - now[0])
				for i2 in range(pos, length + pos + 1):
					counter[i2] = True
			else:
				break
	c = 0
	for i in range(start, end + 1):
		if counter[i]:
			c += 1
	return c

def chatonline2():

	def check(l1, l):
		for (x, y) in l:
			(x, y) = (x + i, y + i)
			for (x1, y1) in l1:
				if x <= x1 <= y or x1 <= x <= y1:
					return True
	(p, q, start, end) = map(int, input().split())
	(l, l1) = ([list(map(int, input().split())) for _ in range(p)], [list(map(int, input().split())) for _ in range(q)])
	c = 0
	for i in range(start, end + 1):
		if check(l, l1):
			c += 1
	return c

def guy():
	print('I become the guy.' if int(input()) == len(set(input().split()[1:] + input().split()[1:])) else 'Oh, my keyboard!')
from math import sqrt

def olympicmedal():
	maxr1 = 0
	for i in input().split()[1:]:
		maxr1 = max(maxr1, int(i))
	maxp1 = 0
	for i in input().split()[1:]:
		maxp1 = max(maxp1, int(i))
	minp2 = float('inf')
	for i in input().split()[1:]:
		minp2 = min(minp2, int(i))
	(a, b) = map(int, input().split())
	r2 = maxr1 * sqrt(b * maxp1 / (b * maxp1 + a * minp2))
	print(r2)

def homeworkf():
	num = input()
	sets = set(map(int, input().split()))
	lens = len(sets)
	if lens > 3:
		return 'NO'
	if lens == 2 or lens == 1:
		return 'YES'
	sets = sorted(list(sets))
	if (sets[0] + sets[2]) / 2 == sets[1]:
		return 'YES'
	else:
		return 'NO'

def candymax():
	(rows, cols) = map(int, input().split())
	diff = set()
	for _ in range(rows):
		candypos = 0
		dwpos = 0
		p = 0
		for i in input():
			if i == 'S':
				candypos = p
			elif i == 'G':
				dwpos = p
			p += 1
		if candypos < dwpos:
			return -1
		diff.add(candypos - dwpos)
	return len(diff)
print(candymax())


import sys
input = sys.stdin.readline
read_tuple = lambda _type: map(_type, input().split(' '))
from collections import Counter

def solve(n, m, grid):
	diffs = [row.index('S') - row.index('G') for row in grid]
	for diff in diffs:
		if diff < 0:
			return -1
	return len(Counter(diffs))
(n, m) = read_tuple(int)
grid = [list(input().replace('\n', '')) for _ in range(n)]
print(solve(n, m, grid))


(n, m) = map(int, input().split())
gs = set()
for i in range(n):
	row = input()
	for j in range(m):
		if row[j] == 'G':
			g = j
		if row[j] == 'S':
			s = j
	if s > g:
		gs.add(s - g)
	else:
		print(-1)
		exit(0)
print(len(gs))


(n, m) = map(int, input().split())
result = True
res = []
for _ in range(n):
	arr = input()
	g = False
	lasts = -1
	gstart = 0
	for (index, i) in enumerate(arr):
		if i == 'G':
			g = True
			gstart = index
		elif i == 'S':
			if g:
				lasts = index
				res.append(lasts - gstart)
				break
			else:
				result = False
				break
res = set(res)
if result:
	print(len(res))
else:
	print(-1)


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)
		exit()
	ds.add(d)
print(len(ds))


(n, m) = 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)


distance = lambda x: x.find('S') - x.find('G')

def main():
	(n, m) = map(int, input().split())
	s = {distance(input()) for i in range(n)}
	if min(s) < 0:
		print(-1)
	else:
		print(len(s))
main()


(n, m) = map(int, input().split())
grid = []
a = set()
for i in range(n):
	s = input()
	(x, y) = (0, 0)
	for j in range(len(s)):
		if s[j] == 'S':
			x = j
		elif s[j] == 'G':
			y = j
		else:
			continue
	a.add(x - y)
f = 1
for i in a:
	if i < 0:
		f = 0
		break
if f:
	print(len(a))
else:
	print('-1')


(n, m) = map(int, input().split())
res = 0
result = []
S_num = 0
G_num = 0
t = True
for i in range(n):
	Str = input()
	for j in range(m):
		if Str[j] == 'G':
			G_num = j
		elif Str[j] == 'S':
			S_num = j
	if S_num - G_num - 1 not in result:
		result.append(S_num - G_num - 1)
		res += 1
	if G_num > S_num:
		print(-1)
		t = False
		break
if t == True:
	print(res)


(n, m) = map(int, input().split())
l = []
for i in range(n):
	k = list(input())
	s = -1
	for j in range(m):
		if k[j] == 'G':
			for a in range(j + 1, m):
				if k[a] == 'S':
					s = abs(j - a)
			l.append(s)
if min(l) == -1:
	print(-1)
else:
	print(len(set(l)))


def main():
	(n, m) = [int(i) for i in input().split()]
	matrix = []
	for i in range(n):
		s = input()
		matrix.append(s)
	a = set()
	valid = True
	for i in range(n):
		g = 0
		s = 0
		for j in range(m):
			if matrix[i][j] == 'G':
				g = j
			if matrix[i][j] == 'S':
				s = j
		if s - g > 0:
			a.add(s - g)
		else:
			valid = False
			break
	if valid:
		print(len(a))
	else:
		print(-1)
main()


import sys
from functools import lru_cache

def main(mat):
	dist = []
	for row in mat:
		g = row.index('G')
		s = row.index('S')
		if g > s:
			print(-1)
			return
		elif s - g > 0:
			dist.append(s - g)
	print(len(set(dist)))
mat = []
for (e, line) in enumerate(sys.stdin.readlines()):
	inp = line.strip()
	if e == 0:
		continue
	mat.append(list((c for c in inp)))
main(mat)


lst = []
(z, x) = input().split()
z = int(z)
for i in range(z):
	c = input()
	lst.append(c.index('S') - c.index('G'))
lst = set(lst)
print([len(lst), -1][min(lst) < 0])


import sys
import math
import collections
import bisect

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
(n, m) = get_ints()
floor = []
np = 0
gap = 0
ans = set()
for i in range(n):
	row = list(get_string())
	g = row.index('G')
	s = row.index('S')
	if g == m - 1:
		np += 1
	elif g < s:
		val = s - g - 1
		ans.add(val)
	else:
		np += 1
if np > 0:
	print(-1)
else:
	print(len(ans))


(n, m) = map(int, input().split())
a = set()
for i in range(n):
	s = input()
	g = s.find('G')
	c = s.find('S')
	if c < g:
		print(-1)
		exit()
	a.add(g - c)
print(len(a))


n = input().split()
n = int(n[0])
se = []
s = ''
for i in range(n):
	st = input()
	g = st.index('G')
	s = st.index('S')
	s -= g
	if s <= 0:
		print(-1)
		quit()
	elif not s in se:
		se.append(s)
print(len(se))


(n, k) = map(int, input().split())
chess = []
checked = []
count = 0
l = [0] * n
for i in range(n):
	chess.append(input())
for i in range(n):
	G = chess[i].index('G')
	S = chess[i].index('S')
	if S < G:
		print(-1)
		break
	else:
		l[i] = S - G
else:
	for i in l:
		if i not in checked:
			checked.append(i)
			count += 1
	print(count)


(n, m) = map(int, input().split())
dists = set()
for i in range(n):
	row = input()
	d = row.index('S') - row.index('G')
	d = max(d, -1)
	dists.add(d)
	if d < 1:
		break
if -1 in dists:
	print(-1)
else:
	print(len(dists))


(n, m) = map(int, input().split())
distance_to_candy = []
distance_to_end = []
for _ in range(n):
	row = input()
	distance_to_candy.append(row.index('S') - row.index('G'))
	distance_to_end.append(m - row.index('G'))
if min(distance_to_candy) < 0:
	print(-1)
else:
	print(len(set(distance_to_candy)))


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())


import sys
positions = {}
i = 0
unbeatable = False
line_n = 0
for line in sys.stdin:
	i += 1
	if i == 1:
		line_n = int(line.split(' ')[0])
		continue
	line = line[:-1]
	for (i, ch) in enumerate(line):
		if ch == 'G':
			for (l, c) in enumerate(line[i:]):
				if c == 'S':
					positions[l] = True
					break
			else:
				print(-1)
				sys.exit(0)
	if line_n + 1 == i:
		break
print(len(positions))


l = list(map(int, input().split()))
n = l[0]
m = l[1]
s = set()
b = False
for i in range(n):
	q = input()
	b = False
	count = 0
	if q.find('S') < q.find('G'):
		print('-1')
		break
	for j in range(m):
		if q[j] == 'G':
			b = True
		elif b and q[j] == '*':
			count += 1
		elif q[j] == 'S':
			s.add(count)
			break
else:
	print(len(s))


(n, m) = map(int, input().split())
matrix = []
nn = n
while nn:
	matrix.append(input())
	nn -= 1
skipped = False
moves = set()
for i in range(n):
	posG = -1
	posS = -1
	for j in range(m - 1, -1, -1):
		if matrix[i][j] == 'G':
			posG = j
			if posS == -1:
				break
		elif matrix[i][j] == 'S':
			posS = j
			if posG != -1:
				break
	if posG > posS:
		skipped = True
		print(-1)
		exit(0)
	else:
		moves.add(posS - posG)
print(len(moves))


(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) = map(int, input().split())
a = []
for i in range(n):
	s = input()
	if s.index('S') - s.index('G') > 0:
		a.append(s.index('S') - s.index('G'))
	else:
		exit(print(-1))
s = len(set(a))
print(s)


(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)


(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) = [int(i) for i in input().split()]
mini = 0
flag = 0
dist = []
for i in range(n):
	l = list(input())
	S = l.index('S')
	G = l.index('G')
	if G > S:
		flag = 1
	else:
		dist.append(S - G)
if flag == 1:
	print(-1)
else:
	print(len(set(dist)))


(n, m) = list(map(int, input().split()))
ans = set()
for i in range(n):
	line = input()
	candy = -1
	dwarf = -1
	for (j, c) in enumerate(line):
		if c == 'G':
			dwarf = j
		elif c == 'S':
			candy = j
		if dwarf != -1 and candy != -1:
			break
	dist = candy - dwarf
	if dist > 0:
		ans.add(dist)
	else:
		ans = set()
		break
if len(ans) == 0:
	print(-1)
else:
	print(len(ans))


(n, m) = map(int, input().split())
matrix = []
dist = set()
for i in range(n):
	line = list(input())
	if line.index('G') > line.index('S'):
		print(-1)
		exit(0)
	dist.add(line.index('S') - line.index('G'))
print(len(dist))


def inp():
	return map(int, input().split())
from math import *
(n, m) = inp()
(out, dis) = (-1, set())
for i in range(n):
	string = input()
	(g, s) = (string.find('G'), string.find('S'))
	if g < s:
		dis.add(s - g)
	else:
		exit(print(-1))
print(len(dis))


(n, m) = map(int, input().split())
minn = 1000
a = []
for i in range(n):
	word = input()
	if word.find('S') < word.find('G'):
		print(-1)
		exit()
	else:
		x = word.find('S') - word.find('G')
		if x not in a:
			a.append(x)
print(len(a))


(n, m) = list(map(int, input().split()))
move = 0
diff = []
possible = True
for row in range(n):
	s_pos = None
	g_pos = None
	field = list(input())
	for col in range(m):
		if field[col] == 'S':
			s_pos = col
		elif field[col] == 'G':
			g_pos = col
	if g_pos > s_pos:
		possible = False
		break
	diff.append(s_pos - g_pos)
if possible:
	diff.sort()
	prev = None
	for elem in diff:
		if elem != prev:
			move += 1
		prev = elem
	print(move)
else:
	print(-1)


(n, m) = map(int, input().split())
end = m - 1
MAX = float('inf')
arr = set()
for i in range(n):
	inp = input()
	last_g = inp.rfind('G')
	if last_g == -1:
		last_g = MAX
	last_s = inp.rfind('S')
	if last_s == -1:
		last_s = MAX
	if last_s != MAX and last_g != MAX and (last_s > last_g):
		arr.add(last_s - last_g)
	if last_s < last_g:
		print(-1)
		quit()
print(len(arr))


(a, b) = [int(i) for i in input().split()]
l = []
d = 0
for i in range(a):
	s = str(input())
	if s.index('S') - s.index('G') > 0:
		l.append(s.index('S') - s.index('G'))
	else:
		d = d + 1
c = set(l)
if d > 0:
	print('-1')
else:
	print(len(c))


(n, m) = map(int, input().split())
s = set()
prnt = True
for i in range(n):
	row = list(input())
	G = row.index('G')
	S = row.index('S')
	if S < G:
		print(-1)
		prnt = False
		break
	s.add(S - G)
if prnt:
	print(len(s))


import sys

def input():
	return sys.stdin.readline().strip()
(n, m) = map(int, input().split())
matrix = []
for i in range(n):
	matrix.append(input())
count = {}
possible = True
for i in range(n):
	g_pos = 0
	s_pos = 0
	for j in range(m):
		if matrix[i][j] == 'G':
			g_pos = j
		elif matrix[i][j] == 'S':
			s_pos = j
	if s_pos < g_pos:
		possible = False
		break
	else:
		count[s_pos - g_pos] = 1
if possible:
	print(len(count))
else:
	print(-1)


(n, m) = map(int, input().split())
field = []
wrong = 0
for i in range(n):
	s = input()
	G = -1
	S = -1
	scount = 0
	gcount = 0
	for j in range(m):
		if s[j] == 'G':
			G = j
			gcount += 1
		if s[j] == 'S':
			S = j
			scount += 1
	if scount > 1 or gcount > 1:
		wrong = 1
		continue
	if scount < 1 or gcount < 1:
		wrong = 1
		continue
	if S < G:
		wrong = 1
		continue
	field.append(S - G)
if wrong == 1:
	print(-1)
else:
	d = {}
	for i in field:
		if i != 0 and i not in d:
			d[i] = 1
	print(len(d.keys()))


(n, m) = map(int, input().split())
solution = True
distances = []
for i in range(n):
	line = [c for c in input()]
	gIndex = line.index('G')
	sIndex = line.index('S')
	if sIndex < gIndex:
		solution = False
	else:
		distances.append(gIndex - sIndex)
if solution:
	print(len(set(distances)))
else:
	print(-1)


(n, m) = [int(i) for i in input().split()]
res = []
poss = True
for i in range(n):
	row = [ch for ch in input()]
	c = 0
	d = 0
	for (i, ch) in enumerate(row):
		if ch == 'G':
			d = i
		elif ch == 'S':
			c = i
	dist = c - d - 1
	if dist < 0:
		poss = False
		break
	res.append(dist)
if poss:
	print(len(set(res)))
else:
	print(-1)


(n, m) = map(int, input().split())
steps = set()
flg = True
for i in range(n):
	arr = list(input())
	if flg:
		sidx = arr.index('S')
		gidx = arr.index('G')
		if gidx > sidx:
			flg = False
			break
		else:
			steps.add(sidx - gidx)
if not flg:
	print(-1)
else:
	print(len(steps))


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)


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)))


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))


from sys import stdin, stdout
from collections import Counter, deque
from queue import PriorityQueue
helperConstants = True
helperUtilityFunctions = True

def input():
	return stdin.readline().strip()
if helperConstants:
	YES = 'YES'
	NO = 'NO'
	yes = 'yes'
	no = 'no'
	true = 'true'
	false = 'false'
	FALSE = 'FALSE'
	TRUE = 'TRUE'
	IMPOSSIBLE = 'IMPOSSIBLE'
	POSSIBLE = 'POSSIBLE'
if helperUtilityFunctions:

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

	def getIntegerInputs():
		return map(int, input().split())

	def getInputIntegerMatrix(n):
		matrix = []
		for i in range(n):
			matrix.append(list(map(int, input().split())))
		return matrix

	def getInputStringMatrix(n):
		matrix = []
		for i in range(n):
			matrix.append(input())
		return matrix

	def outputIntegerMatrix(matrix):
		for i in range(len(matrix)):
			print(*matrix[i])

	def outputStringMatrix(matrix):
		for i in range(len(matrix)):
			print(matrix[i])

	def kickstartoutput(testcase, *outputs):
		print('Case #%d:' % testcase, *outputs)

def solve():
	(n, m) = getIntegerInputs()
	matrix = getInputStringMatrix(n)
	flag = True
	freq = set()
	count = 0
	for string in matrix:
		candy = False
		dwarf = False
		for i in range(len(string)):
			char = string[i]
			if char == 'S' and (not dwarf):
				flag = False
				break
			elif char == 'G':
				dwarf = True
				pos_dwarf = i + 1
			elif char == 'S':
				candy = True
				pos_candy = i + 1
		if not candy or not dwarf:
			flag = False
			break
		if not flag:
			print(-1)
			return
		if pos_candy - pos_dwarf not in freq:
			freq.add(pos_candy - pos_dwarf)
			count += 1
	if not flag:
		print(-1)
		return
	print(count)
solve()


(n, m) = map(int, input().split())
l = []
f = 0
s = []
for i in range(n):
	temp = input()
	sindex = temp.index('S')
	gindex = temp.index('G')
	if sindex < gindex:
		f = 1
		break
	else:
		s.append(sindex - gindex)
	l.append(temp)
if f == 1:
	print(-1)
else:
	s = set(s)
	print(len(s))


def dist(s):
	return s.find('S') - s.find('G') - 1
(n, m) = map(int, input().split())
res = [dist(input()) for i in range(n)]
print(-1 if min(res) < 0 else len(set(res)))


(m, n) = list(map(int, input().split()))
li = list()
poss = 1
di = list()
for data in range(m):
	val = input()
	li.append(list(val))
	if list(val).index('G') > list(val).index('S'):
		poss = 0
		break
	else:
		value = list(val).index('S') - list(val).index('G')
		if value not in di:
			di.append(value)
if poss == 0:
	print(-1)
else:
	print(len(list(set(di))))


from sys import stdin, stdout

def main():
	(n, m) = map(int, stdin.readline().split())
	s = set()
	for _ in range(n):
		l = stdin.readline().strip()
		dwarf = -1
		candy = -1
		for i in range(m):
			if l[i] == 'G':
				dwarf = i
			if l[i] == 'S':
				candy = i
		if candy < dwarf:
			print(-1)
			return
		s.add(candy - dwarf)
	print(len(s))
	return
main()


def main():
	(nbLig, nbCol) = map(int, input().split())
	candTab = [input() for indLig in range(nbLig)]
	dset = set()
	for indLig in range(nbLig):
		dwarf = -1
		candy = -1
		for indCol in range(nbCol):
			if candTab[indLig][indCol] == 'G':
				dwarf = indCol
			elif candTab[indLig][indCol] == 'S':
				candy = indCol
				break
		if dwarf == -1:
			return -1
		dset.add(candy - dwarf)
	return len(dset)
print(main())


(n, m) = map(int, input().split())
arr = []
ans = 0
flag = True
for i in range(n):
	s = input()
	if flag:
		gap = s.find('S') - s.find('G')
		if gap > 0:
			if gap not in arr:
				arr.append(gap)
				ans += 1
		else:
			flag = False
if flag:
	print(ans)
else:
	print(-1)


(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))


(n, m) = map(int, input().split())
record = set()
for i in range(n):
	t = input()
	if t.index('G') > t.index('S'):
		print(-1)
		exit()
	else:
		record.add(t.index('S') - t.index('G'))
if record:
	print(len(record))


(n, m) = map(int, input().split())
lis = []
flag = True
for i in range(n):
	arr = input()
	idx_s = arr.index('S')
	idx_g = arr.index('G')
	if idx_s < idx_g:
		flag = False
	else:
		lis.append(idx_s - idx_g)
se = set(lis)
if not flag:
	print(-1)
else:
	print(len(se))


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


(n, m) = map(int, input().split(' '))
li = []
for i in range(n):
	s = input()
	li.append(s)
fl = 0
hs = [0] * 1001
for i in range(n):
	cid = li[i].find('S')
	did = li[i].find('G')
	if cid < did:
		fl = 1
		break
	else:
		hs[cid - did] = 1
if fl == 1:
	print(-1)
else:
	ans = 0
	for i in range(1001):
		if hs[i] == 1:
			ans += 1
	print(ans)