#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <cassert>
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
#include <functional>
#include <utility>
#include <stack>

/* vector<Edge> とその配列で名前変えたほうがいいかも */
/* 辺の重複、自己ループ、辺の削除(負の辺の判定含め) */
/* 辺の探索 */
/* 経路復元 */

using CostType = long long;

struct Edge_ToCost {
	int to;
	CostType cost;
	Edge_ToCost(int to, CostType cost);

	static int Compare_by_cost(const Edge_ToCost& left, const Edge_ToCost& right);

	struct GreaterCost {
		bool operator()(const Edge_ToCost& left, const Edge_ToCost& right);
	};
};

struct Edge_FromToCost {
	int from;
	int to;
	CostType cost;
	Edge_FromToCost(int from, int to, CostType cost);

	static int Compare_by_cost(const Edge_FromToCost& left, const Edge_FromToCost& right);

	struct GreaterCost {
		bool operator()(const Edge_FromToCost& left, const Edge_FromToCost& right);
	};
	struct LessCost {
		bool operator()(const Edge_FromToCost& left, const Edge_FromToCost& right);
	};
};


/* 多重辺、自己ループはない仕様 */
/* 頂点に何かが割り振られているときもあるよね */
class GraphAsListImpl {
public:
	using Edge = Edge_ToCost;
	using List = std::vector<Edge>;
	using Iterator = List::iterator;
	using ConstIterator = List::const_iterator;

protected:
	List* graph_p_m;
	int size_m;

	void Copy(const GraphAsListImpl& other);
	bool Is_valid_vertex(int vertex) const;
public:
	GraphAsListImpl();
	GraphAsListImpl(int size);
	GraphAsListImpl(const GraphAsListImpl& other);
	~GraphAsListImpl();

	GraphAsListImpl& operator=(const GraphAsListImpl& other);
	const List& operator[](int index) const;

	int Size() const;
	void Add(int from, int to, CostType cost, bool bidirected = false);
	Iterator Find(int from, int to);
	ConstIterator Find(int from, int to) const;
	bool Erase(int from, int to);
};

class GraphAsListBidirected;
class GraphAsList {
public:
	using Edge = GraphAsListImpl::Edge;
	using List = GraphAsListImpl::List;
	using Iterator = GraphAsListImpl::Iterator;
	using ConstIterator = GraphAsListImpl::ConstIterator;
private:
	GraphAsListImpl graph_impl_m;
public:
	GraphAsList();
	GraphAsList(int size);
	GraphAsList(const GraphAsList& other);
	GraphAsList(const GraphAsListBidirected& other);
	~GraphAsList();

	GraphAsList& operator=(const GraphAsList& other);
	const List& operator[](int index) const;

	int Size() const;
	void Add(int from, int to, CostType cost = 1, bool bidirected = false);
	Iterator Find(int from, int to);
	ConstIterator Find(int from, int to) const;
	bool Erase(int from, int to, bool bidirected = false);
};


class GraphAsListBidirected {
public:
	/* メンバ関数に対する friend は記述の順番に注意 */
	friend GraphAsList::GraphAsList(const GraphAsListBidirected& other);

	using Edge = GraphAsListImpl::Edge;
	using List = GraphAsListImpl::List;
	using Iterator = GraphAsListImpl::Iterator;
	using ConstIterator = GraphAsListImpl::ConstIterator;
private:
	GraphAsListImpl graph_impl_m;
public:
	GraphAsListBidirected();
	GraphAsListBidirected(int size);
	GraphAsListBidirected(const GraphAsListBidirected& other);
	~GraphAsListBidirected();

	GraphAsListBidirected& operator=(const GraphAsListBidirected& other);
	const List& operator[](int index) const;

	int Size() const;
	void Add(int vertex1, int vertex2, CostType cost = 1);
	std::pair<Iterator, Iterator> Find(int vertex1, int vertex2);
	std::pair<ConstIterator, ConstIterator> Find(int vertex1, int vertex2) const;
	bool Erase(int vertex1, int vertex2);
};

/* 強連結成分分解 */
class SCCsCalculator {
	GraphAsList graph_m;

	int current_m;
	std::vector<int> index_m;
	std::vector<int> lowlink_m;
	std::vector<bool> on_stack_m;
	std::stack<int> stack_m;

	std::vector<std::vector<int>> SCCs_m;

	void Calc_sub_rec(int from);
	void Calc_sub(int start);

	static const int UNVISITED = -1;
public:
	SCCsCalculator(const GraphAsList& graph);
	std::vector<std::vector<int>> Calc();
};

/* 連結性を仮定 */
class LowlinkCalculator {
public:
	using Edge = Edge_FromToCost;
private:
	GraphAsListBidirected graph_m;

	int current_m;
	std::vector<int> index_m;
	std::vector<int> lowlink_m;
	std::vector<int> parent_m;
	//Tree childs;

	void Calc_sub_rec(int from, int parent);
	void Calc_sub(int start);

	static const int UNVISITED = -1;
public:
	LowlinkCalculator(const GraphAsListBidirected& graph);
	void Calc();
	std::vector<Edge> Bridges();
	std::vector<int> Articulations();
};



struct GraphQueueElement {
	CostType distance_m;
	int vertex_m;

	static int Compare(const GraphQueueElement& left, const GraphQueueElement& right);

	GraphQueueElement(CostType distance, int vertex);
	GraphQueueElement(const GraphQueueElement&) = default;
};
bool operator<(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator>(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator<=(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator>=(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator==(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator!=(const GraphQueueElement& left, const GraphQueueElement& right);

std::vector<CostType> Dijkstra(const GraphAsList& graph, int start);
GraphAsListBidirected Prim(const GraphAsListBidirected& graph_arg);
GraphAsListBidirected Kruskal(const GraphAsListBidirected& graph);

#endif
#pragma warning(disable:4996)
#if ONLY_MY_ENVIR
#include "Graph.h"
#include "UnionFind.h"
#endif

#include <queue>

/*-----------------------------------*/
/*---------   Edge_ToCost   ---------*/
/*-----------------------------------*/

Edge_ToCost::Edge_ToCost(int to, CostType cost)
	: to(to), cost(cost) {
}

int Edge_ToCost::Compare_by_cost(const Edge_ToCost& left, const Edge_ToCost& right) {
	if (left.cost > right.cost) return 1;
	if (left.cost < right.cost) return -1;
	if (left.to > right.to) return 1;
	if (left.to < right.to) return -1;
	return 0;
}

bool Edge_ToCost::GreaterCost::operator()(const Edge_ToCost& left, const Edge_ToCost& right) {
	return Compare_by_cost(left, right) > 0;
}

/*---------------------------------------*/
/*---------   Edge_FromToCost   ---------*/
/*---------------------------------------*/

Edge_FromToCost::Edge_FromToCost(int from, int to, CostType cost)
	:from(from), to(to), cost(cost) {
}

int Edge_FromToCost::Compare_by_cost(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	if (left.cost > right.cost) return 1;
	if (left.cost < right.cost) return -1;
	if (left.from > right.from) return 1;
	if (left.from < right.from) return -1;
	if (left.to > right.to) return 1;
	if (left.to < right.to) return -1;
	return 0;
}

bool Edge_FromToCost::GreaterCost::operator()(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	return Compare_by_cost(left, right) > 0;
}

bool Edge_FromToCost::LessCost::operator()(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	return Compare_by_cost(left, right) < 0;
}


/*---------------------------------------*/
/*---------   GraphAsListImpl   ---------*/
/*---------------------------------------*/

void GraphAsListImpl::Copy(const GraphAsListImpl& other) {
	if (graph_p_m == other.graph_p_m) return;
	delete[] graph_p_m;
	size_m = other.size_m;
	graph_p_m = new List[size_m];
	std::copy(other.graph_p_m, other.graph_p_m + size_m, graph_p_m);
}

bool GraphAsListImpl::Is_valid_vertex(int vertex) const {
	return vertex >= 0 && vertex <= size_m;
}

GraphAsListImpl::GraphAsListImpl()
	:size_m(0), graph_p_m(nullptr) {
}

GraphAsListImpl::GraphAsListImpl(int size)
	: size_m(size) {
	graph_p_m = new List[size_m];
}

GraphAsListImpl::GraphAsListImpl(const GraphAsListImpl& other)
	: GraphAsListImpl() {
	Copy(other);
}

GraphAsListImpl::~GraphAsListImpl() {
	delete[] graph_p_m;
}

GraphAsListImpl& GraphAsListImpl::operator=(const GraphAsListImpl& other) {
	Copy(other);
	return *this;
}

const GraphAsListImpl::List& GraphAsListImpl::operator[](int index) const {
	return graph_p_m[index];
}

int GraphAsListImpl::Size() const {
	return size_m;
}

void GraphAsListImpl::Add(int from, int to, CostType cost, bool bidirected) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	if (bidirected) {
		Add(from, to, cost, false);
		Add(to, from, cost, false);
		return;
	}
	graph_p_m[from].push_back(Edge(to, cost));
}

GraphAsListImpl::Iterator GraphAsListImpl::Find(int from, int to) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	for (auto it = list.begin(); it != list.end(); ++it) {
		if (it->to == to) return it;
	}
	return list.end();
}

GraphAsListImpl::ConstIterator GraphAsListImpl::Find(int from, int to) const {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	for (auto it = list.begin(); it != list.end(); ++it) {
		if (it->to == to) return it;
	}
	return list.end();
}

bool GraphAsListImpl::Erase(int from, int to) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	auto it = Find(from, to);
	if (it == graph_p_m[from].end()) return false;
	list.erase(it);
	return true;
}

/*---------------------------*/
/*-----   GraphAsList   -----*/
/*---------------------------*/

GraphAsList::GraphAsList() : graph_impl_m() {}
GraphAsList::GraphAsList(int size) : graph_impl_m(size) {}
GraphAsList::GraphAsList(const GraphAsList& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsList::GraphAsList(const GraphAsListBidirected& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsList::~GraphAsList() {}
GraphAsList& GraphAsList::operator=(const GraphAsList& other) {
	graph_impl_m = other.graph_impl_m;
	return *this;
}

const GraphAsList::List& GraphAsList::operator[](int index) const {
	return graph_impl_m[index];
}

int GraphAsList::Size() const {
	return graph_impl_m.Size();
}

void GraphAsList::Add(int from, int to, CostType cost, bool bidirected) {
	graph_impl_m.Add(from, to, cost, bidirected);
}

GraphAsList::Iterator GraphAsList::Find(int from, int to) {
	return graph_impl_m.Find(from, to);
}

GraphAsList::ConstIterator GraphAsList::Find(int from, int to) const {
	return graph_impl_m.Find(from, to);
}

bool GraphAsList::Erase(int from, int to, bool bidirected) {
	if (bidirected) graph_impl_m.Erase(from, to) && graph_impl_m.Erase(to, from);
	return graph_impl_m.Erase(from, to);
}

/*-------------------------------------*/
/*-----   GraphAsListBidirected   -----*/
/*-------------------------------------*/

GraphAsListBidirected::GraphAsListBidirected() : graph_impl_m() {}
GraphAsListBidirected::GraphAsListBidirected(int size) : graph_impl_m(size) {}
GraphAsListBidirected::GraphAsListBidirected(const GraphAsListBidirected& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsListBidirected::~GraphAsListBidirected() {}

GraphAsListBidirected& GraphAsListBidirected::operator=(const GraphAsListBidirected& other) {
	graph_impl_m = other.graph_impl_m;
	return *this;
}

const GraphAsListBidirected::List& GraphAsListBidirected::operator[](int index) const {
	return graph_impl_m[index];
}

int GraphAsListBidirected::Size() const {
	return graph_impl_m.Size();
}

void GraphAsListBidirected::Add(int vertex1, int vertex2, CostType cost) {
	return graph_impl_m.Add(vertex1, vertex2, cost, true);
}

std::pair<GraphAsListBidirected::Iterator, GraphAsListBidirected::Iterator>
GraphAsListBidirected::Find(int vertex1, int vertex2) {
	return make_pair(graph_impl_m.Find(vertex1, vertex2), graph_impl_m.Find(vertex2, vertex1));
}

std::pair<GraphAsListBidirected::ConstIterator, GraphAsListBidirected::ConstIterator>
GraphAsListBidirected::Find(int vertex1, int vertex2) const {
	return make_pair(graph_impl_m.Find(vertex1, vertex2), graph_impl_m.Find(vertex2, vertex1));
}

bool GraphAsListBidirected::Erase(int vertex1, int vertex2) {
	return graph_impl_m.Erase(vertex1, vertex2) && graph_impl_m.Erase(vertex2, vertex1);
}

/*--------------------------------------*/
/*---------   SCCsCalculator   ---------*/
/*--------------------------------------*/

void SCCsCalculator::Calc_sub_rec(int from) {
	index_m[from] = current_m;
	lowlink_m[from] = current_m;
	++current_m;
	stack_m.push(from);
	on_stack_m[from] = true;

	for (auto&& edge : graph_m[from]) {
		int to = edge.to;
		if (index_m[to] == UNVISITED) {
			Calc_sub_rec(to);
			lowlink_m[from] = std::min(lowlink_m[from], lowlink_m[to]);
		} else if (on_stack_m[to]) {		// この条件何のため？
			lowlink_m[from] = std::min(lowlink_m[from], index_m[to]);
		}
	}

	if (lowlink_m[from] == index_m[from]) {
		SCCs_m.push_back(std::vector<int>());
		int vertex;
		do {
			vertex = stack_m.top();
			stack_m.pop();

			on_stack_m[vertex] = false;
			SCCs_m.back().push_back(vertex);
		} while (vertex != from);
	}
}

void SCCsCalculator::Calc_sub(int start) {
	Calc_sub_rec(start);
}

SCCsCalculator::SCCsCalculator(const GraphAsList& graph)
	: graph_m(graph), current_m(0), index_m(graph.Size(), UNVISITED),
	lowlink_m(graph.Size(), UNVISITED), on_stack_m(graph.Size(), false) {
}

std::vector<std::vector<int>> SCCsCalculator::Calc() {
	const int size = graph_m.Size();
	for (int i = 0; i < size; ++i) {
		if (index_m[i] != UNVISITED) continue;
		Calc_sub(i);
	}
	return SCCs_m;
}

/*-----------------------------------------*/
/*---------   LowlinkCalculator   ---------*/
/*-----------------------------------------*/

void LowlinkCalculator::Calc_sub_rec(int from, int parent) {
	index_m[from] = current_m;
	lowlink_m[from] = current_m;
	++current_m;

	for (auto&& edge : graph_m[from]) {
		int to = edge.to;
		if (to == parent) continue;

		if (index_m[to] == UNVISITED) {
			Calc_sub_rec(to, from);
			lowlink_m[from] = std::min(lowlink_m[from], lowlink_m[to]);
			parent_m[to] = from;
		} else {
			lowlink_m[from] = std::min(lowlink_m[from], index_m[to]);
		}
	}
}

void LowlinkCalculator::Calc_sub(int start) {
	parent_m[start] = start;
	Calc_sub_rec(start, -1);
}

LowlinkCalculator::LowlinkCalculator(const GraphAsListBidirected& graph)
	: graph_m(graph), current_m(0), index_m(graph.Size(), UNVISITED), lowlink_m(graph.Size(), UNVISITED), parent_m(graph.Size()) {
}

void LowlinkCalculator::Calc() {
	const int size = graph_m.Size();
	for (int i = 0; i < size; ++i) {
		if (index_m[i] != UNVISITED) continue;
		Calc_sub(i);
	}
}

std::vector<LowlinkCalculator::Edge> LowlinkCalculator::Bridges() {
	const int size = graph_m.Size();
	std::vector<Edge> ret_vec;
	for (int i = 0; i < size; ++i) {
		int parent = parent_m[i];
		if (parent == i) continue;
		if (lowlink_m[i] > index_m[parent]) {
			int vertex1 = std::min(i, parent);
			int vertex2 = std::max(i, parent);
			ret_vec.push_back(Edge(vertex1, vertex2, 1));
		}
	}
	return ret_vec;
}

std::vector<int> LowlinkCalculator::Articulations() {
	return std::vector<int>();
}



/*----------------------------------*/
/*---------   グローバル   ---------*/
/*----------------------------------*/

int GraphQueueElement::Compare(const GraphQueueElement& left, const GraphQueueElement& right) {
	if (left.distance_m > right.distance_m) return 1;
	if (left.distance_m < right.distance_m) return -1;
	return 0;
}

GraphQueueElement::GraphQueueElement(CostType distance, int vertex)
	: distance_m(distance), vertex_m(vertex) {
}

bool operator<(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) < 0;
}

bool operator>(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) > 0;
}

bool operator<=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) <= 0;
}

bool operator>=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) >= 0;
}

bool operator==(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) == 0;
}

bool operator!=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) != 0;
}

std::vector<CostType> Dijkstra(const GraphAsList& graph, int start) {
	// assert(!Has_negative_edge());

	using Elem = GraphQueueElement;

	const int size = graph.Size();
	const CostType INF_DIST = std::numeric_limits<CostType>::max();
	std::priority_queue<Elem, std::vector<Elem>, std::greater<Elem> > que;

	std::vector<CostType> dist_arr(size, INF_DIST);
	dist_arr[start] = 0;
	que.push(Elem(0, start));

	while (!que.empty()) {
		const Elem curr_pair = que.top();
		que.pop();

		const CostType curr_dist = curr_pair.distance_m;
		const int from = curr_pair.vertex_m;

		if (curr_dist > dist_arr[from]) continue;

		for (auto&& elem : graph[from]) {
			const int to = elem.to;
			const CostType cost = elem.cost;
			const CostType new_dist = curr_dist + cost;

			if (new_dist >= dist_arr[to]) continue;
			dist_arr[to] = new_dist;
			que.push(Elem(new_dist, to));
		}
	}
	return dist_arr;
}


/* 無向グラフとみなしてプリム O(ElogE) */
GraphAsListBidirected Prim(const GraphAsListBidirected& graph_arg) {
	using Edge = Edge_FromToCost;

	const GraphAsList graph(graph_arg);
	const int size = graph.Size();
	bool* used_p = new bool[size];
	std::fill(used_p, used_p + size, false);
	std::priority_queue<Edge, std::vector<Edge>, Edge::GreaterCost> edge_queue;
	
	int start = 0;
	used_p[start] = true;
	for (auto&& edge : graph[start]) {
		edge_queue.push(Edge(start, edge.to, edge.cost));
	}

	int edge_count = 0;
	GraphAsListBidirected ret_graph(size);
	while (edge_count < size - 1) {
		if (edge_queue.empty()) throw std::runtime_error("graph must be connected");
		Edge edge = edge_queue.top(); edge_queue.pop();
		int from = edge.from;
		int to = edge.to;
		CostType cost = edge.cost;
		if (used_p[to]) continue;

		used_p[to] = true;
		ret_graph.Add(from, to, cost);
		for (auto&& new_edge : graph[to]) {
			if (used_p[new_edge.to]) continue;
			edge_queue.push(Edge(to, new_edge.to, new_edge.cost));
		}
		++edge_count;
	}
	delete[] used_p;
	return ret_graph;
}

/* 無向グラフとみなしてクラスカル O(ElogE) */
GraphAsListBidirected Kruskal(const GraphAsListBidirected& graph) {
#ifdef __UNION_FIND_H__
	using Edge = Edge_FromToCost;

	int size = graph.Size();
	UnionFindTree union_find(size);
	std::vector<Edge> edge_arr;

	for (int from = 0; from < size; ++from) {
		for (auto&& edge : graph[from]) {
			if (from > edge.to) continue;
			edge_arr.push_back(Edge(from, edge.to, edge.cost));
		}
	}
	std::sort(edge_arr.begin(), edge_arr.end(), Edge::LessCost());

	GraphAsListBidirected ret_graph(size);
	int edge_count = 0;
	for(auto&& edge : edge_arr) {
		if (edge_count == size - 1) break;
		int from = edge.from;
		int to = edge.to;
		CostType cost = edge.cost;
		if (union_find.Is_same(from, to)) continue;
		ret_graph.Add(from, to, cost);
		union_find.Unite(from, to);
		++edge_count;
	}
	return ret_graph;
#else
#endif
}
#ifndef __FLOW_SOLVER__
#define __FLOW_SOLVER__

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

#include <vector>
#include <algorithm>
#include <limits>
#include <queue>

using CapacityType = long long;
struct GraphEdgeWithReverse {
	int to_m;
	CapacityType capacity_m;
	int rev_index_m;		  // グラフの一要素(逆辺の入っている)における逆辺の添字(ポインタにする手もある)

	GraphEdgeWithReverse(int to, CapacityType capacity, int rev_index);
};

/* 本当は自動的に逆辺の容量を調整するのがよさそう */
class GraphWithReverse {
public:
	typedef GraphEdgeWithReverse Edge;
private:
	std::vector<Edge>* edges_m;
	int size_m;

public:
	GraphWithReverse(int size);
	~GraphWithReverse();

	int Size() const;
	std::vector<Edge>* Data();

	void Add(int from, int to, CapacityType capacity, bool bidirected);
};

/* 使い切り */
class FlowSolver {
	static const CapacityType INF_CAPACITY;
	static const int CANNOT_REACH;
private:
	GraphWithReverse graph_m;

	CapacityType Ford_fulkerson_sub_rec(int from, int sink, CapacityType curr_max_flow, bool* used_p);
	CapacityType Ford_fulkerson_sub(int source, int sink, bool* used_p);

	void Calc_dist(int start, int* dist_p);
	CapacityType Dinic_sub_rec(int from, int sink, CapacityType curr_max_flow, int* done_index_p, int* dist_p);
	CapacityType Dinic_sub(int source, int sink, int* done_index_p, int* dist_p);
public:
	FlowSolver(const GraphAsList& graph_arg);

	/* source, sink は頂点番号 */

	/* O(E * Maxflow) */
	CapacityType Ford_fulkerson(int source, int sink);
	/* O(E * V ** 2) */
	CapacityType Dinic(int source, int sink);
};


#endif

#ifdef ONLY_MY_ENVIR
#include "FlowSolver.h"
#endif

/*--------------------------------------------*/
/*---------   GraphEdgeWithReverse   ---------*/
/*--------------------------------------------*/

GraphEdgeWithReverse::GraphEdgeWithReverse(int to, CapacityType capacity, int rev_index)
	:to_m(to), capacity_m(capacity), rev_index_m(rev_index) {
}

GraphWithReverse::GraphWithReverse(int size)
	:size_m(size) {
	edges_m = new std::vector<Edge>[size_m];
}

GraphWithReverse::~GraphWithReverse() {
	delete[] edges_m;
}

int GraphWithReverse::Size() const {
	return size_m;
}

std::vector<GraphWithReverse::Edge>* GraphWithReverse::Data() {
	return edges_m;
}

void GraphWithReverse::Add(int from, int to, CapacityType capacity, bool bidirected) {
	if (bidirected) {
		Add(from, to, capacity, false);
		Add(to, from, capacity, false);
		return;
	}
	
	edges_m[from].push_back(Edge(to, capacity, edges_m[to].size()));
	edges_m[to].push_back(Edge(from, 0, edges_m[from].size() - 1));
}

/*----------------------------------*/
/*---------   FlowSolver   ---------*/
/*----------------------------------*/

const CapacityType FlowSolver::INF_CAPACITY = std::numeric_limits<CapacityType>::max();
const int FlowSolver::CANNOT_REACH = -1;

CapacityType FlowSolver::Ford_fulkerson_sub_rec(int from, int sink, CapacityType curr_max_flow, bool* used_p) {
	if (from == sink) return curr_max_flow;
	used_p[from] = true;

	typedef std::vector<GraphWithReverse::Edge> GraphDataType;
	GraphDataType* data_p = graph_m.Data();
	for (auto&& edge : data_p[from]) {
		if (used_p[edge.to_m] || edge.capacity_m <= 0) continue;
		CapacityType flow = Ford_fulkerson_sub_rec(edge.to_m, sink, std::min(curr_max_flow, edge.capacity_m), used_p);
		if (flow > 0) {
			edge.capacity_m -= flow;
			data_p[edge.to_m][edge.rev_index_m].capacity_m += flow;
			return flow;
		}
	}
	return 0;
}

CapacityType FlowSolver::Ford_fulkerson_sub(int source, int sink, bool* used_p) {
	const int size = graph_m.Size();
	std::fill(used_p, used_p + size, false);
	return Ford_fulkerson_sub_rec(source, sink, INF_CAPACITY, used_p);
}

void FlowSolver::Calc_dist(int start, int* dist_p) {
	typedef std::vector<GraphWithReverse::Edge> GraphDataType;
	const int size = graph_m.Size();
	std::fill(dist_p, dist_p + size, CANNOT_REACH);
	GraphDataType* data_p = graph_m.Data();

	std::queue<int> dist_queue;
	dist_p[start] = 0;
	dist_queue.push(start);
	while (!dist_queue.empty()) {
		int from = dist_queue.front(); dist_queue.pop();
		for (auto&& edge : data_p[from]) {
			if (dist_p[edge.to_m] != CANNOT_REACH || edge.capacity_m <= 0) continue;
			dist_p[edge.to_m] = dist_p[from] + 1;
			dist_queue.push(edge.to_m);
		}
	}
}

CapacityType FlowSolver::Dinic_sub_rec(int from, int sink, CapacityType curr_max_flow, int* done_index_p, int* dist_p) {
	if (from == sink) return curr_max_flow;

	typedef std::vector<GraphWithReverse::Edge> GraphDataType;
	GraphDataType* data_p = graph_m.Data();
	for (int& i = done_index_p[from]; i < data_p[from].size(); ++i) {		// i は done_index_p[from] の別名
		GraphWithReverse::Edge& edge = data_p[from][i];
		if (dist_p[edge.to_m] <= dist_p[from] || edge.capacity_m <= 0) continue;
		CapacityType flow = Dinic_sub_rec(edge.to_m, sink, std::min(curr_max_flow, edge.capacity_m), done_index_p, dist_p);
		if (flow > 0) {
			edge.capacity_m -= flow;
			data_p[edge.to_m][edge.rev_index_m].capacity_m += flow;
			return flow;
		}
	}
	return 0;
}

CapacityType FlowSolver::Dinic_sub(int source, int sink, int* done_index_p, int* dist_p) {
	return Dinic_sub_rec(source, sink, INF_CAPACITY, done_index_p, dist_p);
}

FlowSolver::FlowSolver(const GraphAsList& graph_arg)
	: graph_m(graph_arg.Size()) {
	const int size = graph_arg.Size();

	for (int from = 0; from < size; ++from) {
		for (auto&& edge : graph_arg[from]) {
			graph_m.Add(from, edge.to, edge.cost, false);
		}
	}
}

CapacityType FlowSolver::Ford_fulkerson(int source, int sink) {
	const int size = graph_m.Size();
	bool* used_p = new bool[size];
	std::fill(used_p, used_p + size, false);

	CapacityType sum_flow = 0;
	while (true) {
		CapacityType curr_flow = Ford_fulkerson_sub(source, sink, used_p);
		if (curr_flow == 0) break;
		sum_flow += curr_flow;
	}

	delete[] used_p;
	return sum_flow;
}

CapacityType FlowSolver::Dinic(int source, int sink) {
	const int size = graph_m.Size();
	int* done_index_p = new int[size];
	int* dist_p = new int[size];

	CapacityType sum_flow = 0;
	while (true) {
		Calc_dist(source, dist_p);
		if (dist_p[sink] == CANNOT_REACH) break;
		std::fill(done_index_p, done_index_p + size, 0);
		while (true) {
			CapacityType curr_flow = Dinic_sub(source, sink, done_index_p, dist_p);
			if (curr_flow == 0) break;
			sum_flow += curr_flow;
		}
	}

	delete[] done_index_p;
	delete[] dist_p;
	return sum_flow;
}
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i, a, n) for(LL i = (a), i##_max = (n); i < i##_max; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##min = (a); i >= i##min; --i)
#define ALL(arr) (arr).begin(), (arr).end()
#define FLOAT fixed << setprecision(16)
#define SPEEDUP {cin.tie(NULL); ios::sync_with_stdio(false);}
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }
template <class T>
T Next() { T buf; cin >> buf; return buf; }

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "BinaryMatrix.h"
#include "BIT.h"
#include "Factorization.h"
#include "FlowSolver.h"
#include "Graph.h"
#include "LazySegmentTree.h"
#include "Math.h"
#include "Matrix.h"
#include "MinMax.h"
#include "Position.h"
#include "Range.h"
#include "Rational.h"
#include "SegmentTree.h"
#include "SegmentTree2D.h"
#include "SuffixArray.h"
#include "Tree.h"
#include "UnionFind.h"
#include "MinCostFlowSolver.h"
#include "Bipartite.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
// template <class T>
// auto Is(const T& value) { return [value](const auto& comparand) -> bool { return comparand == value; }; }
#endif

int H, W;
string s[100];
int main() {
	cin >> H >> W;
	REP(i, 0, H) {
		cin >> s[i];
	}

	int si, sj, ti, tj;
	REP(i, 0, H) {
		REP(j, 0, W) {
			if (s[i][j] == 'S') {
				si = i;
				sj = j;
			}
			if (s[i][j] == 'T') {
				ti = i;
				tj = j;
			}
		}
	}

	if (si == ti || sj == tj) {
		cout << -1 << endl;
		return 0;
	}

	GraphAsList G(H + W + 2);
	REP(i, 0, H) {
		REP(j, 0, W) {
			if (s[i][j] == 'o') {
				G.Add(i, H + j, 1, true);
			}
		}
	}

	G.Add(H + W, si, INF);
	G.Add(H + W, H + sj, INF);
	G.Add(ti, H + W + 1, INF);
	G.Add(H + tj, H + W + 1, INF);

	FlowSolver fs(G);
	cout << fs.Dinic(H + W, H + W + 1) << endl;
	return 0;
}


Measured memory_bytes: 1920