Problem p03718 (python)

Fixed submission:
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = 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)
    exit()
print(F.max_flow(0,H+W+1))

Buggy submission (verdict: Runtime Error):
import sys#if RE->suspect recursion limit error
from collections import deque
sys.setrecursionlimit(10000)

class Dinic:
    """max-flow-min-cut
    faster than ford-fulkerson algorithm
    O(|V||E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        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):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def bfs(self,s:int):
        """ bfs from s
        use deque to bfs
        """
        self.level=[-1]*self.V
        Q=deque()
        self.level[s]=0
        Q.append(s)

        while Q:
            v = Q.pop()
            for i in range(len(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):

        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        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
            grid[i][j]="o"
        if grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        if grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j+H*W,i*W+j,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j,i*W+k+H*W,float("inf"))
                F.add_edge(i*W+k,i*W+j+H*W,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i,k*W+i+H*W,float("inf"))
                F.add_edge(k*W+i,j*W+i+H*W,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx,gy*W+gx+H*W))

Buggy submission (verdict: Runtime Error):
import sys#if RE->suspect recursion limit error
from collections import deque
sys.setrecursionlimit(10000)

class Dinic:
    """max-flow-min-cut
    faster than ford-fulkerson algorithm
    O(|V||E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.level=[-1]*self.V
        self.iter=[-1]*self.V
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def bfs(self,s:int):
        """ bfs from s
        use deque to bfs
        """
        self.level=[-1]*self.V
        Q=deque()
        self.level[s]=0
        Q.append(s)

        while Q:
            v = Q.pop()
            for i in range(len(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):

        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        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 = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        if grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        if grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j+H*W,i*W+j,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j,i*W+k+H*W,float("inf"))
                F.add_edge(i*W+k,i*W+j+H*W,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i,k*W+i+H*W,float("inf"))
                F.add_edge(k*W+i,j*W+i+H*W,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx,gy*W+gx+H*W))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(20002)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        if grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        if grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*100+j+10000,i*100+j,1)

for i in range(H):
    for j in range(W):
        for k in range(j):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*100+j,i*100+k+10000,float("inf"))
                F.add_edge(i*100+k,i*100+j+10000,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*100+i,k*100+i+10000,float("inf"))
                F.add_edge(k*100+i,j*100+i+10000,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*100+sx,gy*100+gx+10000))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(20002)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        if grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        if grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j+H*W,i*W+j,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j,i*W+k+H*W,float("inf"))
                F.add_edge(i*W+k,i*W+j+H*W,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i,k*W+i+H*W,float("inf"))
                F.add_edge(k*W+i,j*W+i+H*W,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx,gy*W+gx+H*W))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        if grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        if grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j+H*W,i*W+j,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j,i*W+k+H*W,float("inf"))
                F.add_edge(i*W+k,i*W+j+H*W,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i,k*W+i+H*W,float("inf"))
                F.add_edge(k*W+i,j*W+i+H*W,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx,gy*W+gx+H*W))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        if grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        if grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j+H*W,i*W+j,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j,i*W+k+H*W,float("inf"))
                F.add_edge(i*W+k,i*W+j+H*W,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i,k*W+i+H*W,float("inf"))
                F.add_edge(k*W+i,j*W+i+H*W,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx,gy*W+gx*H*W))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        if grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        if grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j,i*W+j+H*W,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j+H*W,i*W+k,float("inf"))
                F.add_edge(i*W+k+H*W,i*W+j,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i+H*W,k*W+i,float("inf"))
                F.add_edge(k*W+i+H*W,j*W+i,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx+H*W,gy*W+gx))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(H*W*2*10)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        elif grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        elif grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j,i*W+j+H*W,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j+H*W,i*W+k,float("inf"))
                F.add_edge(i*W+k+H*W,i*W+j,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i+H*W,k*W+i,float("inf"))
                F.add_edge(k*W+i+H*W,j*W+i,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx+H*W,gy*W+gx))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        elif grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        elif grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j,i*W+j+H*W,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j+H*W,i*W+k,float("inf"))
                F.add_edge(i*W+k+H*W,i*W+j,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i+H*W,k*W+i,float("inf"))
                F.add_edge(k*W+i+H*W,j*W+i,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx+H*W,gy*W+gx))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        elif grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        elif grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j,i*W+j+H*W,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j+H*W,i*W+k,1)
                F.add_edge(i*W+k+H*W,i*W+j,1)

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i+H*W,k*W+i,1)
                F.add_edge(k*W+i+H*W,j*W+i,1)




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx+H*W,gy*W+gx))

Buggy submission (verdict: Runtime Error):
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        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:
                    #decrease capacity to denote use it with d flow
                    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):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*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 = FordFulkerson(H*W)
for i in range(H):
    for j in range(W):
        if grid[i][j]!="o":
            continue
        for k in range(j+1,W):
            if grid[i][k]=="o":
                F.add_edge(i*W+j,i*W+k,1)
                F.add_edge(i*W+k,i*W+j,1)
for i in range(W):
    for j in range(H):
        if grid[j][i]!="o":
            continue
        for k in range(j+1,H):
            if grid[k][i]=="o":
                F.add_edge(j*W+i,k*W+i,1)
                F.add_edge(k*W+i,j*W+i,1)

s=-1
g=-1
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            s=i*W+j
        if grid[i][j]=="T":
            g=i*W+j

s_i = s//W
s_j = s%W
g_i = g//W
g_j = g%W

if s_i==g_i or s_j == g_j:
    print(-1)
    exit()

for i in range(H):
    for j in range(W):
        if i==s_i or j==s_j and grid[i][j]=="o":
            F.add_edge(s,i*W+j,1)
        if i==g_i or j==g_j and grid[i][j]=="o":
            F.add_edge(i*W+j,g,1)
        pass

print(F.max_flow(s,g))