AtCoder Regular Contest 074 - Lotus Leaves

There is a pond with a rectangular shape.
The pond is divided into a grid with H rows and W columns of squares.
We will denote the square at the i-th row from the top and j-th column from the left by (i,\ j).
Some of the squares in the pond contains a lotus leaf floating on the water.
On one of those leaves, S, there is a frog trying to get to another leaf T.
The state of square (i,\ j) is given to you by a character a_{ij}, as follows:
 - . : A square without a leaf.
 - o : A square with a leaf floating on the water.
 - S : A square with the leaf S.
 - T : A square with the leaf T.
The frog will repeatedly perform the following action to get to the leaf T: "jump to a leaf that is in the same row or the same column as the leaf where the frog is currently located."
Snuke is trying to remove some of the leaves, other than S and T, so that the frog cannot get to the leaf T.
Determine whether this objective is achievable. If it is achievable, find the minimum necessary number of leaves to remove.

-----Constraints-----
 - 2 ≤ H, W ≤ 100
 - a_{ij} is ., o, S or T.
 - There is exactly one S among a_{ij}.
 - There is exactly one T among a_{ij}.

-----Input-----
Input is given from Standard Input in the following format:
H W
a_{11} ... a_{1W}
:
a_{H1} ... a_{HW}

-----Output-----
If the objective is achievable, print the minimum necessary number of leaves to remove.
Otherwise, print -1 instead.

-----Sample Input-----
3 3
S.o
.o.
o.T

-----Sample Output-----
2

Remove the upper-right and lower-left leaves.

Source: atcoder | Difficulty: HARD


Solutions:
from networkx import *
(H, *S) = open(0)
(H, W) = map(int, H.split())
g = Graph()
a = g.add_edges_from
for i in range((m := (H * W))):
	(a([[m * 2, (h := (i // W))], [m * 2, (w := (i % W + m))]] * ((c := S[h][w - m]) == 'S') + [[h, (I := (m * 3))], [w, I]] * (c == 'T'), capacity=I), a([[h, w], [w, h]] * (c > 'T'), capacity=1))
print([-1, (f := minimum_cut(g, m * 2, I)[0])][f < I])


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class Dinic:

	def __init__(self, n):
		self.n = n
		self.links = [[] for _ in range(n)]
		self.depth = None
		self.progress = None

	def add_link(self, _from, to, cap):
		self.links[_from].append([cap, to, len(self.links[to])])
		self.links[to].append([0, _from, len(self.links[_from]) - 1])

	def bfs(self, s):
		from collections import deque
		depth = [-1] * self.n
		depth[s] = 0
		q = deque([s])
		while q:
			v = q.popleft()
			for (cap, to, _) in self.links[v]:
				if cap > 0 and depth[to] < 0:
					depth[to] = depth[v] + 1
					q.append(to)
		self.depth = depth

	def dfs(self, v, t, flow):
		if v == t:
			return flow
		links_v = self.links[v]
		for i in range(self.progress[v], len(links_v)):
			self.progress[v] = i
			(cap, to, rev) = link = links_v[i]
			if cap == 0 or self.depth[v] >= self.depth[to]:
				continue
			d = self.dfs(to, t, min(flow, cap))
			if d == 0:
				continue
			link[0] -= d
			self.links[to][rev][0] += d
			return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.depth[t] < 0:
				return flow
			self.progress = [0] * self.n
			current_flow = self.dfs(s, t, INF)
			while current_flow > 0:
				flow += current_flow
				current_flow = self.dfs(s, t, INF)

def build_grid(H, W, intv, _type, space=True, padding=False):
	if space:
		_input = lambda : input().split()
	else:
		_input = lambda : input()
	_list = lambda : list(map(_type, _input()))
	if padding:
		offset = 1
	else:
		offset = 0
	grid = list2d(H + offset * 2, W + offset * 2, intv)
	for i in range(offset, H + offset):
		row = _list()
		for j in range(offset, W + offset):
			grid[i][j] = row[j - offset]
	return grid
(H, W) = MAP()
grid = build_grid(H, W, '', str, space=0)
dn = Dinic(H + W + 2)
s = H + W
t = H + W + 1
for i in range(H):
	for j in range(W):
		if grid[i][j] == 'o':
			dn.add_link(i, H + j, 1)
			dn.add_link(H + j, i, 1)
		elif grid[i][j] == 'S':
			dn.add_link(s, i, INF)
			dn.add_link(s, H + j, INF)
		elif grid[i][j] == 'T':
			dn.add_link(i, t, INF)
			dn.add_link(H + j, t, INF)
ans = dn.max_flow(s, t)
if ans >= INF:
	print(-1)
else:
	print(ans)


import networkx as nx
G = nx.Graph()
(h, w) = map(int, input().split())
grid = [input() for _ in range(h)]
G.add_nodes_from(range(h + w + 2))
for i in range(h):
	for j in range(w):
		if grid[i][j] == 'S':
			s = h + w
			G.add_edge(s, i)
			G.add_edge(s, j + h)
		elif grid[i][j] == 'T':
			t = h + w + 1
			G.add_edge(i, t)
			G.add_edge(j + h, t)
		elif grid[i][j] == 'o':
			G.add_edge(i, j + h, capacity=1)
			G.add_edge(j + h, i, capacity=1)
try:
	(ans, _) = nx.maximum_flow(G, s, t)
except:
	ans = -1
print(ans)


from collections import deque

class Dinic:

	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.g[fr].append(forward)
		self.g[to].append(backward)

	def add_bidirectional_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.g[v1].append(edge1)
		self.g[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.n
		deq = deque([s])
		level[s] = 0
		g = self.g
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in g[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 30
		g = self.g
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.g)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
d = Dinic(H + W + 2)
for i in range(H):
	for j in range(W):
		if a[i][j] == 'S':
			d.add_edge(H + W, i, 10 ** 5)
			d.add_edge(H + W, H + j, 10 ** 5)
		elif a[i][j] == 'T':
			d.add_edge(i, H + W + 1, 10 ** 5)
			d.add_edge(H + j, H + W + 1, 10 ** 5)
		elif a[i][j] == 'o':
			d.add_edge(i, H + j, 1)
			d.add_edge(H + j, i, 1)
ans = d.flow(H + W, H + W + 1)
if ans > 10000:
	print(-1)
else:
	print(ans)


from typing import NamedTuple, Optional, List, cast

class MFGraph:

	class Edge(NamedTuple):
		src: int
		dst: int
		cap: int
		flow: int

	class _Edge:

		def __init__(self, dst: int, cap: int) -> None:
			self.dst = dst
			self.cap = cap
			self.rev: Optional[MFGraph._Edge] = None

	def __init__(self, n: int) -> None:
		self._n = n
		self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
		self._edges: List[MFGraph._Edge] = []

	def add_edge(self, src: int, dst: int, cap: int) -> int:
		assert 0 <= src < self._n
		assert 0 <= dst < self._n
		assert 0 <= cap
		m = len(self._edges)
		e = MFGraph._Edge(dst, cap)
		re = MFGraph._Edge(src, 0)
		e.rev = re
		re.rev = e
		self._g[src].append(e)
		self._g[dst].append(re)
		self._edges.append(e)
		return m

	def get_edge(self, i: int) -> Edge:
		assert 0 <= i < len(self._edges)
		e = self._edges[i]
		re = cast(MFGraph._Edge, e.rev)
		return MFGraph.Edge(re.dst, e.dst, e.cap + re.cap, re.cap)

	def edges(self) -> List[Edge]:
		return [self.get_edge(i) for i in range(len(self._edges))]

	def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
		assert 0 <= i < len(self._edges)
		assert 0 <= new_flow <= new_cap
		e = self._edges[i]
		e.cap = new_cap - new_flow
		assert e.rev is not None
		e.rev.cap = new_flow

	def flow(self, s: int, t: int, flow_limit: Optional[int]=None) -> int:
		assert 0 <= s < self._n
		assert 0 <= t < self._n
		assert s != t
		if flow_limit is None:
			flow_limit = cast(int, sum((e.cap for e in self._g[s])))
		current_edge = [0] * self._n
		level = [0] * self._n

		def fill(arr: List[int], value: int) -> None:
			for i in range(len(arr)):
				arr[i] = value

		def bfs() -> bool:
			fill(level, self._n)
			queue = []
			q_front = 0
			queue.append(s)
			level[s] = 0
			while q_front < len(queue):
				v = queue[q_front]
				q_front += 1
				next_level = level[v] + 1
				for e in self._g[v]:
					if e.cap == 0 or level[e.dst] <= next_level:
						continue
					level[e.dst] = next_level
					if e.dst == t:
						return True
					queue.append(e.dst)
			return False

		def dfs(lim: int) -> int:
			stack = []
			edge_stack: List[MFGraph._Edge] = []
			stack.append(t)
			while stack:
				v = stack[-1]
				if v == s:
					flow = min(lim, min((e.cap for e in edge_stack)))
					for e in edge_stack:
						e.cap -= flow
						assert e.rev is not None
						e.rev.cap += flow
					return flow
				next_level = level[v] - 1
				while current_edge[v] < len(self._g[v]):
					e = self._g[v][current_edge[v]]
					re = cast(MFGraph._Edge, e.rev)
					if level[e.dst] != next_level or re.cap == 0:
						current_edge[v] += 1
						continue
					stack.append(e.dst)
					edge_stack.append(re)
					break
				else:
					stack.pop()
					if edge_stack:
						edge_stack.pop()
					level[v] = self._n
			return 0
		flow = 0
		while flow < flow_limit:
			if not bfs():
				break
			fill(current_edge, 0)
			while flow < flow_limit:
				f = dfs(flow_limit - flow)
				flow += f
				if f == 0:
					break
		return flow

	def min_cut(self, s: int) -> List[bool]:
		visited = [False] * self._n
		stack = [s]
		visited[s] = True
		while stack:
			v = stack.pop()
			for e in self._g[v]:
				if e.cap > 0 and (not visited[e.dst]):
					visited[e.dst] = True
					stack.append(e.dst)
		return visited
import sys
input = sys.stdin.readline
(h, w) = map(int, input().split())
A = tuple((input().rstrip() for _ in range(h)))
G = MFGraph(h + w + 2)
s = h + w
t = s + 1
big = 10 ** 9
for i in range(h):
	for j in range(w):
		if A[i][j] == 'S':
			G.add_edge(s, i, big)
			G.add_edge(s, h + j, big)
		if A[i][j] == 'T':
			G.add_edge(i, t, big)
			G.add_edge(h + j, t, big)
		if A[i][j] == 'o':
			G.add_edge(i, h + j, 1)
			G.add_edge(h + j, i, 1)
ans = G.flow(s, t)
if ans >= big:
	ans = -1
print(ans)


import sys
sys.setrecursionlimit(1000000)

def FF(E, s, t):
	NN = H + W + 2
	G = [[] for _ in range(NN)]
	for (a, b, f) in E:
		G[a].append([b, f, len(G[b])])
		G[b].append([a, 0, len(G[a]) - 1])

	def dfs(s, t, f):
		if s == t:
			return f
		used[s] = 1
		for (i, (b, _f, r)) in enumerate(G[s]):
			if used[b] or _f == 0:
				continue
			d = dfs(b, t, min(f, _f))
			if d > 0:
				G[s][i][1] -= d
				G[b][r][1] += d
				return d
		return 0
	flow = 0
	while 1:
		used = [0] * NN
		f = dfs(s, t, 10 ** 100)
		if f == 0:
			return flow
		flow += f
E = []
(H, W) = list(map(int, input().split()))
for i in range(H):
	A = input()
	for j in range(W):
		if A[j] == 'o':
			E.append((i, j + H, 1))
			E.append((j + H, i, 1))
		elif A[j] == 'S':
			S = (i, j + H)
		elif A[j] == 'T':
			T = (i, j + H)
E.append((H + W, S[0], 10 ** 6))
E.append((H + W, S[1], 10 ** 6))
E.append((T[0], H + W + 1, 10 ** 6))
E.append((T[1], H + W + 1, 10 ** 6))
ff = FF(E, H + W, H + W + 1)
print(ff if ff < 10 ** 6 else -1)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(h, w) = list(map(int, input().split()))
data = []
rs = []
cs = []
for i in range(h):
	c = input()
	if 'S' in c:
		start = (i, c.index('S'))
	if 'T' in c:
		goal = (i, c.index('T'))
	for j in range(w):
		if c[j] in 'o':
			data.append(1)
			rs.append(i)
			cs.append(h + j)
			data.append(1)
			rs.append(h + j)
			cs.append(i)
s = h + w
t = h + w + 1
V = 10 ** 9
data.append(V)
rs.append(s)
cs.append(start[0])
data.append(V)
rs.append(s)
cs.append(start[1] + h)
data.append(V)
rs.append(goal[0])
cs.append(t)
data.append(V)
rs.append(goal[1] + h)
cs.append(t)
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(h + w + 2, h + w + 2))
val = scipy.sparse.csgraph.maximum_flow(m, s, t).flow_value
if val >= 10 ** 9:
	val = -1
print(val)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
(H, W) = map(int, readline().split())
A = [line.rstrip().decode('utf-8') for line in readlines()]

class Dinic:

	def __init__(self, N, source, sink):
		self.N = N
		self.G = [[] for _ in range(N)]
		self.source = source
		self.sink = sink

	def add_edge(self, fr, to, cap):
		n1 = len(self.G[fr])
		n2 = len(self.G[to])
		self.G[fr].append([to, cap, n2])
		self.G[to].append([fr, 0, n1])

	def bfs(self):
		level = [0] * self.N
		G = self.G
		source = self.source
		sink = self.sink
		q = deque([source])
		level[source] = 1
		pop = q.popleft
		append = q.append
		while q:
			v = pop()
			lv = level[v] + 1
			for (to, cap, rev) in G[v]:
				if not cap:
					continue
				if level[to]:
					continue
				level[to] = lv
				if to == sink:
					self.level = level
					return
				append(to)
		self.level = level

	def dfs(self, v, f):
		if v == self.sink:
			return f
		G = self.G
		prog = self.progress
		level = self.level
		lv = level[v]
		E = G[v]
		for i in range(prog[v], len(E)):
			(to, cap, rev) = E[i]
			prog[v] = i
			if not cap:
				continue
			if level[to] <= lv:
				continue
			x = f if f < cap else cap
			ff = self.dfs(to, x)
			if ff:
				E[i][1] -= ff
				G[to][rev][1] += ff
				return ff
		return 0

	def max_flow(self):
		INF = 10 ** 18
		flow = 0
		while True:
			self.bfs()
			if not self.level[self.sink]:
				return flow
			self.progress = [0] * self.N
			while True:
				f = self.dfs(self.source, INF)
				if not f:
					break
				flow += f
		return flow
source = 0
sink = H + W + 1
dinic = Dinic(H + W + 2, source, sink)
add = dinic.add_edge
INF = 10 ** 18
for h in range(1, H + 1):
	for (w, ox) in enumerate(A[h - 1], 1):
		if ox == 'x':
			continue
		elif ox == 'o':
			add(h, H + w, 1)
			add(H + w, h, 1)
		elif ox == 'S':
			add(source, h, INF)
			add(h, source, INF)
			add(source, H + w, INF)
			add(H + w, source, INF)
		elif ox == 'T':
			add(sink, h, INF)
			add(h, sink, INF)
			add(sink, H + w, INF)
			add(H + w, sink, INF)
f = dinic.max_flow()
answer = f if f < INF else -1
print(answer)


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()

class MaxFlow(object):

	def __init__(self, n):
		self.n = n
		self.E = [[] for _ in range(n)]

	def add_edge(self, u, v, cap):
		e = [v, cap, 0]
		rev = [u, 0, e]
		e[-1] = rev
		self.E[u].append(e)
		self.E[v].append(rev)

	def _bfs(self, s, t):
		self._level = level = [-1] * self.n
		level[s] = 0
		queue = [s]
		for v in queue:
			for (nv, cap, _) in self.E[v]:
				if cap and level[nv] == -1:
					level[nv] = level[v] + 1
					if nv == t:
						return True
					queue.append(nv)
		return level[t] != -1

	def _dfs(self, s, t):
		(E, level, it) = (self.E, self._level, self._iter)
		stack = [(s, INF)]
		while stack:
			(v, f) = stack[-1]
			if v == t:
				for (v, _) in stack[:-1]:
					E[v][it[v]][1] -= f
					E[v][it[v]][-1][1] += f
				return f
			while it[v] < len(E[v]):
				(nv, cap, _) = E[v][it[v]]
				if cap and level[v] < level[nv]:
					stack.append((nv, min(f, cap)))
					break
				it[v] += 1
			else:
				stack.pop()
				level[v] = 0
		return 0

	def solve(self, s, t):
		res = 0
		while self._bfs(s, t):
			self._iter = [0] * self.n
			f = 1
			while f:
				f = self._dfs(s, t)
				res += f
		return res
from itertools import product

def resolve():
	(m, n) = map(int, input().split())
	grid = [input() for _ in range(m)]
	N = m + n
	flow = MaxFlow(N + 2)
	for (i, j) in product(range(m), range(n)):
		if grid[i][j] == 'S':
			flow.add_edge(i, j + m, INF)
			flow.add_edge(j + m, i, INF)
			flow.add_edge(N, i, INF)
			flow.add_edge(N, j + m, INF)
		elif grid[i][j] == 'T':
			flow.add_edge(i, j + m, INF)
			flow.add_edge(j + m, i, INF)
			flow.add_edge(i, N + 1, INF)
			flow.add_edge(j + m, N + 1, INF)
		elif grid[i][j] != '.':
			flow.add_edge(i, j + m, 1)
			flow.add_edge(j + m, i, 1)
	ans = flow.solve(N, N + 1)
	if ans > 10 << 30:
		ans = -1
	print(ans)
resolve()


def main():

	def add_edge(From, to, cap):
		g[From][to] = cap
		g[to][-From - 1] = 0

	def max_flow(s, t):
		flow = 0
		while True:
			used = [False] * n
			used2 = [0] * n
			q = [(s, 10 ** 6)]
			ans = [0]
			while q:
				(v, f) = q[-1]
				a = ans[0]
				if a == 0:
					if v == t:
						ans[0] = f
						continue
					(gkv, gv) = (gkey[v], g[v])
					(l, used[v]) = (len(gkv), True)
					while True:
						i = used2[v]
						used2[v] += 1
						if i < l:
							to = gkv[i]
							(cap, to2) = (gv[to], [to, -to - 1][to < 0])
							if not used[to2] and cap:
								q.append((to2, min(f, cap)))
								break
						else:
							q.pop()
							ans[0] = 0
							break
				else:
					q.pop()
					if q:
						v = q[-1][0]
						i = used2[v] - 1
						to = gkey[v][i]
						g[v][to] -= a
						g[[to, -to - 1][to < 0]][-v - 1] += a
			if not ans[0]:
				return flow
			flow += ans[0]
	(h, w) = list(map(int, input().split()))
	n = h + w + 2
	g = [dict() for _ in range(n)]
	for i in range(h):
		A = input()
		for j in range(w):
			if A[j] == 'o':
				add_edge(i, j + h, 1)
				add_edge(j + h, i, 1)
			elif A[j] == 'S':
				add_edge(h + w, i, 10 ** 6)
				add_edge(h + w, j + h, 10 ** 6)
			elif A[j] == 'T':
				add_edge(i, h + w + 1, 10 ** 6)
				add_edge(j + h, h + w + 1, 10 ** 6)
	gkey = [list(i.keys()) for i in g]
	ans = max_flow(h + w, h + w + 1)
	if ans >= 10 ** 6:
		print(-1)
	else:
		print(ans)
main()


import sys
from collections import deque
sys.setrecursionlimit(10000)

class Dinic:

	def __init__(self, V: int):
		self.V = V
		self.adj = [[] for _ in range(V)]
		self.level = [-1] * self.V
		self.iter = [-1] * self.V

	def add_edge(self, fro: int, to: int, cap: int):
		self.adj[fro].append([to, cap, len(self.adj[to])])
		self.adj[to].append([fro, 0, len(self.adj[fro]) - 1])

	def bfs(self, s: int):
		self.level = [-1] * self.V
		Q = deque()
		self.level[s] = 0
		Q.append(s)
		while Q:
			v = Q.pop()
			for i in range(len(self.adj[v])):
				(nex_id, nex_cap, nex_rev) = self.adj[v][i]
				if nex_cap > 0 and self.level[nex_id] < -0:
					self.level[nex_id] = self.level[v] + 1
					Q.append(nex_id)

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.iter[v], len(self.adj[v])):
			self.iter[v] = i
			(nex_id, nex_cap, nex_rev) = self.adj[v][i]
			if nex_cap > 0 and self.level[v] < self.level[nex_id]:
				d = self.dfs(nex_id, t, min(f, nex_cap))
				if d > 0:
					self.adj[v][i][1] -= d
					self.adj[nex_id][nex_rev][1] += d
					return d
		return 0

	def max_flow(self, s: int, t: int):
		flow = 0
		self.used = [False] * self.V
		while True:
			self.bfs(s)
			self.iter = [0] * self.V
			f = self.dfs(s, t, float('inf'))
			if f == 0:
				return flow
			else:
				flow += f
(H, W) = map(int, input().split())
grid = [[v for v in input()] for _ in range(H)]
F = Dinic(H + W + 2)
for i in range(H):
	for j in range(W):
		if grid[i][j] == 'S':
			(sy, sx) = (i, j)
			F.add_edge(0, i + 1, float('inf'))
			F.add_edge(0, H + j + 1, float('inf'))
		elif grid[i][j] == 'T':
			(gy, gx) = (i, j)
			F.add_edge(i + 1, H + W + 1, float('inf'))
			F.add_edge(H + j + 1, H + W + 1, float('inf'))
		elif grid[i][j] == 'o':
			F.add_edge(i + 1, H + j + 1, 1)
			F.add_edge(H + j + 1, i + 1, 1)
if sy == gy or sx == gx:
	print(-1)
	exit()
print(F.max_flow(0, H + W + 1))


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()
import networkx as nx

def resolve():
	(m, n) = map(int, input().split())
	G = nx.Graph()
	G.add_nodes_from(range(m + n + 2))
	for i in range(m):
		for (j, c) in enumerate(input()):
			if c == '.':
				continue
			elif c == 'o':
				G.add_edge(i, m + j, capacity=1)
			elif c == 'S':
				G.add_edge(-1, i, capacity=INF)
				G.add_edge(-1, m + j, capacity=INF)
			elif c == 'T':
				G.add_edge(i, m + n, capacity=INF)
				G.add_edge(m + j, m + n, capacity=INF)
	ans = nx.algorithms.flow.maximum_flow_value(G, -1, m + n)
	if ans >= INF:
		ans = -1
	print(ans)
resolve()


from collections import deque

class MaxFlow:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, fr, to, cap):
		m = len(self.pos)
		self.pos.append((fr, len(self.graph[fr])))
		self.graph[fr].append([to, len(self.graph[to]), cap])
		self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
		return m

	def get_edge(self, idx):
		(to, rev, cap) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		(rev_to, rev_rev, rev_cap) = self.graph[to][rev]
		return (rev_to, to, cap + rev_cap, rev_cap)

	def edges(self):
		m = len(self.pos)
		for i in range(m):
			yield self.get_edge(i)

	def change_edge(self, idx, new_cap, new_flow):
		(to, rev, cap) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
		self.graph[to][rev][2] = new_flow

	def dfs(self, s, v, up):
		if v == s:
			return up
		res = 0
		lv = self.level[v]
		for i in range(self.iter[v], len(self.graph[v])):
			(to, rev, cap) = self.graph[v][i]
			if lv <= self.level[to] or self.graph[to][rev][2] == 0:
				continue
			d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
			if d <= 0:
				continue
			self.graph[v][i][2] += d
			self.graph[to][rev][2] -= d
			res += d
			if res == up:
				break
			self.iter[v] += 1
		return res

	def max_flow(self, s, t):
		return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

	def max_flow_with_limit(self, s, t, limit):
		flow = 0
		while flow < limit:
			self.level = [-1] * self.n
			self.level[s] = 0
			queue = deque()
			queue.append(s)
			while queue:
				v = queue.popleft()
				for (to, rev, cap) in self.graph[v]:
					if cap == 0 or self.level[to] >= 0:
						continue
					self.level[to] = self.level[v] + 1
					if to == t:
						break
					queue.append(to)
			if self.level[t] == -1:
				break
			self.iter = [0] * self.n
			while flow < limit:
				f = self.dfs(s, t, limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [0] * self.n
		queue = deque()
		queue.append(s)
		while queue:
			p = queue.popleft()
			visited[p] = True
			for (to, rev, cap) in self.graph[p]:
				if cap and (not visited[to]):
					visited[to] = True
					queue.append(to)
		return visited
(H, W) = map(int, input().split())
a = [list(input().rstrip()) for _ in range(H)]
mf = MaxFlow(H + W + 2)
start = H + W
terminal = H + W + 1
INF = 10 ** 6
for i in range(H):
	for j in range(W):
		if a[i][j] == 'S':
			mf.add_edge(start, i, INF)
			mf.add_edge(start, H + j, INF)
		elif a[i][j] == 'T':
			mf.add_edge(i, terminal, INF)
			mf.add_edge(H + j, terminal, INF)
		elif a[i][j] == 'o':
			mf.add_edge(i, H + j, 1)
			mf.add_edge(H + j, i, 1)
ans = mf.max_flow(start, terminal)
if ans >= INF:
	print(-1)
else:
	print(ans)


import collections
import queue

class Dinic:

	def __init__(self, N):
		self.N = N
		self.edges = collections.defaultdict(list)
		self.level = [0 for _ in range(self.N)]
		self.iter = [0 for _ in range(self.N)]

	def add(self, u, v, c, directed=True):
		if directed:
			self.edges[u].append([v, c, len(self.edges[v])])
			self.edges[v].append([u, 0, len(self.edges[u]) - 1])
		else:
			self.edges[u].append([v, c, len(self.edges[v])])
			self.edges[v].append([u, 0, len(self.edges[u]) - 1])
			self.edges[v].append([u, c, len(self.edges[u])])
			self.edges[u].append([v, 0, len(self.edges[v]) - 1])

	def bfs(self, s):
		self.level = [-1 for _ in range(self.N)]
		self.level[s] = 0
		que = queue.Queue()
		que.put(s)
		while not que.empty():
			v = que.get()
			for i in range(len(self.edges[v])):
				e = self.edges[v][i]
				if e[1] > 0 and self.level[e[0]] < 0:
					self.level[e[0]] = self.level[v] + 1
					que.put(e[0])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.iter[v], len(self.edges[v])):
			self.iter[v] = i
			e = self.edges[v][i]
			if e[1] > 0 and self.level[v] < self.level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.edges[e[0]][e[2]][1] += d
					return d
		return 0

	def maxFlow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.iter = [0 for _ in range(self.N)]
			f = self.dfs(s, t, float('inf'))
			while f > 0:
				flow += f
				f = self.dfs(s, t, float('inf'))
(H, W) = map(int, input().split())
graph = Dinic(H + W + 2)
for h in range(H):
	tmp = str(input())
	for w in range(W):
		if tmp[w] == 'o':
			graph.add(h + 1, H + 1 + w, 1)
			graph.add(H + w + 1, h + 1, 1)
		if tmp[w] == 'S':
			start = [h, w]
			graph.add(0, h + 1, float('inf'))
			graph.add(0, H + w + 1, float('inf'))
		if tmp[w] == 'T':
			goal = [h, w]
			graph.add(h + 1, H + W + 1, float('inf'))
			graph.add(H + 1 + w, H + W + 1, float('inf'))
if start[0] == goal[0] or start[1] == goal[1]:
	print(-1)
	return
print(graph.maxFlow(0, H + W + 1))


import sys
input = sys.stdin.readline
(H, W) = list(map(int, input().split()))
a = [list(input())[:-1] for _ in range(H)]
c = H + W - 1

class FordFulkerson:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def dfs(self, v, t, f):
		if v == t:
			return f
		used = self.used
		used[v] = 1
		for e in self.G[v]:
			(w, cap, rev) = e
			if cap and (not used[w]):
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		f = INF = c
		N = self.N
		while f:
			self.used = [0] * N
			f = self.dfs(s, t, INF)
			flow += f
		return flow
flk = FordFulkerson(H * W * 2 + H + W + 1)
b = H * W
s = 0
t = 0
for i in range(H):
	for j in range(W):
		if a[i][j] != '.':
			flk.add_edge(b + i * W + j, b * 2 + i, c)
			flk.add_edge(b * 2 + i, i * W + j, c)
for j in range(W):
	for i in range(H):
		if a[i][j] != '.':
			flk.add_edge(b + i * W + j, b * 2 + H + j, c)
			flk.add_edge(b * 2 + H + j, i * W + j, c)
for i in range(H):
	for j in range(W):
		if a[i][j] != '.':
			flk.add_edge(i * W + j, b + i * W + j, 1)
		if a[i][j] == 'S':
			s = b + i * W + j
		if a[i][j] == 'T':
			t = i * W + j
if (s - b) % W != t % W and (s - b) // W != t // W:
	if sum([x.count('o') for x in a]) == H * W - 2:
		print(min(H, W) * 2 - 2)
	else:
		print(flk.flow(s, t))
else:
	print(-1)


from collections import deque
INF = float('inf')
TO = 0
CAP = 1
REV = 2

class Dinic:

	def __init__(self, N):
		self.N = N
		self.V = [[] for _ in range(N)]
		self.level = [0] * N

	def add_edge(self, u, v, cap):
		self.V[u].append([v, cap, len(self.V[v])])
		self.V[v].append([u, 0, len(self.V[u]) - 1])

	def add_edge_undirected(self, u, v, cap):
		self.V[u].append([v, cap, len(self.V[v])])
		self.V[v].append([u, cap, len(self.V[u]) - 1])

	def bfs(self, s: int) -> bool:
		self.level = [-1] * self.N
		self.level[s] = 0
		q = deque()
		q.append(s)
		while len(q) != 0:
			v = q.popleft()
			for e in self.V[v]:
				if e[CAP] > 0 and self.level[e[TO]] == -1:
					self.level[e[TO]] = self.level[v] + 1
					q.append(e[TO])
		return True if self.level[self.g] != -1 else False

	def dfs(self, v: int, f) -> int:
		if v == self.g:
			return f
		for i in range(self.ite[v], len(self.V[v])):
			self.ite[v] = i
			e = self.V[v][i]
			if e[CAP] > 0 and self.level[v] < self.level[e[TO]]:
				d = self.dfs(e[TO], min(f, e[CAP]))
				if d > 0:
					e[CAP] -= d
					self.V[e[TO]][e[REV]][CAP] += d
					return d
		return 0

	def solve(self, s, g):
		self.g = g
		flow = 0
		while self.bfs(s):
			self.ite = [0] * self.N
			f = self.dfs(s, INF)
			while f > 0:
				flow += f
				f = self.dfs(s, INF)
		return flow
(H, W) = map(int, input().split())
dinic = Dinic(H + W + 2)
for i in range(H):
	a = input()
	for (j, a_) in enumerate(a):
		if a_ == 'S':
			start = (i, j)
		elif a_ == 'T':
			goal = (i, j)
		if a_ != '.':
			dinic.add_edge_undirected(H + j, i, 1)
dinic.add_edge_undirected(H + W, start[0], 1 << 30)
dinic.add_edge_undirected(H + W, start[1] + H, 1 << 30)
dinic.add_edge_undirected(H + W + 1, goal[0], 1 << 30)
dinic.add_edge_undirected(H + W + 1, goal[1] + H, 1 << 30)
if start[0] == goal[0] or start[1] == goal[1]:
	print(-1)
else:
	print(dinic.solve(H + W, H + W + 1))


from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = list(map(iter, self.G))
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
(h, w) = list(map(int, input().split()))
dinic = Dinic((h + 1) * (w + 1))
maze = [list(input()) for _ in range(h)]
start = 0
goal = 0
INF = 10 ** 9 + 7
for i in range(h):
	for j in range(w):
		if maze[i][j] == '.':
			continue
		if maze[i][j] == 'S':
			start = (i + 1) * (w + 1) + j + 1
			dinic.add_edge(start, j + 1, INF)
			dinic.add_edge(start, (i + 1) * (w + 1), INF)
		elif maze[i][j] == 'T':
			goal = (i + 1) * (w + 1) + j + 1
			dinic.add_edge(j + 1, goal, INF)
			dinic.add_edge((i + 1) * (w + 1), goal, INF)
		dinic.add_multi_edge(j + 1, (i + 1) * (w + 1) + j + 1, 1, 1)
		dinic.add_multi_edge((i + 1) * (w + 1), (i + 1) * (w + 1) + j + 1, 1, 1)
ans = dinic.flow(start, goal)
print(ans if ans < 10 ** 9 else -1)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import networkx as nx

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

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

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

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 10
mod = 10 ** 9 + 7
(H, W) = MAP()
a = [list(input()) for _ in range(H)]
G = nx.Graph()
G.add_nodes_from(list(range(0, H + W + 2)))
for i in range(H):
	for j in range(W):
		if a[i][j] == 'S':
			(sy, sx) = (i, j)
			G.add_edge(0, i + 1, capacity=INF)
			G.add_edge(0, H + j + 1, capacity=INF)
		elif a[i][j] == 'T':
			(gy, gx) = (i, j)
			G.add_edge(i + 1, H + W + 1, capacity=INF)
			G.add_edge(H + j + 1, H + W + 1, capacity=INF)
		elif a[i][j] == 'o':
			G.add_edge(i + 1, H + j + 1, capacity=1)
			G.add_edge(H + j + 1, i + 1, capacity=1)
if sy == gy or sx == gx:
	print(-1)
	return
print(nx.maximum_flow_value(G, 0, H + W + 1))


from collections import deque
INF = 1 << 23

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for _ in range(self.N)]

	def add_edge(self, u, v, cap):
		self.G[u].append([v, cap, len(self.G[v])])
		self.G[v].append([u, 0, len(self.G[u]) - 1])

	def bfs(self, s):
		self.level = [-1] * self.N
		que = deque([s])
		self.level[s] = 0
		while que:
			u = que.popleft()
			for (v, cap, _) in self.G[u]:
				if cap > 0 and self.level[v] < 0:
					self.level[v] = self.level[u] + 1
					que.append(v)

	def dfs(self, u, t, f):
		if u == t:
			return f
		for i in range(self.progress[u], len(self.G[u])):
			self.progress[u] = i
			(v, cap, rev) = self.G[u][i]
			if cap > 0 and self.level[u] < self.level[v]:
				d = self.dfs(v, t, min(f, cap))
				if d > 0:
					self.G[u][i][1] -= d
					self.G[v][rev][1] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		INF = 10 ** 9
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.progress = [0] * self.N
			current_flow = self.dfs(s, t, INF)
			while current_flow > 0:
				flow += current_flow
				current_flow = self.dfs(s, t, INF)

def main():
	(H, W) = (int(i) for i in input().split())
	A = [input() for i in range(H)]
	F = Dinic(H + W + 2)
	s = H + W
	t = H + W + 1
	for h in range(H):
		for w in range(W):
			if A[h][w] == 'S':
				F.add_edge(s, h + W, INF)
				F.add_edge(s, w, INF)
			elif A[h][w] == 'T':
				F.add_edge(h + W, t, INF)
				F.add_edge(w, t, INF)
			if A[h][w] != '.':
				F.add_edge(h + W, w, 1)
				F.add_edge(w, h + W, 1)
	ans = F.max_flow(s, t)
	if INF <= ans:
		print(-1)
	else:
		print(ans)
main()


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

class Dinic:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.level = None
		self.it = None

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.graph[fr].append(forward)
		self.graph[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.graph[v1].append(edge1)
		self.graph[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [-1] * self.n
		deq = deque([s])
		level[s] = 0
		G = self.graph
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] == -1:
					level[w] = lv
					deq.append(w)
		return level[t] != -1

	def dfs(self, v, t, f):
		if v == t:
			return f
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and self.level[v] < self.level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 18
		while self.bfs(s, t):
			(*self.it,) = list(map(iter, self.graph))
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow

def solve():
	(H, W) = list(map(int, rl().split()))
	INF = 10 ** 18
	s = H + W
	t = s + 1
	dinic = Dinic(t + 1)
	for i in range(H):
		line = input()
		for j in range(W):
			if line[j] == 'o':
				dinic.add_multi_edge(i, H + j, 1, 1)
			elif line[j] == 'S':
				dinic.add_edge(s, i, INF)
				dinic.add_edge(s, H + j, INF)
			elif line[j] == 'T':
				dinic.add_edge(i, t, INF)
				dinic.add_edge(H + j, t, INF)
	ans = dinic.flow(s, t)
	print(ans if ans < INF else -1)

def __starting_point():
	solve()
__starting_point()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
from collections import deque

class Dinic:

	def __init__(self, n, edges):
		self.n = n
		self.edges = [[] for _ in range(n)]
		self.iter = [0] * n
		self.level = None
		self.graph(edges)

	def graph(self, E):
		edges = self.edges
		for (fr, to, cap) in E:
			edges[fr].append([to, cap, len(edges[to])])
			edges[to].append([fr, 0, len(edges[fr]) - 1])

	def maxflow(self, source, sink):
		max_flow = 0
		while True:
			self.bfs(source)
			if self.level[sink] < 0:
				return max_flow
			self.iter = [0] * self.n
			flow = self.dfs(source, sink, float('inf'))
			while flow:
				max_flow += flow
				flow = self.dfs(source, sink, float('inf'))

	def bfs(self, source):
		edges = self.edges
		level = [-1] * self.n
		level[source] = 0
		q = deque([source])
		while q:
			fr = q.popleft()
			for (to, cap, _) in edges[fr]:
				if cap > 0 > level[to]:
					level[to] = level[fr] + 1
					q.append(to)
		self.level = level

	def dfs(self, source, sink, flow):
		if source == sink:
			return flow
		while self.iter[source] < len(self.edges[source]):
			(to, cap, rev) = self.edges[source][self.iter[source]]
			if cap > 0 and self.level[source] < self.level[to]:
				f = self.dfs(to, sink, min(flow, cap))
				if f:
					self.edges[source][self.iter[source]][1] -= f
					self.edges[to][rev][1] += f
					return f
			self.iter[source] += 1
		return 0
inf = float('inf')
(h, w) = map(int, input().split())
Edges = []
for x in range(h):
	s = list(input())
	for y in range(w):
		if s[y] == 'S':
			Edges.append((0, x + 1, inf))
			Edges.append((0, y + 1 + h, inf))
		elif s[y] == 'T':
			Edges.append((x + 1, h + w + 1, inf))
			Edges.append((y + 1 + h, h + w + 1, inf))
		elif s[y] == 'o':
			Edges.append((x + 1, y + 1 + h, 1))
			Edges.append((y + 1 + h, x + 1, 1))
dinic = Dinic(h + w + 2, Edges)
mf = dinic.maxflow(0, h + w + 1)
print(-1 if mf == inf else mf)


import itertools
import os
import sys
from collections import deque, defaultdict
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(H, W) = list(map(int, sys.stdin.readline().split()))
table = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
S = H + W
T = H + W + 1
graph = [[] for _ in range(H + W + 2)]
for (h, w) in itertools.product(range(H), range(W)):
	if table[h][w] == '.':
		continue
	if table[h][w] == 'S':
		graph[S].append((h, IINF))
		graph[S].append((H + w, IINF))
	elif table[h][w] == 'T':
		graph[h].append((T, IINF))
		graph[H + w].append((T, IINF))
	graph[h].append((H + w, 1))
	graph[H + w].append((h, 1))

class Dinic:

	def __init__(self, graph=None, residual=None):
		assert graph and (not residual) or (not graph and residual)
		if graph:
			self.graph = self.residual_graph(graph)
		else:
			self.graph = residual

	@staticmethod
	def residual_graph(graph):
		ret = [[] for _ in range(len(graph))]
		for v in range(len(graph)):
			for (u, cap) in graph[v]:
				rev = [v, 0]
				edge = [u, cap, rev]
				rev.append(edge)
				ret[v].append(edge)
				ret[u].append(rev)
		return ret

	def _dist(self, s):
		ret = [-1] * len(self.graph)
		ret[s] = 0
		que = deque([(s, 0)])
		while que:
			(v, d) = que.popleft()
			for (u, cap, _) in self.graph[v]:
				if ret[u] < 0 < cap:
					ret[u] = d + 1
					que.append((u, d + 1))
		return ret

	def _dfs(self, s, t, dist, iter, flow=float('inf')):
		if s == t:
			return flow
		while iter[s] < len(self.graph[s]):
			edge = self.graph[s][iter[s]]
			(to, cap, rev) = edge
			if dist[s] < dist[to] and cap > 0:
				f = self._dfs(to, t, dist, iter, min(flow, cap))
				if f > 0:
					edge[1] -= f
					rev[1] += f
					return f
			iter[s] += 1
		return 0

	def maximum_flow(self, from_v, to_v):
		ret = 0
		while True:
			dist = self._dist(from_v)
			if dist[to_v] < 0:
				break
			iter = [0] * len(self.graph)
			while True:
				flow = self._dfs(from_v, to_v, dist, iter)
				if flow == 0:
					break
				ret += flow
		return ret
mf = Dinic(graph=graph).maximum_flow(S, T)
if mf >= IINF:
	print(-1)
else:
	print(mf)


NUMERIC_LIMITS = 10 ** 18
import queue

class maxFlow:

	class edge:

		def __init__(s, frm, to, cap, flow):
			(s.frm, s.to) = (frm, to)
			(s.cap, s.flow) = (cap, flow)

	def __init__(s, n):
		s._n = n
		s.g = [[] for _ in range(n)]
		s.pos = []

	def add_edge(s, frm, to, cap):
		m = len(s.pos)
		s.pos.append([frm, len(s.g[frm])])
		s.g[frm].append(s._edge(to, len(s.g[to]), cap))
		s.g[to].append(s._edge(frm, len(s.g[frm]) - 1, 0))
		return m

	def get_edge(s, i):
		m = len(s.pos)
		_e = s.g[s.pos[i][0]][s.pos[i][1]]
		_re = s.g[_e.to][_e.rev]
		return s.edge(s.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)

	def edges(s):
		m = len(s.pos)
		result = []
		for i in range(m):
			result.append(s.get_edge(i))
		return result

	def change_edge(s, i, new_cap, new_flow):
		m = len(s.pos)
		_e = s.g[s.pos[i].to][s.pos[i].rev]
		_re = s.g[_e.to][_e.rev]
		_e.cap = new_cap - new_flow
		_re.cap = new_flow

	def flow(self, s, t, flow_limit=NUMERIC_LIMITS):
		level = [0] * self._n
		iter = [0] * self._n

		def bfs():
			for i in range(self._n):
				level[i] = -1
			level[s] = 0
			que = queue.Queue()
			que.put(s)
			while not que.empty():
				v = que.get()
				for e in self.g[v]:
					if e.cap == 0 or level[e.to] >= 0:
						continue
					level[e.to] = level[v] + 1
					if e.to == t:
						return
					que.put(e.to)

		def dfs(this, v, up):
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(iter[v], len(self.g[v])):
				e = self.g[v][i]
				if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0:
					continue
				d = this(this, e.to, min(up - res, self.g[e.to][e.rev].cap))
				if d <= 0:
					continue
				self.g[v][i].cap += d
				self.g[e.to][e.rev].cap -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self._n):
				iter[i]
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False] * self._n
		que = queue.Queue()
		que.put(s)
		while not que.empty():
			p = que.get()
			visited[p] = True
			for e in self.g[p]:
				if e.cap and (not visited[e.to]):
					visited[e.to] = True
					que.put(e.to)
		return visited

	class _edge:

		def __init__(s, to, rev, cap):
			(s.to, s.rev) = (to, rev)
			s.cap = cap
(H, W) = list(map(int, input().split()))
a = [list(input()) for _ in range(H)]
flow = maxFlow(H + W + 2)
s = H + W
t = H + W + 1
for h in range(H):
	for w in range(W):
		if a[h][w] == 'S':
			flow.add_edge(s, h, H + W + 1)
			flow.add_edge(s, H + w, H + W + 1)
		elif a[h][w] == 'T':
			flow.add_edge(h, t, H + W + 1)
			flow.add_edge(H + w, t, H + W + 1)
		if a[h][w] != '.':
			flow.add_edge(h, H + w, 1)
			flow.add_edge(H + w, h, 1)
ans = flow.flow(s, t)
if ans > H + W:
	print(-1)
else:
	print(ans)


import sys
readline = sys.stdin.buffer.readline

def even(n):
	return 1 if n % 2 == 0 else 0
from collections import deque

class Dinic:

	def __init__(self, N, source, sink):
		self.N = N
		self.G = [[] for _ in range(N)]
		self.source = source
		self.sink = sink

	def add_edge(self, fr, to, cap):
		n1 = len(self.G[fr])
		n2 = len(self.G[to])
		self.G[fr].append([to, cap, n2])
		self.G[to].append([fr, 0, n1])

	def add_edge_undirected(self, fr, to, cap):
		n1 = len(self.G[fr])
		n2 = len(self.G[to])
		self.G[fr].append([to, cap, n2])
		self.G[to].append([fr, cap, n1])

	def bfs(self):
		level = [0] * self.N
		G = self.G
		source = self.source
		sink = self.sink
		q = deque([source])
		level[source] = 1
		pop = q.popleft
		append = q.append
		while q:
			v = pop()
			lv = level[v] + 1
			for (to, cap, rev) in G[v]:
				if not cap:
					continue
				if level[to]:
					continue
				level[to] = lv
				if to == sink:
					self.level = level
					return
				append(to)
		self.level = level

	def dfs(self, v, f):
		if v == self.sink:
			return f
		G = self.G
		prog = self.progress
		level = self.level
		lv = level[v]
		E = G[v]
		for i in range(prog[v], len(E)):
			(to, cap, rev) = E[i]
			prog[v] = i
			if not cap:
				continue
			if level[to] <= lv:
				continue
			x = f if f < cap else cap
			ff = self.dfs(to, x)
			if ff:
				E[i][1] -= ff
				G[to][rev][1] += ff
				return ff
		return 0

	def max_flow(self):
		INF = 10 ** 18
		flow = 0
		while True:
			self.bfs()
			if not self.level[self.sink]:
				return flow
			self.progress = [0] * self.N
			while True:
				f = self.dfs(self.source, INF)
				if not f:
					break
				flow += f
		return flow
(H, W) = map(int, readline().split())
maze = []
for _ in range(H):
	maze += [list(readline().rstrip().decode())]
source = 0
sink = H + W + 1
network = Dinic(H + W + 2, source, sink)
INF = 10 ** 18
for i in range(1, H + 1):
	for (j, ox) in enumerate(maze[i - 1], 1):
		if ox == 'x':
			continue
		elif ox == 'o':
			network.add_edge_undirected(i, H + j, 1)
		elif ox == 'S':
			network.add_edge_undirected(source, i, INF)
			network.add_edge_undirected(source, H + j, INF)
		elif ox == 'T':
			network.add_edge_undirected(i, sink, INF)
			network.add_edge_undirected(H + j, sink, INF)
f = network.max_flow()
if f >= INF:
	print(-1)
else:
	print(f)


(H, W) = map(int, input().split())
A = [input() for i in range(H)]
sy = sx = ty = tx = -1
for (i, row) in enumerate(A):
	for (j, c) in enumerate(row):
		if c == 'S':
			(sy, sx) = (i, j)
		if c == 'T':
			(ty, tx) = (i, j)
if sy == ty or sx == tx:
	print(-1)
	exit()
S = H + W
G = S + 1
P = G + 1
es = [[] for i in range(P)]

def add_edge(fr, to, cap):
	es[fr].append([to, cap, len(es[to])])
	es[to].append([fr, 0, len(es[fr]) - 1])
INF = float('inf')
add_edge(S, sy, INF)
add_edge(S, H + sx, INF)
add_edge(ty, G, INF)
add_edge(H + tx, G, INF)
for (i, row) in enumerate(A):
	for (j, c) in enumerate(row):
		if c != 'o':
			continue
		add_edge(i, H + j, 1)
		add_edge(H + j, i, 1)
level = [0] * P
iters = [0] * P
from collections import deque

def dinic_max_flow(s, t):
	global iters

	def _bfs(s):
		global level
		level = [-1] * P
		level[s] = 0
		q = deque([s])
		while q:
			v = q.popleft()
			for (to, cap, rev) in es[v]:
				if cap > 0 and level[to] < 0:
					level[to] = level[v] + 1
					q.append(to)

	def _dfs(v, t, f):
		if v == t:
			return f
		for i in range(iters[v], len(es[v])):
			iters[v] += 1
			(to, cap, rev) = es[v][i]
			if es[v][i][1] > 0 and level[v] < level[to]:
				d = _dfs(to, t, min(f, es[v][i][1]))
				if d > 0:
					es[v][i][1] -= d
					es[to][rev][1] += d
					return d
		return 0
	flow = 0
	while True:
		_bfs(s)
		if level[t] < 0:
			return flow
		iters = [0] * P
		f = 0
		while True:
			f = _dfs(s, t, INF)
			if f <= 0:
				break
			flow += f
print(dinic_max_flow(S, G))


from collections import deque
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

class Dinic:

	def __init__(self):
		self.G = defaultdict(list)

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		backward = [fr, 0, forward]
		forward[-1] = backward
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge2 = [v1, cap2, edge1]
		edge1[-1] = edge2
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = defaultdict(int)
		q = deque([s])
		level[s] = 1
		G = self.G
		while len(q) > 0:
			v = q.popleft()
			lv = level[v] + 1
			nexts = G[v]
			for (w, cap, _) in nexts:
				if cap > 0 and level[w] == 0:
					level[w] = lv
					q.append(w)
		is_reach = level[t] > 0
		return is_reach

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		nexts = self.G[v]
		for edge in nexts:
			(w, cap, rev) = edge
			if cap > 0 and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d > 0:
					edge[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 10
		G = self.G
		while self.bfs(s, t):
			f = INF
			while f > 0:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
ans = set()
(H, W) = map(int, input().split())
fields = []
for i in range(H):
	inp = list(input())
	fields.append(inp)
dinic = Dinic()
start = -1
end = -2
INF = 10 ** 10
for i in range(H):
	for j in range(W):
		if fields[i][j] == 'T':
			dinic.add_edge(i, end, INF)
			dinic.add_edge(j + H, end, INF)
		if fields[i][j] == 'S':
			dinic.add_edge(start, i, INF)
			dinic.add_edge(start, j + H, INF)
		if fields[i][j] != '.':
			dinic.add_edge(i, j + H, 1)
			dinic.add_edge(j + H, i, 1)
ans = dinic.flow(start, end)
if ans > INF:
	print(-1)
else:
	print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 15
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

class E:

	def __init__(self, dst, cap, rev):
		self.dst = dst
		self.cap = cap
		self.rev = rev

	def __repr__(self):
		return '({}, {}, {})'.format(self.dst, self.cap, self.rev)

	def __str__(self):
		return '({}, {}, {})'.format(self.dst, self.cap, self.rev)

class Dinic:

	def __init__(self, n):
		self.n = n
		self.g = [[] for _ in range(n)]

	def add_edge(self, src, dst, cap):
		self.g[src].append(E(dst, cap, len(self.g[dst])))
		self.g[dst].append(E(src, 0, len(self.g[src]) - 1))

	def add_undirected_edge(self, src, dst, cap):
		self.g[src].append(E(dst, cap, len(self.g[dst])))
		self.g[dst].append(E(src, cap, len(self.g[src]) - 1))

	def dfs(self, s, u, crr):
		if s == u or crr == 0:
			return crr
		sm = 0
		for i in range(self.itr[u], len(self.g[u])):
			e = self.g[u][i]
			ee = self.g[e.dst][e.rev]
			v = e.dst
			if self.level[v] >= self.level[u] or ee.cap <= 0:
				continue
			f = self.dfs(s, v, min(crr - sm, ee.cap))
			if f <= 0:
				continue
			ee.cap -= f
			e.cap += f
			sm += f
			if sm == crr:
				break
		return sm

	def run(self, s, t):
		q = [0] * self.n
		flow = 0
		while True:
			self.level = [-1] * self.n
			q[0] = s
			self.level[s] = 0
			ql = 0
			qr = 1
			while ql != qr and self.level[t] == -1:
				u = q[ql]
				ql += 1
				for e in self.g[u]:
					if e.cap > 0 and self.level[e.dst] == -1:
						self.level[e.dst] = self.level[u] + 1
						q[qr] = e.dst
						qr += 1
			if self.level[t] == -1:
				return flow
			self.itr = [0] * self.n
			flow += self.dfs(s, t, inf)
		return flow

def main():
	(h, w) = LI()
	a = [S() for _ in range(h)]
	dn = Dinic(h + w + 2)
	s = h + w
	t = s + 1
	for i in range(h):
		for j in range(w):
			c = a[i][j]
			if c == '.':
				continue
			if c == 'o':
				dn.add_undirected_edge(i, h + j, 1)
			elif c == 'S':
				dn.add_edge(s, i, inf)
				dn.add_edge(s, h + j, inf)
				for ii in range(h):
					a
			elif c == 'T':
				dn.add_edge(i, t, inf)
				dn.add_edge(h + j, t, inf)
	r = dn.run(s, t)
	if r >= inf:
		return -1
	return r
print(main())


from collections import *
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

class Dinic:

	def __init__(self, n, s, t):
		(self.n, self.s, self.t) = (n, s, t)
		self.to = defaultdict(list)
		self.level = [-1]
		self.max_flow = -1

	def add_edge(self, u, v, cap):
		u_index_in_to_v = len(self.to[v])
		v_index_in_to_u = len(self.to[u])
		self.to[u].append([v, cap, u_index_in_to_v])
		self.to[v].append([u, 0, v_index_in_to_u])

	def add_undir_edge(self, u, v, cap):
		u_index_in_to_v = len(self.to[v])
		v_index_in_to_u = len(self.to[u])
		self.to[u].append([v, cap, u_index_in_to_v])
		self.to[v].append([u, cap, v_index_in_to_u])

	def set_level(self):
		s = self.s
		level = [-1] * self.n
		level[s] = 0
		q = deque()
		q.append([s, 0])
		while q:
			(u, u_level) = q.popleft()
			for (v, cap, _) in self.to[u]:
				if cap == 0:
					continue
				if level[v] != -1:
					continue
				level[v] = u_level + 1
				if v == self.t:
					self.level = level
					return True
				q.append([v, u_level + 1])
		return False

	def dfs(self, u=-1, flow_to_me=10 ** 16):
		if u == -1:
			u = self.s
		if u == self.t:
			return flow_to_me
		flow_from_me = 0
		u_level = self.level[u]
		for (utov_i, (v, cap, vtou_i)) in enumerate(self.to[u]):
			if self.level[v] != u_level + 1:
				continue
			if cap == 0:
				continue
			flow_to_v = self.dfs(v, min(cap, flow_to_me - flow_from_me))
			if not flow_to_v:
				continue
			flow_from_me += flow_to_v
			self.to[u][utov_i][1] -= flow_to_v
			self.to[v][vtou_i][1] += flow_to_v
		return flow_from_me

	def calculation(self):
		res = 0
		while self.set_level():
			res += self.dfs()
		return res

	def get_max_flow(self):
		if self.max_flow == -1:
			self.max_flow = self.calculation()
		return self.max_flow
(h, w) = MI()
aa = [input() for _ in range(h)]

def main():
	inf = 10 ** 9 + 7
	s = h + w
	t = h + w + 1
	mc = Dinic(h + w + 2, s, t)
	(si, sj, ti, tj) = (-1, -2, -3, -4)
	for (i, row) in enumerate(aa):
		for (j, a) in enumerate(row):
			if a == 'S':
				if i == ti or j == tj:
					print(-1)
					return
				(si, sj) = (i, j)
				mc.add_edge(s, i, inf)
				mc.add_edge(s, j + h, inf)
			elif a == 'T':
				if i == si or j == sj:
					print(-1)
					return
				(ti, tj) = (i, j)
				mc.add_edge(i, t, inf)
				mc.add_edge(j + h, t, inf)
			elif a == 'o':
				mc.add_undir_edge(i, j + h, 1)
	print(mc.get_max_flow())
main()


import sys
input = sys.stdin.readline
INF = 10 ** 18
(H, W) = map(int, input().split())
V = H + W

def make():
	state = [list(input().rstrip()) for _ in range(H)]
	graph = [{} for _ in range(V + 2)]
	start = V
	finish = V + 1
	for h in range(H):
		for w in range(W):
			(u, v) = (h, w + H)
			if state[h][w] == 'o':
				graph[u][v] = 1
				graph[v][u] = 1
			if state[h][w] == 'S':
				graph[v][start] = INF
				graph[start][v] = INF
				graph[u][start] = INF
				graph[start][u] = INF
			if state[h][w] == 'T':
				graph[u][finish] = INF
				graph[finish][u] = INF
				graph[v][finish] = INF
				graph[finish][v] = INF
	return (graph, start, finish)

def dfs2(start, finish, graph):
	Flow = [INF] * len(graph)
	used = [False] * len(graph)
	Par = [-1] * len(graph)
	stack = [start]
	used[start] = True
	while stack:
		v = stack.pop()
		if v == finish:
			d = Flow[v]
			while v != start:
				nv = Par[v]
				graph[nv][v] -= d
				graph[v][nv] += d
				v = nv
			return (d, graph)
		for (i, (nv, ncap)) in enumerate(graph[v].items()):
			if not used[nv] and ncap > 0:
				used[nv] = True
				stack.append(nv)
				Par[nv] = v
				Flow[nv] = min(Flow[v], ncap)
	return (0, graph)

def max_flow(start, finish, graph):
	flow = 0
	while True:
		(f, graph) = dfs2(start, finish, graph)
		if f == 0:
			return flow
		flow += f

def main():
	(graph, start, finish) = make()
	ans = max_flow(start, finish, graph)
	if ans > INF // 2:
		print(-1)
	else:
		print(ans)
main()


class FordFulkerson:

	def __init__(self, V: int):
		self.V = V
		self.adj = [[] for _ in range(V)]
		self.used = [False] * V

	def add_edge(self, fro: int, to: int, cap: int):
		self.adj[fro].append([to, cap, len(self.adj[to])])
		self.adj[to].append([fro, 0, len(self.adj[fro]) - 1])

	def dfs(self, v, t, f):
		if v == t:
			return f
		self.used[v] = True
		for i in range(len(self.adj[v])):
			(nex_id, nex_cap, nex_rev) = self.adj[v][i]
			if not self.used[nex_id] and nex_cap > 0:
				d = self.dfs(nex_id, t, min(f, nex_cap))
				if d > 0:
					self.adj[v][i][1] -= d
					self.adj[nex_id][nex_rev][1] += d
					return d
		return 0

	def max_flow(self, s: int, t: int):
		flow = 0
		self.used = [False] * self.V
		while True:
			self.used = [False] * self.V
			f = self.dfs(s, t, float('inf'))
			if f == 0:
				return flow
			else:
				flow += f
(H, W) = list(map(int, input().split()))
grid = [[v for v in input()] for _ in range(H)]
F = FordFulkerson(H + W + 2)
for i in range(H):
	for j in range(W):
		if grid[i][j] == 'S':
			(sy, sx) = (i, j)
			F.add_edge(0, i + 1, float('inf'))
			F.add_edge(0, H + j + 1, float('inf'))
		elif grid[i][j] == 'T':
			(gy, gx) = (i, j)
			F.add_edge(i + 1, H + W + 1, float('inf'))
			F.add_edge(H + j + 1, H + W + 1, float('inf'))
		elif grid[i][j] == 'o':
			F.add_edge(i + 1, H + j + 1, 1)
			F.add_edge(H + j + 1, i + 1, 1)
if sy == gy or sx == gx:
	print(-1)
	return
print(F.max_flow(0, H + W + 1))


from collections import deque

class Dinic:

	def __init__(self, n: int):
		self.INF = 10 ** 9 + 7
		self.n = n
		self.graph = [[] for _ in range(n)]

	def add_edge(self, _from: int, to: int, capacity: int):
		forward = [to, capacity, None]
		forward[2] = backward = [_from, 0, forward]
		self.graph[_from].append(forward)
		self.graph[to].append(backward)

	def bfs(self, s: int, t: int):
		self.level = [-1] * self.n
		q = deque([s])
		self.level[s] = 0
		while q:
			_from = q.popleft()
			for (to, capacity, _) in self.graph[_from]:
				if capacity > 0 and self.level[to] < 0:
					self.level[to] = self.level[_from] + 1
					q.append(to)

	def dfs(self, _from: int, t: int, f: int) -> int:
		if _from == t:
			return f
		for edge in self.itr[_from]:
			(to, capacity, reverse_edge) = edge
			if capacity > 0 and self.level[_from] < self.level[to]:
				d = self.dfs(to, t, min(f, capacity))
				if d > 0:
					edge[1] -= d
					reverse_edge[1] += d
					return d
		return 0

	def max_flow(self, s: int, t: int):
		flow = 0
		while True:
			self.bfs(s, t)
			if self.level[t] < 0:
				break
			self.itr = list(map(iter, self.graph))
			f = self.dfs(s, t, self.INF)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.INF)
		return flow
(h, w) = map(int, input().split())
a = [list(input()) for i in range(h)]
di = Dinic(h + w + 2)
for i in range(h):
	for j in range(w):
		if a[i][j] == 'o':
			di.add_edge(i, h + j, 1)
			di.add_edge(h + j, i, 1)
		if a[i][j] == 'S':
			di.add_edge(h + w, i, 10 ** 5)
			di.add_edge(h + w, h + j, 10 ** 5)
		if a[i][j] == 'T':
			di.add_edge(i, h + w + 1, 10 ** 5)
			di.add_edge(h + j, h + w + 1, 10 ** 5)
ans = di.max_flow(h + w, h + w + 1)
if ans >= 10 ** 5:
	print(-1)
else:
	print(ans)


from scipy.sparse import *
(H, *S) = open(0)
(H, W, *A) = map(int, H.split())
for i in range((m := (H * W))):
	A += [m * 2, (h := (i // W)), (I := (m * 3)), m * 2, (w := (i % W + m)), I] * ((c := S[h][w - m]) == 'S') + [h, I, I, w, I, I] * (c == 'T') + [h, w, 1, w, h, 1] * (c > 'T')
print([-1, (f := csgraph.maximum_flow(csr_matrix((A[2::3], (A[::3], A[1::3])), [I + 1] * 2), m * 2, I).flow_value)][f < I])


from collections import deque

class mf_graph:
	n = 1
	g = [[] for i in range(1)]
	pos = []

	def __init__(self, N):
		self.n = N
		self.g = [[] for i in range(N)]

	def add_edge(self, From, To, cap):
		assert 0 <= From and From < self.n
		assert 0 <= To and To < self.n
		assert 0 <= cap
		m = len(self.pos)
		self.pos.append((From, len(self.g[From])))
		self.g[From].append({'to': To, 'rev': len(self.g[To]), 'cap': cap})
		self.g[To].append({'to': From, 'rev': len(self.g[From]) - 1, 'cap': 0})
		return m

	def get_edge(self, i):
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e['to']][_e['rev']]
		return {'from': self.pos[i][0], 'to': _e['to'], 'cap': _e['cap'] + _re['cap'], 'flow': _re['cap']}

	def edges(self):
		m = len(self.pos)
		result = []
		for i in range(m):
			result.append(self.get_edge(i))
		return result

	def change_edge(self, i, new_cap, new_flow):
		m = len(self.pos)
		assert 0 <= i and i < m
		assert 0 <= new_flow and new_flow <= new_cap
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e['to']][_e['rev']]
		_e['cap'] = new_cap - new_flow
		_re['cap'] = new_flow

	def flow(self, s, t, flow_limit=2 ** 31 - 1):
		assert 0 <= s and s < self.n
		assert 0 <= t and t < self.n
		level = [0 for i in range(self.n)]
		Iter = [0 for i in range(self.n)]
		que = deque([])

		def bfs():
			for i in range(self.n):
				level[i] = -1
			level[s] = 0
			que = deque([])
			que.append(s)
			while len(que) > 0:
				v = que.popleft()
				for e in self.g[v]:
					if e['cap'] == 0 or level[e['to']] >= 0:
						continue
					level[e['to']] = level[v] + 1
					if e['to'] == t:
						return
					que.append(e['to'])

		def dfs(func, v, up):
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(Iter[v], len(self.g[v])):
				e = self.g[v][i]
				if level_v <= level[e['to']] or self.g[e['to']][e['rev']]['cap'] == 0:
					continue
				d = func(func, e['to'], min(up - res, self.g[e['to']][e['rev']]['cap']))
				if d <= 0:
					continue
				self.g[v][i]['cap'] += d
				self.g[e['to']][e['rev']]['cap'] -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self.n):
				Iter[i] = 0
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False for i in range(self.n)]
		que = deque([])
		que.append(s)
		while len(que) > 0:
			p = que.popleft()
			visited[p] = True
			for e in self.g[p]:
				if e['cap'] and (not visited[e['to']]):
					visited[e['to']] = True
					que.append(e['to'])
		return visited
(H, W) = list(map(int, input().split()))
a = [list(input()) for i in range(H)]
G = mf_graph(H + W + 2)
INF = 10 ** 9
s = H + W
t = H + W + 1
for i in range(H):
	for j in range(W):
		if a[i][j] == 'S':
			G.add_edge(s, i, INF)
			G.add_edge(s, j + H, INF)
		if a[i][j] == 'T':
			G.add_edge(i, t, INF)
			G.add_edge(j + H, t, INF)
		if a[i][j] != '.':
			G.add_edge(i, j + H, 1)
			G.add_edge(j + H, i, 1)
ans = G.flow(s, t)
if ans >= INF:
	print(-1)
else:
	print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
from collections import deque

class MaxFlow:

	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.g[fr].append(forward)
		self.g[to].append(backward)

	def bfs(self, s, t):
		self.level = level = [None] * self.n
		deq = deque([s])
		level[s] = 0
		g = self.g
		while deq:
			v = deq.popleft()
			nlv = level[v] + 1
			for (nv, cap, _) in g[v]:
				if cap and level[nv] is None:
					level[nv] = nlv
					deq.append(nv)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(nv, cap, rev) = e
			if cap and level[v] < level[nv]:
				d = self.dfs(nv, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		g = self.g
		while self.bfs(s, t):
			(*self.it,) = list(map(iter, self.g))
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow

def main2(h, w, mat):
	ss = (-1, -1)
	tt = (-1, -1)
	n = h + w + 2
	g = [[] for _ in range(n)]
	ary = []
	inf = 10 ** 18
	for i in range(h):
		for j in range(w):
			if mat[i][j] == 'o':
				ary.append([i, h + j, 1])
				ary.append([h + j, i, 1])
			elif mat[i][j] == 'S':
				ary.append([h + w, i, inf])
				ary.append([i, h + w, inf])
				ary.append([h + w, h + j, inf])
				ary.append([h + j, h + w, inf])
				ss = (i, j)
			elif mat[i][j] == 'T':
				ary.append([h + w + 1, i, inf])
				ary.append([i, h + w + 1, inf])
				ary.append([h + w + 1, h + j, inf])
				ary.append([h + j, h + w + 1, inf])
				tt = (i, j)
	if ss[0] == tt[0] or ss[1] == tt[1]:
		return -1
	mf = MaxFlow(n)
	for (i, j, c) in ary:
		mf.add_edge(i, j, c)
	ret = mf.flow(h + w, h + w + 1)
	return ret

def __starting_point():
	(h, w) = list(map(int, input().split()))
	mat = [list(input()) for _ in range(h)]
	ret2 = main2(h, w, [x.copy() for x in mat])
	print(ret2)
__starting_point()


import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra
(H, W) = map(int, input().split())
INF = 10 ** 9
start = 0
goal = H + W + 1
V = H + W + 2
graph = [[0] * V for _ in range(V)]
edges = []
for i in range(H):
	row = input()
	for (j, cell) in enumerate(row):
		if cell == 'o':
			graph[1 + i][1 + H + j] = 1
			graph[1 + H + j][1 + i] = 1
	s = row.find('S')
	t = row.find('T')
	if s != -1:
		graph[start][1 + i] = INF
		graph[start][1 + H + s] = INF
	if t != -1:
		graph[1 + i][goal] = INF
		graph[1 + H + t][goal] = INF

def max_flow(graph):
	f = 0
	while True:
		if f > 200:
			return -1
		(dist, pred) = dijkstra(graph, indices=start, unweighted=True, return_predecessors=True)
		if dist[goal] > INF:
			return f
		f += 1
		after = goal
		while after != start:
			before = pred[after]
			graph[before][after] -= 1
			graph[after][before] += 1
			after = before
answer = max_flow(graph)
print(answer)


import collections

class Dinic:

	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		self.g[fr].append([to, cap, len(self.g[to])])
		self.g[to].append([fr, 0, len(self.g[fr]) - 1])

	def add_multi_edge(self, v1, v2, cap1, cap2):
		self.g[v1].append([v2, cap1, len(self.g[v2])])
		self.g[v2].append([v1, cap2, len(self.g[v1]) - 1])

	def bfs(self, s):
		level = [-1] * self.n
		deq = collections.deque()
		level[s] = 0
		deq.append(s)
		while deq:
			v = deq.popleft()
			for e in self.g[v]:
				if e[1] > 0 and level[e[0]] < 0:
					level[e[0]] = level[v] + 1
					deq.append(e[0])
		self.level = level

	def dfs(self, v, t, f):
		if v == t:
			return f
		es = self.g[v]
		level = self.level
		for i in range(self.it[v], len(self.g[v])):
			e = es[i]
			if e[1] > 0 and level[v] < level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.g[e[0]][e[2]][1] += d
					self.it[v] = i
					return d
		self.it[v] = len(self.g[v])
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				break
			self.it = [0] * self.n
			while True:
				f = self.dfs(s, t, 10 ** 9 + 7)
				if f > 0:
					flow += f
				else:
					break
		return flow
(h, w) = list(map(int, input().split()))
A = [input() for i in range(h)]
dinic = Dinic(h + w + 2)
start = h + w
end = h + w + 1
INF = 10 ** 9 + 7
for i in range(h):
	for j in range(w):
		c = A[i][j]
		if c is 'o':
			dinic.add_multi_edge(i, h + j, 1, 1)
		elif c is 'S':
			dinic.add_edge(start, i, INF)
			dinic.add_edge(start, h + j, INF)
		elif c is 'T':
			dinic.add_edge(i, end, INF)
			dinic.add_edge(h + j, end, INF)
ans = dinic.max_flow(start, end)
if ans >= INF:
	print(-1)
else:
	print(ans)


import collections

class Dinic:

	def __init__(self, vnum):
		self.edge = [[] for i in range(vnum)]
		self.n = vnum
		self.inf = float('inf')

	def addedge(self, st, en, c):
		self.edge[st].append([en, c, len(self.edge[en])])
		self.edge[en].append([st, 0, len(self.edge[st]) - 1])

	def bfs(self, vst):
		dist = [-1] * self.n
		dist[vst] = 0
		Q = collections.deque([vst])
		while Q:
			nv = Q.popleft()
			for (vt, c, r) in self.edge[nv]:
				if dist[vt] == -1 and c > 0:
					dist[vt] = dist[nv] + 1
					Q.append(vt)
		self.dist = dist

	def dfs(self, nv, en, nf):
		nextv = self.nextv
		if nv == en:
			return nf
		dist = self.dist
		ist = nextv[nv]
		for (i, (vt, c, r)) in enumerate(self.edge[nv][ist:], ist):
			if dist[nv] < dist[vt] and c > 0:
				df = self.dfs(vt, en, min(nf, c))
				if df > 0:
					self.edge[nv][i][1] -= df
					self.edge[vt][r][1] += df
					return df
			nextv[nv] += 1
		return 0

	def getmf(self, st, en):
		mf = 0
		while True:
			self.bfs(st)
			if self.dist[en] == -1:
				break
			self.nextv = [0] * self.n
			while True:
				fl = self.dfs(st, en, self.inf)
				if fl > 0:
					mf += fl
				else:
					break
		return mf
(H, W) = map(int, input().split())
G = [input() for _ in range(H)]
T = Dinic(H + W)
inf = 10 ** 9 + 7
SS = []
for i in range(H):
	for j in range(W):
		if G[i][j] == '.':
			continue
		if G[i][j] == 'o':
			T.addedge(i, H + j, 1)
			T.addedge(H + j, i, 1)
			continue
		SS.append(i)
		SS.append(H + j)
		T.addedge(i, H + j, inf)
		T.addedge(H + j, i, inf)
ans = T.getmf(SS[0], SS[-1])
if ans >= 10 ** 9:
	print(-1)
else:
	print(ans)


import sys
sys.setrecursionlimit(10 ** 7)

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())
from collections import deque

class Dinic:

	def __init__(self, N, inf):
		self.N = N
		self.inf = inf
		self.G = [[] for _ in range(N)]
		self.level = [0] * N

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s):
		self.level = [-1] * self.N
		deq = deque([s])
		self.level[s] = 0
		while deq:
			v = deq.pop()
			lv = self.level[v] + 1
			for (w, cap, _) in self.G[v]:
				if cap > 0 and self.level[w] == -1:
					self.level[w] = lv
					deq.appendleft(w)

	def dfs(self, v, t, f):
		if v == t:
			return f
		for e in self.iter[v]:
			(w, cap, rev) = e
			if cap > 0 and self.level[v] < self.level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d > 0:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] == -1:
				return flow
			(*self.iter,) = map(iter, self.G)
			f = self.inf
			while f > 0:
				f = self.dfs(s, t, self.inf)
				flow += f
(H, W) = MI()
inf = 10 ** 5
Di = Dinic(H + W + 2, inf)
(s, t) = (H + W, H + W + 1)
for i in range(H):
	S = LS2()
	for j in range(W):
		if S[j] == 'S':
			Di.add_edge(s, i, inf)
			Di.add_edge(s, j + H, inf)
		elif S[j] == 'T':
			Di.add_edge(i, t, inf)
			Di.add_edge(j + H, t, inf)
		elif S[j] == 'o':
			Di.add_edge(i, j + H, 1)
			Di.add_edge(j + H, i, 1)
ans = Di.flow(s, t)
print(ans if ans < inf else -1)


from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
import sys
read = sys.stdin.read
readline = sys.stdin.readline
(h, w) = map(int, readline().split())
b = read().split()
S = h + w
T = h + w + 1
D = Dinic(h + w + 2)
for i in range(h):
	for j in range(w):
		if b[i][j] == 'S':
			(sh, sw) = (i, j)
			D.add_edge(S, i, 200)
			D.add_edge(S, j + h, 200)
		elif b[i][j] == 'T':
			(th, tw) = (i, j)
			D.add_edge(i, T, 200)
			D.add_edge(j + h, T, 200)
		elif b[i][j] == 'o':
			D.add_edge(i, j + h, 1)
			D.add_edge(j + h, i, 1)
if sh == th or sw == tw:
	print(-1)
else:
	print(D.flow(S, T))


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)
INF = 10 ** 15

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class Dinic:

	def __init__(self, G, source, sink):
		self.G = G
		self.sink = sink
		self.source = source

	def add_edge(self, u, v, cap):
		self.G[u][v] = cap
		self.G[v][u] = 0

	def bfs(self):
		level = defaultdict(int)
		q = [self.source]
		level[self.source] = 1
		d = 1
		while q:
			if level[self.sink]:
				break
			qq = []
			d += 1
			for u in q:
				for (v, cap) in self.G[u].items():
					if cap == 0:
						continue
					if level[v]:
						continue
					level[v] = d
					qq += [v]
			q = qq
		self.level = level

	def dfs(self, u, f):
		if u == self.sink:
			return f
		for (v, cap) in self.iter[u]:
			if cap == 0 or self.level[v] != self.level[u] + 1:
				continue
			d = self.dfs(v, min(f, cap))
			if d:
				self.G[u][v] -= d
				self.G[v][u] += d
				return d
		return 0

	def max_flow(self):
		flow = 0
		while True:
			self.bfs()
			if self.level[self.sink] == 0:
				break
			self.iter = {u: iter(self.G[u].items()) for u in self.G}
			while True:
				f = self.dfs(self.source, INF)
				if f == 0:
					break
				flow += f
		return flow
(h, w) = LI()
s = SR(h)
G = defaultdict(lambda : defaultdict(int))
for i in range(h):
	for j in range(w):
		if s[i][j] == 'o':
			G[i][h + j] = 1
			G[h + j][i] = 1
		elif s[i][j] == 'S':
			G[h + w][i] = INF
			G[h + w][h + j] = INF
		elif s[i][j] == 'T':
			G[i][h + w + 1] = INF
			G[h + j][h + w + 1] = INF
ans = Dinic(G, h + w, h + w + 1).max_flow()
print(ans if ans < INF else -1)


import sys
sys.setrecursionlimit(10 ** 8)

class FK:

	def __init__(self, n):
		self.table = [[0] * n for i in range(n)]
		self.n = n

	def add(self, x, y, f):
		self.table[x][y] = f

	def ford(self, s, t, f):
		self.visit[s] = True
		if s == t:
			return f
		for i in range(self.n):
			if not self.visit[i] and self.table[s][i] > 0:
				df = self.ford(i, t, min(f, self.table[s][i]))
				if df > 0:
					self.table[s][i] -= df
					self.table[i][s] += df
					return df
		return 0

	def flow(self, s, t):
		ans = 0
		inf = 10 ** 20
		while True:
			self.visit = [False] * self.n
			df = self.ford(s, t, inf)
			if df == 0:
				break
			ans += df
		return ans
(H, W) = map(int, input().split())
C = [input() for i in range(H)]
maxflow = FK(W + H + 2)
inf = 10 ** 20
for i in range(W):
	for j in range(H):
		if C[j][i] == 'S':
			sx = i
			sy = j
			maxflow.add(0, i + 1, inf)
			maxflow.add(0, W + 1 + j, inf)
			continue
		if C[j][i] == 'T':
			gx = i
			gy = j
			maxflow.add(i + 1, W + H + 1, inf)
			maxflow.add(W + 1 + j, W + H + 1, inf)
			continue
		if C[j][i] == 'o':
			maxflow.add(i + 1, W + 1 + j, 1)
			maxflow.add(W + 1 + j, i + 1, 1)
if gx == sx or gy == sy:
	print('-1')
	return
ans = maxflow.flow(0, H + W + 1)
print(ans)


INF = 10 ** 9
que = [0] * 1024

def bfs(g, flow, parent, s1, s2, t1, t2):
	qf = 0
	que[0] = s1
	que[1] = s2
	ql = 2
	while qf < ql:
		u = que[qf]
		qf += 1
		for v in g[u]:
			if 0 <= flow[u][v] and parent[v] == -1:
				parent[v] = u
				if v != t1 and v != t2:
					que[ql] = v
					ql += 1
				else:
					return (1, v)
	return (0, 0)

def solve(h, w, g, s, t):
	n = h + w
	(si, sj) = s
	(ti, tj) = t
	if si == ti or sj == tj:
		return -1
	f = 0
	flow = [[0] * n for _ in range(n)]
	while True:
		parent = [-1] * n
		parent[si] = -2
		parent[sj] = -2
		(m, te) = bfs(g, flow, parent, si, sj, ti, tj)
		if m == 0:
			break
		f += 1
		v = te
		while v != si and v != sj:
			u = parent[v]
			flow[u][v] -= 1
			flow[v][u] += 1
			v = u
	return f

def main():
	(h, w) = input().split()
	h = int(h)
	w = int(w)
	g = [[] for _ in range(h + w)]
	s = None
	t = None
	for i in range(h):
		a = input()
		for j in range(w):
			ch = a[j]
			if ch == 'o':
				g[i].append(h + j)
				g[h + j].append(i)
			elif ch == 'S':
				s = (i, h + j)
			elif ch == 'T':
				t = (i, h + j)
	print(solve(h, w, g, s, t))

def __starting_point():
	main()
__starting_point()


import queue

class Dinic:

	def __init__(self, v, inf=1000000007):
		self.V = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.level = [0 for _ in range(v)]
		self.iter = [0 for _ in range(v)]

	def add_edge(self, from_, to, cap):
		self.G[from_].append({'to': to, 'cap': cap, 'rev': len(self.G[to])})
		self.G[to].append({'to': from_, 'cap': 0, 'rev': len(self.G[from_]) - 1})

	def bfs(self, s):
		self.level = [-1 for _ in range(self.V)]
		self.level[s] = 0
		que = queue.Queue()
		que.put(s)
		while not que.empty():
			v = que.get()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e['cap'] > 0 and self.level[e['to']] < 0:
					self.level[e['to']] = self.level[v] + 1
					que.put(e['to'])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.iter[v], len(self.G[v])):
			self.iter[v] = i
			e = self.G[v][i]
			if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
				d = self.dfs(e['to'], t, min(f, e['cap']))
				if d > 0:
					e['cap'] -= d
					self.G[e['to']][e['rev']]['cap'] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.iter = [0 for _ in range(self.V)]
			f = self.dfs(s, t, self.inf)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.inf)
(H, W) = map(int, input().split())
a = [list(input()) for i in range(H)]
Dn = Dinic(2 + H + W)
INF = 10 ** 15
s = (-1, -1)
t = (-1, -1)
for i in range(H):
	for j in range(W):
		if a[i][j] != '.':
			Dn.add_edge(i + 1, H + 1 + j, 1)
			Dn.add_edge(H + 1 + j, i + 1, 1)
		if a[i][j] == 'S':
			Dn.add_edge(0, i + 1, INF)
			Dn.add_edge(0, H + 1 + j, INF)
			s = (i, j)
		if a[i][j] == 'T':
			Dn.add_edge(i + 1, H + W + 1, INF)
			Dn.add_edge(H + 1 + j, H + W + 1, INF)
			t = (i, j)
if s[0] == t[0] or s[1] == t[1]:
	print(-1)
else:
	ans = Dn.max_flow(0, 1 + H + W)
	print(ans)


def main():
	import sys
	input = sys.stdin.readline
	from collections import deque

	class Dinic:

		def __init__(self, N):
			self.N = N
			self.G = [[] for i in range(N)]

		def add_edge(self, fr, to, cap):
			forward = [to, cap, None]
			forward[2] = backward = [fr, 0, forward]
			self.G[fr].append(forward)
			self.G[to].append(backward)

		def add_multi_edge(self, v1, v2, cap1, cap2):
			edge1 = [v2, cap1, None]
			edge1[2] = edge2 = [v1, cap2, edge1]
			self.G[v1].append(edge1)
			self.G[v2].append(edge2)

		def bfs(self, s, t):
			self.level = level = [None] * self.N
			deq = deque([s])
			level[s] = 0
			G = self.G
			while deq:
				v = deq.popleft()
				lv = level[v] + 1
				for (w, cap, _) in G[v]:
					if cap and level[w] is None:
						level[w] = lv
						deq.append(w)
			return level[t] is not None

		def dfs(self, v, t, f):
			if v == t:
				return f
			level = self.level
			for e in self.it[v]:
				(w, cap, rev) = e
				if cap and level[v] < level[w]:
					d = self.dfs(w, t, min(f, cap))
					if d:
						e[1] -= d
						rev[1] += d
						return d
			return 0

		def flow(self, s, t):
			flow = 0
			INF = 10 ** 9 + 7
			G = self.G
			while self.bfs(s, t):
				(*self.it,) = map(iter, self.G)
				f = INF
				while f:
					f = self.dfs(s, t, INF)
					flow += f
			return flow
	(H, W) = map(int, input().split())
	grid = []
	for _ in range(H):
		line = input().rstrip('\n')
		grid.append(line)
	dinic = Dinic(H + W + 5)
	for h in range(H):
		for w in range(W):
			if grid[h][w] == 'o':
				dinic.add_edge(h + 1, H + w + 1, 1)
				dinic.add_edge(H + w + 1, h + 1, 1)
			elif grid[h][w] == 'S':
				dinic.add_edge(H + W + 1, h + 1, 10 ** 5)
				dinic.add_edge(H + W + 1, H + w + 1, 10 ** 5)
			elif grid[h][w] == 'T':
				dinic.add_edge(h + 1, H + W + 2, 10 ** 5)
				dinic.add_edge(H + w + 1, H + W + 2, 10 ** 5)
	ans = dinic.flow(H + W + 1, H + W + 2)
	if ans > 400:
		print(-1)
	else:
		print(ans)
main()


from collections import deque

class MF_graph(object):

	def __init__(self, n):
		self.n = n
		self.g = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, frm, to, cap):
		m = len(self.pos)
		self.pos.append((frm, len(self.g[frm])))
		self.g[frm].append([to, len(self.g[to]), cap])
		self.g[to].append([frm, len(self.g[frm]) - 1, 0])
		return m

	def get_edge(self, i):
		(e_to, e_rev, e_cap) = self.g[self.pos[i][0]][self.pos[i][1]]
		(re_to, _, re_cap) = self.g[e_to][e_rev]
		return (re_to, e_to, e_cap + re_cap, re_cap)

	def edges(self):
		m = len(self.pos)
		for i in range(m):
			yield self.get_edge(i)

	def change_edge(self, i, new_cap, new_flow):
		(f, s) = self.pos[i]
		(rf, rs, _) = self.g[f][s]
		self.g[f][s][2] = new_cap - new_flow
		self.g[rf][rs][2] = new_flow
		return

	def dfs(self, s, v, up):
		if v == s:
			return up
		res = 0
		level_v = self.level[v]
		for i in range(self.iter[v], len(self.g[v])):
			(u_to, u_rev, _) = self.g[v][i]
			if level_v <= self.level[u_to] or self.g[u_to][u_rev][2] == 0:
				continue
			d = self.dfs(s, u_to, min(up - res, self.g[u_to][u_rev][2]))
			if d <= 0:
				continue
			self.g[v][i][2] += d
			self.g[u_to][u_rev][2] -= d
			res += d
			if res == up:
				break
		return res

	def flow(self, s, t, flow_limit=10 ** 18):
		self.iter = [0] * self.n
		flow = 0
		while flow < flow_limit:
			self.level = [-1] * self.n
			self.level[s] = 0
			que = deque([s])
			while que:
				v = que.popleft()
				for (u_to, _, u_cap) in self.g[v]:
					if u_cap == 0 or self.level[u_to] >= 0:
						continue
					self.level[u_to] = self.level[v] + 1
					if u_to == t:
						break
					que.append(u_to)
			if self.level[t] == -1:
				break
			self.iter = [0] * self.n
			while flow < flow_limit:
				f = self.dfs(s, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False] * self.n
		que = deque([s])
		while que:
			v = que.popleft()
			visited[v] = True
			for (u_to, _, u_cap) in self.g[v]:
				if u_cap and (not visited[u_to]):
					visited[u_to] = True
					que.append(u_to)
		return visited
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
inf = 10 ** 18
g = MF_graph(H + W + 2)
source = H + W
sink = H + W + 1
for i in range(H):
	for j in range(W):
		if S[i][j] == 'S':
			g.add_edge(source, i, inf)
			g.add_edge(source, H + j, inf)
		elif S[i][j] == 'T':
			g.add_edge(i, sink, inf)
			g.add_edge(H + j, sink, inf)
		elif S[i][j] == 'o':
			g.add_edge(i, H + j, 1)
			g.add_edge(H + j, i, 1)
flow = g.flow(source, sink)
if flow >= inf:
	print(-1)
else:
	print(flow)


from collections import deque

class Dinic:

	def __init__(self, v, inf=10 ** 9 + 7):
		self.V = v
		self.inf = inf
		self.G = [list() for _ in range(v)]
		self.level = [-1 for _ in range(v)]
		self.iter = [0] * v

	def addedge(self, fr, to, cap):
		go = [to, cap, None]
		go[2] = back = [fr, 0, go]
		self.G[fr].append(go)
		self.G[to].append(back)

	def bfs(self, st, en):
		q = deque([st])
		self.level = [-1 for _ in range(self.V)]
		self.level[st] = 0
		while q:
			cur = q.popleft()
			for (x, cap, _) in self.G[cur]:
				if cap and self.level[x] < 0:
					self.level[x] = self.level[cur] + 1
					q.append(x)
		return self.level[en] > 0

	def dfs(self, v, t, f):
		if v == t:
			return f
		for e in self.iter[v]:
			(w, cap, rev) = e
			if cap and self.level[v] < self.level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		while self.bfs(s, t):
			self.iter = list(map(iter, self.G))
			f = self.dfs(s, t, self.inf)
			while f:
				flow += f
				f = self.dfs(s, t, self.inf)
		return flow
(H, W) = map(int, input().split())
dinic = Dinic(200)
for y in range(H):
	s = input()
	for x in range(W):
		if s[x] == 'o':
			dinic.addedge(y, x + 100, 1)
			dinic.addedge(x + 100, y, 1)
		elif s[x] == 'S':
			(sy, sx) = (y, x)
			dinic.addedge(y, x + 100, 10 ** 5)
			dinic.addedge(x + 100, y, 10 ** 5)
		elif s[x] == 'T':
			(ty, tx) = (y, x)
			dinic.addedge(y, x + 100, 10 ** 5)
			dinic.addedge(x + 100, y, 10 ** 5)
print(-1 if sy == ty or sx == tx else dinic.flow(sy, ty))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict
(H, W) = map(int, readline().split())
A = [line.rstrip().decode('utf-8') for line in readlines()]
source = 0
sink = H + W + 1
graph = [defaultdict(int) for _ in range(H + W + 2)]
INF = 10 ** 18
for h in range(1, H + 1):
	for (w, ox) in enumerate(A[h - 1], 1):
		if ox == 'x':
			continue
		elif ox == 'o':
			graph[h][H + w] = 1
			graph[H + w][h] = 1
		elif ox == 'S':
			graph[source][h] = INF
			graph[h][source] = INF
			graph[source][H + w] = INF
			graph[H + w][source] = INF
		elif ox == 'T':
			graph[sink][h] = INF
			graph[h][sink] = INF
			graph[sink][H + w] = INF
			graph[H + w][sink] = INF

class Dinic:

	def __init__(self, graph, V, source, sink):
		self.graph = graph
		self.sink = sink
		self.source = source
		self.V = V
		self.N = len(V)

	def compress(self):
		self.N = len(self.V)
		v_to_i = {x: i for (i, x) in enumerate(self.V)}
		self.sink = v_to_i[self.sink]
		self.source = v_to_i[self.source]
		g = [dict() for _ in range(self.N)]
		for (v, e) in self.graph.items():
			vn = v_to_i[v]
			g[vn] = {v_to_i[w]: c for (w, c) in e.items()}
		self.graph = g

	def bfs(self):
		level = [0] * self.N
		q = [self.source]
		level[self.source] = 1
		d = 1
		while q:
			if level[self.sink]:
				break
			qq = []
			d += 1
			for v in q:
				for (w, cap) in self.graph[v].items():
					if cap == 0:
						continue
					if level[w]:
						continue
					level[w] = d
					qq.append(w)
			q = qq
		self.level = level

	def dfs(self, v, f):
		if v == self.sink:
			return f
		for (w, cap) in self.itr[v]:
			if cap == 0 or self.level[w] != self.level[v] + 1:
				continue
			d = self.dfs(w, min(f, cap))
			if d:
				self.graph[v][w] -= d
				self.graph[w][v] += d
				return d
		return 0

	def max_flow(self):
		INF = 10 ** 18
		flow = 0
		while True:
			self.bfs()
			if self.level[self.sink] == 0:
				break
			self.itr = [iter(e.items()) for e in self.graph]
			while True:
				f = self.dfs(self.source, INF)
				if f == 0:
					break
				flow += f
		return flow
answer = Dinic(graph=graph, V=list(range(H + W + 2)), source=0, sink=H + W + 1).max_flow()
if answer >= INF:
	answer = -1
print(answer)


from collections import defaultdict

def ford_fulkerson(graph, start, end):
	INF = 10 ** 9
	network = [defaultdict(int, paths) for paths in graph]

	def dfs(start, end, visited):
		if start == end:
			return ()
		visited.add(start)
		for (next_, capacity) in filter(lambda next_capacity: next_capacity[0] not in visited and next_capacity[1] > 0, network[start].items()):
			path = dfs(next_, end, visited)
			if path is not None:
				return (next_, capacity, path)
		return None

	def margin(path, min_margin=INF):
		if path == ():
			return min_margin
		(_, capacity, remaining_path) = path
		return margin(remaining_path, min(min_margin, capacity))

	def flush(start, path, amount):
		if path == ():
			return
		(next_, _, remaining_path) = path
		network[start][next_] -= amount
		network[next_][start] += amount
		flush(next_, remaining_path, amount)
	while True:
		path = dfs(start, end, set())
		if path == None:
			break
		flush(start, path, margin(path))
	return sum((cap for (_, cap) in graph[start].items())) - sum((cap for (_, cap) in network[start].items()))
(h, w) = map(int, input().split())
A = [input() for _ in range(h)]
for i in range(h):
	for j in range(w):
		if A[i][j] == 'S':
			s = (i, j)
		if A[i][j] == 'T':
			t = (i, j)
if t[0] == s[0] or t[1] == s[1]:
	print(-1)
else:
	INF = 10 ** 8
	si = h + w
	ti = h + w + 1
	graph = [{} for _ in range(h + w + 2)]
	graph[si][s[0]] = INF
	graph[si][h + s[1]] = INF
	graph[t[0]][ti] = INF
	graph[h + t[1]][ti] = INF
	for i in range(h):
		for j in range(w):
			if A[i][j] == 'o':
				graph[i][h + j] = 1
				graph[h + j][i] = 1
	print(ford_fulkerson(graph, si, ti))


import networkx as nx
(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
INF = 10 ** 20
G = nx.Graph()
G.add_nodes_from(range(0, H + W + 2))
for i in range(H):
	for j in range(W):
		if a[i][j] == 'o':
			G.add_edge(i + 1, j + H + 1, capacity=1)
		if a[i][j] == 'S':
			G.add_edge(0, i + 1, capacity=INF)
			G.add_edge(0, j + H + 1, capacity=INF)
		if a[i][j] == 'T':
			G.add_edge(H + W + 1, i + 1, capacity=INF)
			G.add_edge(H + W + 1, j + H + 1, capacity=INF)
(flow_value, flow_dict) = nx.maximum_flow(G, 0, H + W + 1)
print(flow_value if flow_value < INF else -1)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

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

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

def ZIP(n):
	return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Dinic:

	def __init__(self, v, inf=10 ** 10):
		self.v = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.level = [-1] * v
		self.ite = [0] * v

	def add_edge(self, fr, to, cap):
		self.G[fr].append([to, cap, len(self.G[to])])
		self.G[to].append([fr, 0, len(self.G[fr]) - 1])

	def bfs(self, s):
		self.level = [-1] * self.v
		self.level[s] = 0
		Q = deque()
		Q.append(s)
		while Q:
			v = Q.popleft()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e[1] > 0 and self.level[e[0]] < 0:
					self.level[e[0]] = self.level[v] + 1
					Q.append(e[0])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.ite[v], len(self.G[v])):
			self.ite[v] = i
			e = self.G[v][i]
			if e[1] > 0 and self.level[v] < self.level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.G[e[0]][e[2]][1] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.ite = [0] * self.v
			f = self.dfs(s, t, self.inf)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.inf)
(H, W) = MAP()
a = [list(input()) for _ in range(H)]
D = Dinic(H + W + 2)
for i in range(H):
	for j in range(W):
		if a[i][j] == 'S':
			(sy, sx) = (i, j)
			D.add_edge(0, i + 1, INF)
			D.add_edge(0, H + j + 1, INF)
		elif a[i][j] == 'T':
			(gy, gx) = (i, j)
			D.add_edge(i + 1, H + W + 1, INF)
			D.add_edge(H + j + 1, H + W + 1, INF)
		elif a[i][j] == 'o':
			D.add_edge(i + 1, H + j + 1, 1)
			D.add_edge(H + j + 1, i + 1, 1)
if sy == gy or sx == gx:
	print(-1)
	exit()
print(D.max_flow(0, H + W + 1))


from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 10
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = list(map(iter, self.G))
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
inf = 10 ** 9
(H, W) = list(map(int, input().split()))
a = [list(input()) for _ in range(H)]
D = Dinic(H + W + 2)
for i in range(H):
	for j in range(W):
		if a[i][j] == 'S':
			D.add_edge(0, i + 1, inf)
			D.add_edge(0, j + 1 + H, inf)
		elif a[i][j] == 'T':
			D.add_edge(i + 1, H + W + 1, inf)
			D.add_edge(j + 1 + H, H + W + 1, inf)
		elif a[i][j] == 'o':
			D.add_edge(i + 1, j + 1 + H, 1)
			D.add_edge(j + 1 + H, i + 1, 1)
ans = D.flow(0, H + W + 1)
print(ans if ans < inf else -1)


from collections import deque

class EDOMONDS_KARP:

	def __init__(self, N, s, t):
		self.N = N
		self.s = s
		self.t = t
		self.cap = [[0] * N for _ in range(N)]
		self.link = [[] for _ in range(N)]

	def add_edge(self, u, v, c):
		self.cap[u][v] = c
		self.link[u].append(v)
		self.link[v].append(u)

	def max_flow(self):
		N = self.N
		s = self.s
		t = self.t
		f = 0
		flow = [[0] * N for _ in range(N)]
		while True:
			(m, prev) = self.bfs(flow)
			if m == 0:
				break
			f += m
			v = t
			while v != s:
				u = prev[v]
				flow[u][v] += m
				flow[v][u] -= m
				v = u
		return (f, flow)

	def bfs(self, flow):
		N = self.N
		s = self.s
		t = self.t
		cap = self.cap
		link = self.link
		prev = [-1] * N
		prev[s] = -2
		m = [0] * N
		m[s] = float('inf')
		q = deque([s])
		while q:
			u = q.popleft()
			for v in link[u]:
				if cap[u][v] - flow[u][v] > 0 and prev[v] == -1:
					prev[v] = u
					m[v] = min(m[u], cap[u][v] - flow[u][v])
					if v != t:
						q.append(v)
					else:
						return (m[t], prev)
		return (0, prev)
(H, W) = list(map(int, input().split()))
board = [input() for _ in range(H)]
EK = EDOMONDS_KARP(H + W + 2, 0, H + W + 1)
for h in range(H):
	for w in range(W):
		if board[h][w] == 'o':
			EK.add_edge(h + 1, w + H + 1, 1)
			EK.add_edge(w + H + 1, h + 1, 1)
		if board[h][w] == 'S':
			EK.add_edge(0, h + 1, float('inf'))
			EK.add_edge(0, w + H + 1, float('inf'))
		if board[h][w] == 'T':
			EK.add_edge(h + 1, H + W + 1, float('inf'))
			EK.add_edge(w + H + 1, H + W + 1, float('inf'))
(f, _) = EK.max_flow()
print(f if f < float('inf') else -1)


from networkx import *
(H, W) = map(int, input().split())
X = [[a for a in input()] for _ in range(H)]
G = Graph()
G.add_nodes_from(range(-2, H + W))
for i in range(H):
	for j in range(W):
		if X[i][j] == 'o':
			G.add_edge(i, j + H, capacity=1)
		elif X[i][j] == 'S':
			(si, sj) = (i, j)
		elif X[i][j] == 'T':
			(ti, tj) = (i, j)
G.add_edge(-1, si, capacity=1 << 20)
G.add_edge(-1, sj + H, capacity=1 << 20)
G.add_edge(-2, ti, capacity=1 << 20)
G.add_edge(-2, tj + H, capacity=1 << 20)
mf = maximum_flow(G, -1, -2)[0]
print(-1 if mf > 1 << 19 else mf)


from collections import deque
INF = 10 ** 9

class Dinic:

	def __init__(self, n):
		self.n = n
		self.edge = [[] for _ in range(n)]
		self.level = [None] * self.n
		self.it = [None] * self.n

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		backward = [fr, 0, forward]
		forward[2] = backward
		self.edge[fr].append(forward)
		self.edge[to].append(backward)

	def add_bidirect_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge2 = [v1, cap2, edge1]
		edge1[2] = edge2
		self.edge[v1].append(edge1)
		self.edge[v2].append(edge2)

	def bfs(self, s, t):
		self.level = [None] * self.n
		dq = deque([s])
		self.level[s] = 0
		while dq:
			v = dq.popleft()
			lv = self.level[v] + 1
			for (dest, cap, _) in self.edge[v]:
				if cap > 0 and self.level[dest] is None:
					self.level[dest] = lv
					dq.append(dest)
		return self.level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		for e in self.it[v]:
			(to, cap, rev) = e
			if cap and self.level[v] < self.level[to]:
				ret = self.dfs(to, t, min(f, cap))
				if ret:
					e[1] -= ret
					rev[1] += ret
					return ret
		return 0

	def flow(self, s, t):
		flow = 0
		while self.bfs(s, t):
			for i in range(self.n):
				self.it[i] = iter(self.edge[i])
			f = INF
			while f > 0:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
(N, M) = [int(item) for item in input().split()]
n = N + M + 2
dinic = Dinic(n)
for i in range(N):
	line = input().rstrip()
	for (j, ch) in enumerate(line):
		if ch == '.':
			pass
		elif ch == 'o':
			v1 = i + 1
			v2 = N + j + 1
			dinic.add_bidirect_edge(v1, v2, 1, 1)
		elif ch == 'S':
			v1 = i + 1
			v2 = N + j + 1
			dinic.add_edge(0, v1, INF)
			dinic.add_edge(0, v2, INF)
		elif ch == 'T':
			v1 = i + 1
			v2 = N + j + 1
			dinic.add_edge(v1, n - 1, INF)
			dinic.add_edge(v2, n - 1, INF)
ans = dinic.flow(0, n - 1)
if ans >= INF:
	print(-1)
else:
	print(ans)


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, datetime
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)
(H, W) = list(map(int, input().split()))
A = [0] * H
for i in range(H):
	A[i] = str(input())
N = H + W + 2
B = [0] * N
Start = 0
Goal = N - 1
ans = 0
lines = defaultdict(set)
cost = [[0] * N for i in range(N)]
for i in range(H):
	for j in range(W):
		if A[i][j] == 'S':
			(sx, sy) = (i, j)
			lines[0].add(i + 1)
			cost[0][i + 1] = INF
			lines[0].add(H + 1 + j)
			cost[0][H + 1 + j] = INF
		elif A[i][j] == 'T':
			(gx, gy) = (i, j)
			lines[i + 1].add(N - 1)
			cost[i + 1][N - 1] = INF
			lines[H + 1 + j].add(N - 1)
			cost[H + 1 + j][N - 1] = INF
		elif A[i][j] == 'o':
			lines[i + 1].add(H + 1 + j)
			cost[i + 1][H + 1 + j] = 1
			lines[H + 1 + j].add(i + 1)
			cost[H + 1 + j][i + 1] = 1
if sx == gx or sy == gy:
	print(-1)
	return

def Ford_Fulkerson(s):
	nonlocal lines
	nonlocal cost
	nonlocal ans
	queue = deque()
	queue.append([s, INF])
	ed = [True] * N
	ed[s] = False
	route = [0 for i in range(N)]
	route[s] = -1
	while queue:
		(s, flow) = queue.pop()
		for t in lines[s]:
			if ed[t]:
				flow = min(cost[s][t], flow)
				route[t] = s
				queue.append([t, flow])
				ed[t] = False
				if t == Goal:
					ans += flow
					break
		else:
			continue
		break
	else:
		return False
	t = Goal
	s = route[t]
	while s != -1:
		cost[s][t] -= flow
		if cost[s][t] == 0:
			lines[s].remove(t)
		if cost[t][s] == 0:
			lines[t].add(s)
		cost[t][s] += flow
		t = s
		s = route[t]
	return True
while True:
	if Ford_Fulkerson(Start):
		continue
	else:
		break
print(ans)


def main():
	import sys
	sys.setrecursionlimit(1000000)

	def add_edge(From, to, cap):
		g[From][to] = cap
		g[to][-From - 1] = 0

	def max_flow(s, t):

		def dfs(v, t, f):
			q.append(v)
			if v == t:
				return f
			used[v] += 1
			for i in range(len(gkey[v])):
				to = gkey[v][i]
				cap = g[v][to]
				if to < 0:
					to2 = -to - 1
				else:
					to2 = to
				if used[to2] or cap == 0:
					continue
				d = dfs(to2, t, min(f, cap))
				if d > 0:
					g[v][to] -= d
					g[to2][-v - 1] += d
					return d
			q.pop()
			return 0
		flow = 0
		while True:
			used = [0] * n
			q = []
			f = dfs(s, t, 10 ** 100)
			if not q:
				return flow
			flow += f
	(h, w) = list(map(int, input().split()))
	n = h + w + 2
	g = [dict() for _ in range(n)]
	for i in range(h):
		A = input()
		for j in range(w):
			if A[j] == 'o':
				add_edge(i, j + h, 1)
				add_edge(j + h, i, 1)
			elif A[j] == 'S':
				add_edge(h + w, i, 10 ** 6)
				add_edge(h + w, j + h, 10 ** 6)
			elif A[j] == 'T':
				add_edge(i, h + w + 1, 10 ** 6)
				add_edge(j + h, h + w + 1, 10 ** 6)
	gkey = [list(i.keys()) for i in g]
	ans = max_flow(h + w, h + w + 1)
	if ans >= 10 ** 6:
		print(-1)
	else:
		print(ans)
main()


import itertools
import networkx as nx
(H, W) = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
graph = nx.DiGraph()
for (h, w) in itertools.product(list(range(H)), list(range(W))):
	if A[h][w] == 'S':
		s = (h, w)
		graph.add_edge(s, (h, -1), capacity=10 ** 10)
		graph.add_edge(s, (-1, w), capacity=10 ** 10)
	elif A[h][w] == 'T':
		t = (h, w)
		graph.add_edge((h, -1), t, capacity=10 ** 10)
		graph.add_edge((-1, w), t, capacity=10 ** 10)
	elif A[h][w] == 'o':
		graph.add_edge((h, -1), (-1, w), capacity=1)
		graph.add_edge((-1, w), (h, -1), capacity=1)
ans = nx.minimum_cut_value(graph, s, t)
print(-1 if ans >= 10 ** 10 else ans)


def dfs(v, t, f, used, graph):
	if v == t:
		return f
	used[v] = True
	for to in graph[v]:
		c = graph[v][to]
		if used[to] or c == 0:
			continue
		d = dfs(to, t, min(f, c), used, graph)
		if d > 0:
			graph[v][to] -= d
			graph[to][v] += d
			return d
	return 0

def max_flow(s, t, graph):
	flow = 0
	while True:
		used = [False] * len(graph)
		f = dfs(s, t, float('inf'), used, graph)
		flow += f
		if f == 0 or f == float('inf'):
			return flow
(H, W) = map(int, input().split())
a = [input() for _ in range(H)]
a = [[s for s in a[i]] for i in range(H)]
graph = [{} for _ in range(H + W + 2)]
for h in range(H):
	for w in range(W):
		if a[h][w] == 'o':
			graph[h][H + w] = 1
			graph[H + w][h] = 1
		if a[h][w] == 'S':
			graph[H + W][h] = float('inf')
			graph[H + W][H + w] = float('inf')
			graph[h][H + W] = 0
			graph[H + w][H + W] = 0
		if a[h][w] == 'T':
			graph[H + W + 1][h] = 0
			graph[H + W + 1][H + w] = 0
			graph[h][H + W + 1] = float('inf')
			graph[H + w][H + W + 1] = float('inf')
ans = max_flow(H + W, H + W + 1, graph)
if ans == float('inf'):
	ans = -1
print(ans)


from collections import deque
from itertools import combinations

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for _ in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
INF = 10 ** 9 + 7
(t, *a) = open(0)
(h, w) = map(int, t.split())
d = Dinic(h + w + 3)
add = d.add_multi_edge
for (i, s) in enumerate(a, 1):
	for (j, t) in enumerate(s[:-1], h + 1):
		if t != '.':
			if t == 'S':
				add(0, i, INF, INF)
				add(0, j, INF, INF)
			elif t == 'T':
				add(i, h + w + 2, INF, INF)
				add(j, h + w + 2, INF, INF)
			add(i, j, 1, 1)
a = d.flow(0, h + w + 2)
print(-(a >= INF) or a)


def examC():
	ans = 0
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():

	class Dinic:

		def __init__(self, n):
			self.n = n
			self.links = [[] for _ in range(n)]
			self.depth = None
			self.progress = None

		def add_link(self, _from, to, cap):
			self.links[_from].append([cap, to, len(self.links[to])])
			self.links[to].append([0, _from, len(self.links[_from]) - 1])

		def bfs(self, s):
			depth = [-1] * self.n
			depth[s] = 0
			q = deque([s])
			while q:
				v = q.popleft()
				for (cap, to, rev) in self.links[v]:
					if cap > 0 and depth[to] < 0:
						depth[to] = depth[v] + 1
						q.append(to)
			self.depth = depth

		def dfs(self, v, t, flow):
			if v == t:
				return flow
			links_v = self.links[v]
			for i in range(self.progress[v], len(links_v)):
				self.progress[v] = i
				(cap, to, rev) = link = links_v[i]
				if cap == 0 or self.depth[v] >= self.depth[to]:
					continue
				d = self.dfs(to, t, min(flow, cap))
				if d == 0:
					continue
				link[0] -= d
				self.links[to][rev][0] += d
				return d
			return 0

		def max_flow(self, s, t):
			flow = 0
			while True:
				self.bfs(s)
				if self.depth[t] < 0:
					return flow
				self.progress = [0] * self.n
				current_flow = self.dfs(s, t, inf)
				while current_flow > 0:
					flow += current_flow
					current_flow = self.dfs(s, t, inf)
	(H, W) = LI()
	A = [SI() for _ in range(H)]
	din = Dinic(H + W + 2)
	for h in range(H):
		for w in range(W):
			if A[h][w] == 'S':
				din.add_link(0, h + W + 1, inf)
				din.add_link(0, w + 1, inf)
			elif A[h][w] == 'T':
				din.add_link(h + W + 1, H + W + 1, inf)
				din.add_link(w + 1, H + W + 1, inf)
			elif A[h][w] == 'o':
				din.add_link(h + W + 1, w + 1, 1)
				din.add_link(w + 1, h + W + 1, 1)
	ans = din.max_flow(0, H + W + 1)
	if ans >= inf:
		ans = -1
	print(ans)
	return
from decimal import getcontext, Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

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

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = dec('0.000000000001')
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}
getcontext().prec = 28
sys.setrecursionlimit(10 ** 7)
examF()


from collections import defaultdict
from collections import deque

def Ford_Fulkerson_Func(s, g, lines, cost):
	N = len(cost)
	ans = 0
	queue = deque([[s, float('inf')]])
	ed = [True] * N
	ed[s] = False
	route = [0] * N
	route[s] = -1
	while queue:
		(now, flow) = queue.pop()
		for nex in lines[now]:
			if ed[nex]:
				flow = min(cost[now][nex], flow)
				route[nex] = now
				queue.append([nex, flow])
				ed[nex] = False
				if nex == g:
					ans += flow
					break
		else:
			continue
		break
	else:
		return (False, ans)
	t = g
	s = route[t]
	while s != -1:
		cost[s][t] -= flow
		if cost[s][t] == 0:
			lines[s].remove(t)
		if cost[t][s] == 0:
			lines[t].add(s)
		cost[t][s] += flow
		t = s
		s = route[t]
	return (True, ans)

def Ford_Fulkerson(s, g, lines, cost):
	ans = 0
	while True:
		(fl, nans) = Ford_Fulkerson_Func(s, g, lines, cost)
		if fl:
			ans += nans
			continue
		else:
			break
	return ans
(H, W) = map(int, input().split())
lines = defaultdict(set)
cost = [[0] * 202 for i in range(202)]
for i in range(H):
	a = input()
	for j in range(W):
		if a[j] == 'S':
			lines[200].add(i)
			cost[200][i] = 20000
			lines[200].add(100 + j)
			cost[200][100 + j] = 20000
		elif a[j] == 'T':
			lines[i].add(201)
			cost[i][201] = 20000
			lines[100 + j].add(201)
			cost[j + 100][201] = 20000
		elif a[j] == 'o':
			lines[i].add(j + 100)
			cost[i][j + 100] = 1
			lines[j + 100].add(i)
			cost[j + 100][i] = 1
ans = Ford_Fulkerson(200, 201, lines, cost)
if ans >= 20000:
	print(-1)
else:
	print(ans)


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

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

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = SR()
	return l
mod = 1000000007

def A():
	return

def B():
	return

def C():
	return

def D():
	return

def E():
	return

def F():

	def bfs(s, g, n):
		bfs_map = [-1 for i in range(n)]
		bfs_map[s] = 0
		q = deque()
		q.append(s)
		fin = False
		while q:
			x = q.popleft()
			for y in range(n):
				if c[x][y] > 0 and bfs_map[y] < 0:
					bfs_map[y] = bfs_map[x] + 1
					if y == g:
						fin = True
						break
					q.append(y)
			if fin:
				break
		if bfs_map[g] == -1:
			return [None, 0]
		path = [None for i in range(bfs_map[g] + 1)]
		m = float('inf')
		path[bfs_map[g]] = g
		y = g
		for i in range(bfs_map[g])[::-1]:
			for x in range(n + 1):
				if c[x][y] > 0 and bfs_map[x] == bfs_map[y] - 1:
					path[i] = x
					if c[x][y] < m:
						m = c[x][y]
					y = x
					break
		return [path, m]

	def ford_fulkerson(s, g, c, n):
		while 1:
			(p, m) = bfs(s, g, n)
			if not m:
				break
			for i in range(len(p) - 1):
				c[p[i]][p[i + 1]] -= m
				c[p[i + 1]][p[i]] += m
		return sum(c[g])
	(h, w) = LI()
	a = SR(h)
	c = [[0 for i in range(h + w + 2)] for j in range(h + w + 2)]
	for y in range(h):
		for x in range(w):
			if a[y][x] == 'S':
				c[0][y + 1] = float('inf')
				c[0][h + x + 1] = float('inf')
			if a[y][x] == 'T':
				c[y + 1][h + w + 1] = float('inf')
				c[h + x + 1][h + w + 1] = float('inf')
			if a[y][x] == 'o':
				c[y + 1][h + x + 1] = 1
				c[h + x + 1][y + 1] = 1
	ans = ford_fulkerson(0, h + w + 1, c, h + w + 2)
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)

def G():
	return

def H():
	return

def __starting_point():
	F()
__starting_point()


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)
INF = 10 ** 15

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class Dinic:

	def __init__(self, n):
		self.n = n
		self.G = [[] for _ in range(n)]
		self.level = None
		self.it = None

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [-1] * self.n
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] == -1:
					level[w] = lv
					deq.append(w)
		return level[t] != -1

	def dfs(self, v, t, f):
		if v == t:
			return f
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and self.level[v] < self.level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 18
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
(h, w) = LI()
dinic = Dinic(h + w + 2)
s = SR(h)
for i in range(h):
	for j in range(w):
		if s[i][j] == 'o':
			dinic.add_multi_edge(i, h + j, 1, 1)
		elif s[i][j] == 'S':
			dinic.add_edge(h + w, i, INF)
			dinic.add_edge(h + w, h + j, INF)
		elif s[i][j] == 'T':
			dinic.add_edge(i, h + w + 1, INF)
			dinic.add_edge(h + j, h + w + 1, INF)
ans = dinic.flow(h + w, h + w + 1)
print(ans if ans < INF else -1)