{-# LANGUAGE MultiWayIf #-}

module Main where

import Control.Monad
import Control.Monad.Extra
import qualified Data.Array as A
import qualified Data.Array.IO as AIO
import qualified Data.Array.Unboxed as AU
import Data.Bits
import Data.Bool
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BSC8
import Data.Char
import Data.Either
import Data.Function
import qualified Data.Graph.Inductive.Graph as G
import qualified Data.Graph.Inductive.PatriciaTree as G
import qualified Data.Heap as H
import Data.IORef
import Data.Int
import Data.List
import qualified Data.Map.Strict as M
import Data.Maybe
import Data.Monoid
import Data.Ord
import qualified Data.Sequence as SQ
import qualified Data.Set as S
import Data.Tuple
import qualified Data.Vector as V
import Data.Vector.Algorithms.Search
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Debug.Trace
import GHC.Base

main = do
  --aN       <- getI
  --[aA, aB] <- getIL
  --aS       <- getLine
  [aN, aM] <- getIL
  let s = aN * aM
  let t = aN * aM + 1
  grid <- V.replicateM aN getVUC
  graphIter <- VUM.replicate (s + 2) (1 :: Int)
  VUM.unsafeWrite graphIter s 0
  VUM.unsafeWrite graphIter t 0
  iniGraph <-
    V.thaw
      =<< ( V.generateM (s + 2) $
              ( \i ->
                  let iy = div i aM
                      ix = mod i aM
                      as =
                        VU.filter
                          (\t@(iy2, ix2) -> grid V.! iy2 VU.! ix2 == '.')
                          $ aroundSquare iy ix aN aM
                      lenAs = VU.length as
                   in if i < s && grid V.! iy VU.! ix == '#'
                        then VUM.new 0
                        else
                          if
                              | i == s ->
                                let sc =
                                      VU.mapMaybe
                                        ( \aa ->
                                            if grid V.! (div (2 * aa) aM)
                                              VU.! (mod (2 * aa) aM)
                                              == '.'
                                              then
                                                Just
                                                  (2 * aa :: Int, 0 :: Int, 1 :: Int)
                                              else Nothing
                                        )
                                        $ VU.enumFromN
                                          0
                                          ( div s 2
                                              + if odd s
                                                then 1
                                                else 0
                                          )
                                 in VU.thaw sc
                              | i == t ->
                                let sc =
                                      VU.mapMaybe
                                        ( \aa ->
                                            if grid V.! (div (2 * aa + 1) aM)
                                              VU.! (mod (2 * aa + 1) aM)
                                              == '.'
                                              then
                                                Just
                                                  (2 * aa + 1 :: Int, 0 :: Int, 0 :: Int)
                                              else Nothing
                                        )
                                        $ VU.enumFromN 0 (div s 2)
                                 in VU.thaw sc
                              | even i -> do
                                gi <- VUM.unsafeRead graphIter s
                                VUM.modify graphIter succ s
                                graphY <- VUM.new (lenAs + 1)
                                VUM.unsafeWrite graphY 0 (s, gi, 0)
                                VU.imapM_
                                  ( \ii (i2y, i2x) -> do
                                      let i2 = i2y * aM + i2x
                                      gi <- VUM.unsafeRead graphIter i2
                                      VUM.modify graphIter succ i2
                                      VUM.unsafeWrite graphY (ii + 1) (i2, gi, 1)
                                  )
                                  $ as
                                return graphY
                              | odd i -> do
                                gi <- VUM.unsafeRead graphIter t
                                VUM.modify graphIter succ t
                                graphY <- VUM.new (lenAs + 1)
                                VUM.unsafeWrite graphY 0 (t, gi, 1)
                                VU.imapM_
                                  ( \ii (i2y, i2x) -> do
                                      let i2 = i2y * aM + i2x
                                      gi <- VUM.unsafeRead graphIter i2
                                      VUM.modify graphIter succ i2
                                      VUM.unsafeWrite graphY (ii + 1) (i2, gi, 0)
                                  )
                                  $ as
                                return graphY
              )
          ) ::
      IO (VM.IOVector (VUM.IOVector (Int, Int, Int)))
  posVV <-
    V.concatMap id
      <$> ( V.mapM
              ( \i -> do
                  iniGraphY <-
                    VM.unsafeRead iniGraph i ::
                      IO (VUM.IOVector (Int, Int, Int))
                  vm <-
                    ( V.mapM
                        ( \v -> do
                            (a, b, c) <-
                              VUM.unsafeRead iniGraphY v ::
                                IO (Int, Int, Int)
                            if c == 0
                              then return $ Just (a, b)
                              else return Nothing
                        )
                        $ V.enumFromN 0 (VUM.length iniGraphY)
                      )
                  return $
                    V.mapMaybe (\i -> vm V.! i) $
                      V.enumFromN 0 $
                        V.length vm
              )
              $ V.enumFromN 0 (VM.length iniGraph)
          )
  iniPos <-
    VU.thaw $
      VU.map (\i -> posVV V.! i) (VU.enumFromN 0 (V.length posVV))
  {-
  V.imapM_
    ( \i x -> do
        fx <- VU.freeze x
        print $ show i ++ ":" ++ show fx
    )
    =<< (V.freeze iniGraph)
  print =<< VU.freeze iniPos
  -}
  let graphData = aclMaxFlowGraph (aN * aM + 2) iniGraph iniPos
  --print "aclMaxFlowGraph"
  {-
  iniGraph <- V.thaw
    =<< (V.generateM (aN * aM + 2)
         $ (\i -> if
              | i >= aN * aM -> VUM.replicate
                (div (aN * aM) 2 + 1)
                (0 :: Int, 0 :: Int, 0 :: Int)
              | otherwise -> VUM.replicate 5 (0 :: Int, 0 :: Int, 0 :: Int)))
  graphData <- aclMaxFlowGraph (aN * aM + 2) (aN * aM * 6) iniGraph
  let s = aN * aM
  let t = aN * aM + 1
  grid <- V.replicateM aN getVUC
  graphDataAdd1 <- VU.foldM
    (\acc1 i -> VU.foldM
       (\acc2 j -> let v = i * aM + j
                   in if grid V.! i VU.! j == '#'
                      then return acc2
                      else if even (i + j)
                           then aclMaxFlowAddEdge acc2 s v 1
                           else aclMaxFlowAddEdge acc2 v t 1)
       acc1
       (VU.enumFromN 0 aM))
    graphData
    (VU.enumFromN 0 aN)
  graphDataAdd2@(_, _, graphLen, _, graph, _) <- VU.foldM
    (\acc1 i -> VU.foldM
       (\acc2 j -> let v0 = i * aM + j
                   in VU.foldM
                        (\acc3 k@(ky, kx)
                         -> let v1 = kx + (ky * aM)
                            in if odd (i + j) || grid V.! i VU.! j == '#'
                               then return acc3
                               else if grid V.! ky VU.! kx == '.'
                                    then aclMaxFlowAddEdge acc3 v0 v1 1
                                    else return acc3)
                        acc2
                      $ aroundSquare i j aN aM)
       acc1
       (VU.enumFromN 0 aM))
    graphDataAdd1
    (VU.enumFromN 0 aN)
  -}
  {-
  print "graph1"
  V.imapM_
    (\i x -> do
       fx <- VU.freeze x
       print $ show i ++ ":" ++ show fx)
    =<< (V.freeze graph)
  print "graphLen1"
  print =<< VU.freeze graphLen
  -}
  flow <- aclMaxFlowFlow graphData s t
  --print "aclMaxFlowFlow"
  print flow
  {-
   print "graph2"
   V.imapM_
     (\i x -> do
        fx <- VU.freeze x
        print $ show i ++ ":" ++ show fx)
     =<< (V.freeze graph)
   print "graphLen2"
   print =<< VU.freeze graphLen
  -}
  edges <- aclMaxFlowEdges graphData
  --print "aclMaxFlowEdges"
  --print edges
  --print =<< VU.freeze pos2
  newGrid <- V.thaw =<< (V.generateM aN $ \i -> VU.thaw $ grid V.! i)
  VU.mapM_
    ( \e@(from, to, cap, flow) -> do
        if from == s || to == t || flow == 0
          then return ()
          else do
            let i0 = div from aM
                j0 = mod from aM
                i1 = div to aM
                j1 = mod to aM
            newGridI0 <- VM.unsafeRead newGrid i0
            newGridI1 <- VM.unsafeRead newGrid i1
            if
                | i0 == i1 + 1 -> do
                  VUM.unsafeWrite newGridI1 j1 'v'
                  VUM.unsafeWrite newGridI0 j0 '^'
                | j0 == j1 + 1 -> do
                  VUM.unsafeWrite newGridI1 j1 '>'
                  VUM.unsafeWrite newGridI0 j0 '<'
                | i0 == i1 - 1 -> do
                  VUM.unsafeWrite newGridI0 j0 'v'
                  VUM.unsafeWrite newGridI1 j1 '^'
                | otherwise -> do
                  VUM.unsafeWrite newGridI0 j0 '>'
                  VUM.unsafeWrite newGridI1 j1 '<'
    )
    edges
  V.mapM_ (\newGridI -> putStrLn =<< VU.toList <$> VU.freeze newGridI)
    =<< V.freeze newGrid
  return ()

--雑多系
t :: Int -> (Int, Int)
t x = (x, 1)

i def f t = bool t def $ f t

shiftRCnt k = shiftRCntP k 1

shiftRCntP k c =
  let nk = shiftR k 1
   in if nk == 0
        then c
        else shiftRCntP nk (c + 1)

myVUmap f vu =
  if vu == VU.empty
    then VU.empty
    else
      VU.unfoldr
        ( \x ->
            let ret = f $ VU.head x
                tailx = VU.tail x
             in if x == VU.empty
                  then Nothing
                  else
                    if isLeft ret
                      then Just (either id id ret, tailx)
                      else Just (either id id ret, VU.empty)
        )
        vu

myVUmapM f vu =
  if vu == VU.empty
    then return VU.empty
    else
      VU.unfoldrM
        ( \x -> do
            ret <- f $ VU.head x
            let tailx = VU.tail x
            if x == VU.empty
              then return Nothing
              else
                if isLeft ret
                  then return $ Just (either id id ret, tailx)
                  else return $ Just (either id id ret, VU.empty)
        )
        vu

myVUmapM_ f vu =
  if vu == VU.empty
    then return ()
    else do
      ret1 <-
        VU.unfoldrM
          ( \x -> do
              ret2 <- f $ VU.head x
              let tailx = VU.tail x
              if x == VU.empty
                then return Nothing
                else
                  if isLeft ret2
                    then return $ Just (either id id ret2, tailx)
                    else return $ Just (either id id ret2, VU.empty)
          )
          vu
      return ()

myVUfor vu f = myVUmap f vu

myVUforM vu f = myVUmapM f vu

myVUforM_ vu f = myVUmapM_ f vu

myVUfoldl f acc vu =
  if vu == VU.empty
    then return acc
    else do
      let ret = f acc (VU.head vu)
      if isLeft ret
        then myVUfoldl f (either id id ret) (VU.tail vu)
        else return $ either id id ret

myVUfoldr f acc vu =
  if vu == VU.empty
    then return acc
    else do
      let ret = f acc (VU.last vu)
      if isLeft ret
        then myVUfoldr f (either id id ret) (VU.init vu)
        else return $ either id id ret

myVUfoldM f acc vu =
  if vu == VU.empty
    then return acc
    else do
      ret <- f acc (VU.head vu)
      if isLeft ret
        then myVUfoldM f (either id id ret) (VU.tail vu)
        else return $ either id id ret

--周りのマス
aroundSquare y x h w =
  VU.concatMap
    ( \a ->
        VU.mapMaybe
          ( \b ->
              let ya = y + a
                  xb = x + b
               in if abs a + abs b == 1
                    then
                      if ya < 0 || ya >= h || xb < 0 || xb >= w
                        then Nothing
                        else Just (ya, xb)
                    else Nothing
          )
          $ VU.enumFromN (-1) 3
    )
    $ VU.enumFromN (-1) 3

--入力系
splitReadBSC8 :: BSC8.ByteString -> [Int]
splitReadBSC8 bs =
  let (bs1, newBs) = BSC8.splitAt 1 bs
   in if newBs == BSC8.empty
        then [test $ BSC8.readInt bs1]
        else test (BSC8.readInt bs1) : splitReadBSC8 newBs
  where
    test (Just (i, _)) = i

read2DimChar :: VM.IOVector (VUM.IOVector Char) -> Int -> Int -> IO Char
read2DimChar vec y x = do
  vecY <- VM.unsafeRead vec y
  VUM.unsafeRead vecY x

write2DimChar :: VM.IOVector (VUM.IOVector Char) -> Int -> Int -> Char -> IO ()
write2DimChar vec y x t = do
  vecY <- VM.unsafeRead vec y
  VUM.unsafeWrite vecY x t

readTwoDimVec :: VM.IOVector (VUM.IOVector Int) -> Int -> Int -> IO Int
readTwoDimVec vec y x = do
  vecY <- VM.unsafeRead vec y
  VUM.unsafeRead vecY x

writeTwoDimVec :: VM.IOVector (VUM.IOVector Int) -> Int -> Int -> Int -> IO ()
writeTwoDimVec vec y x t = do
  vecY <- VM.unsafeRead vec y
  VUM.unsafeWrite vecY x t

getVUI :: IO (VU.Vector Int)
getVUI = VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine

getRepVUI :: Int -> IO (VU.Vector Int)
getRepVUI n =
  VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) . BSC8.unlines
    <$> replicateM n BSC8.getLine

getVS :: IO (V.Vector Char)
getVS = V.fromList <$> getLine

getVUC :: IO (VU.Vector Char)
getVUC = VU.fromList <$> getLine

readI :: BSC8.ByteString -> Int
readI = fst . fromJust . BSC8.readInt

readInteger :: BSC8.ByteString -> Integer
readInteger = fst . fromJust . BSC8.readInteger

readIL :: BSC8.ByteString -> [Int]
readIL = map readI . BSC8.words

readIT2 :: BSC8.ByteString -> (Int, Int)
readIT2 bs =
  let words = BSC8.words bs
   in (readI $ head words, readI $ last words)

readIT3 :: BSC8.ByteString -> (Int, Int, Int)
readIT3 bs =
  let words = BSC8.words bs
   in (readI $ head words, readI $ words !! 1, readI $ words !! 2)

getI :: IO Int
getI = readI <$> BSC8.getLine

getInteger :: IO Integer
getInteger = readInteger <$> BSC8.getLine

getIL :: IO [Int]
getIL = readIL <$> BSC8.getLine

getIT2 :: IO (Int, Int)
getIT2 = readIT2 <$> BSC8.getLine

getIT3 :: IO (Int, Int, Int)
getIT3 = readIT3 <$> BSC8.getLine

getIT2Order :: IO (Int, Int)
getIT2Order =
  getIL
    >>= \x@[xz, xo] ->
      if xz > xo
        then return (xo, xz)
        else return (xz, xo)

getNIS :: Int -> IO [(Int, BSC8.ByteString)]
getNIS 0 = return []
getNIS n = do
  [aFst, aSnd] <- BSC8.words <$> BSC8.getLine
  next <- getNIS (n - 1)
  return ((readI aFst, aSnd) : next)

il2Words :: [Int] -> String
il2Words = unwords . map show

il2Lines :: [Int] -> String
il2Lines = unlines . map show

---MaxFlow
{-aclMaxFlowGraph n = (,,) n <$> VM.replicateM n (VUM.replicate 0 (0, 0, 0))
  <*> VU.thaw VU.empty
-}
{-
  aclMaxFlowAddAllEdges graphData $ VU.singleton (from, to, cap)

bkaclMaxFlowAddAllEdges graphData@(n, graph, pos) edges = do
  (addPos, addGraphMap) <- VU.foldM
    (\acc@(accPos, accGraphMap) edge@(from, to, cap) -> if
       | from < 0 || n <= from -> error
         "aclMaxFlowAddEdge:fromを0以上nより小さい値になるように見直してください。"
       | to < 0 || n <= to -> error
         "aclMaxFlowAddEdge:toを0以上nより小さい値になるように見直してください。"
       | cap < 0 -> error
         "aclMaxFlowAddEdge:capを0以上の値になるように見直してください。"
       | otherwise -> do
         gFrom <- VM.unsafeRead graph from
         gTo <- VM.unsafeRead graph to
         let gFromSize = VUM.length gFrom
             gToSize = VUM.length gTo
             accGFrom = M.findWithDefault [] from accGraphMap
             accGTo = M.findWithDefault [] to accGraphMap
             accGFromSize = length accGFrom
             accGToSize = length accGTo
             sumGFromSize = gFromSize + accGFromSize
             sumGToSize = gToSize + accGToSize
         return
           ( (from, sumGFromSize):accPos
           , M.insert
               to
               ((from, sumGFromSize, 0):accGTo)
               (M.insert from ((to, sumGToSize, cap):accGFrom) accGraphMap)))
    ([], M.empty)
    edges
  nGraph <- V.thaw
    =<< V.mapM
      (\i -> do
         oGraph <- VU.freeze =<< VM.unsafeRead graph i
         let nGraph = oGraph
               VU.++ (VU.fromList
                      $ reverse (M.findWithDefault [] i addGraphMap))
         VU.thaw nGraph)
      (V.enumFromN 0 n)
  nPos <- VU.thaw =<< ((VU.++ VU.fromList addPos) <$> VU.freeze pos)
  return (n, nGraph, nPos)
-}
{-aclMaxFlowGraph
  :: Int -> IO (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int))
aclMaxFlowGraph n = do
  graphIni <- VM.replicate n (SQ.empty)
  return (n, graphIni, SQ.empty)

aclMaxFlowAddEdge
  :: (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int))
  -> Int
  -> Int
  -> Int
  -> IO (Int, (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int)))
aclMaxFlowAddEdge graphIniData@(iniN, iniGraph, iniPos) from to cap = if
  | from < 0 || iniN <= from -> error
    "aclMaxFlowAddEdge:fromを0以上nより小さい値になるように見直してください。"
  | to < 0 || iniN <= to -> error
    "aclMaxFlowAddEdge:toを0以上nより小さい値になるように見直してください。"
  | cap < 0 -> error
    "aclMaxFlowAddEdge:capを0以上の値になるように見直してください。"
  | otherwise -> do
    let m = SQ.length iniPos
    graphFrom <- VM.unsafeRead iniGraph from
    graphTo <- VM.unsafeRead iniGraph to
    let graphFromSize = SQ.length graphFrom
    let graphToSize = SQ.length graphTo
    VM.unsafeWrite iniGraph from (graphFrom SQ.|> (to, graphToSize, cap))
    VM.unsafeWrite iniGraph to (graphTo SQ.|> (from, graphFromSize, 0))
    return (m, (iniN, iniGraph, iniPos SQ.|> (from, graphFromSize)))

aclMaxFlowConvertIniData
  :: (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int))
  -> IO
    (Int, VM.IOVector (VUM.IOVector (Int, Int, Int)), VUM.IOVector (Int, Int))
aclMaxFlowConvertIniData graphIniData@(iniN, iniGraph, iniPos) = do
  graph <- V.thaw
    =<< (V.generateM
           iniN
           (\i -> do
              seq <- VM.unsafeRead iniGraph i
              VU.thaw
                $ VU.unfoldr
                  (\x -> let (s SQ.:< sn) = SQ.viewl x
                         in if x == SQ.empty
                            then Nothing
                            else Just (s, sn))
                  seq))
  pos <- VU.thaw
    $ VU.unfoldr
      (\x -> let (s SQ.:< sn) = SQ.viewl x
             in if x == SQ.empty
                then Nothing
                else Just (s, sn))
      iniPos
  return (iniN, graph, pos)-}
{-
aclMaxFlowGraph
  :: Int
  -> Int
  -> VM.IOVector (VUM.IOVector (Int, Int, Int))
  -> IO
    ( Int
    , Int
    , VUM.IOVector (Int)
    , Int
    , VM.IOVector (VUM.IOVector (Int, Int, Int))
    , VUM.IOVector (Int, Int))
aclMaxFlowGraph n m iniGraph = do
  pos <- VUM.replicate m (0, 0)
  graphLen <- VUM.replicate n 0
  return (n, m, graphLen, 0, iniGraph, pos)

aclMaxFlowAddEdge
  :: ( Int
     , Int
     , VUM.IOVector (Int)
     , Int
     , VM.IOVector (VUM.IOVector (Int, Int, Int))
     , VUM.IOVector (Int, Int))
  -> Int
  -> Int
  -> Int
  -> IO
    ( Int
    , Int
    , VUM.IOVector (Int)
    , Int
    , VM.IOVector (VUM.IOVector (Int, Int, Int))
    , VUM.IOVector (Int, Int))
aclMaxFlowAddEdge graphData@(n, m, graphLen, posLen, graph, pos) from to cap =
  if
    | from < 0 || n <= from -> error
      "aclMaxFlowAddEdge:fromを0以上nより小さい値になるように見直してください。"
    | to < 0 || n <= to -> error
      "aclMaxFlowAddEdge:toを0以上nより小さい値になるように見直してください。"
    | cap < 0 -> error
      "aclMaxFlowAddEdge:capを0以上の値になるように見直してください。"
    | otherwise -> do
      graphFrom <- VM.unsafeRead graph from
      graphTo <- VM.unsafeRead graph to
      graphFromSize <- VUM.unsafeRead graphLen from
      graphToSize <- VUM.unsafeRead graphLen to
      VUM.unsafeWrite graphFrom graphFromSize (to, graphToSize, cap)
      VUM.unsafeWrite graphTo graphToSize (from, graphFromSize, 0)
      VUM.unsafeWrite pos posLen (from, graphFromSize)
      VUM.unsafeModify graphLen succ from
      VUM.unsafeModify graphLen succ to
      return (n, m, graphLen, posLen + 1, graph, pos)
-}
aclMaxFlowGraph ::
  Int ->
  VM.IOVector (VUM.IOVector (Int, Int, Int)) ->
  VUM.IOVector (Int, Int) ->
  (Int, VM.IOVector (VUM.IOVector (Int, Int, Int)), VUM.IOVector (Int, Int))
aclMaxFlowGraph n iniGraph iniPos = (n, iniGraph, iniPos)

aclMaxFlowGetEdge graphData@(n, graph, pos) i =
  let m = VUM.length pos
   in if i < 0 || m <= i
        then
          error
            "aclMaxFlowAddEdge:iを0以上mより小さい値になるように見直してください。"
        else do
          posi <- VUM.unsafeRead pos i
          graphi <- VM.unsafeRead graph (fst posi)
          e@(eTo, eRev, eCap) <- VUM.unsafeRead graphi (snd posi)
          graphTo <- VM.unsafeRead graph eTo
          re@(reTo, reRev, reCap) <- VUM.unsafeRead graphTo eRev
          return (fst posi, eTo, eCap + reCap, reCap)

aclMaxFlowEdges graphData@(n, graph, pos) =
  let m = VUM.length pos
   in VU.mapM (aclMaxFlowGetEdge graphData) $ VU.enumFromN 0 m

aclMaxFlowChangeEdge graphData@(n, graph, pos) i newCap newFlow = do
  let m = VUM.length pos
  if i < 0 || m <= i
    then
      error
        "aclMaxFlowAddEdge:iを0以上mより小さい値になるように見直してください。"
    else do
      posi <- VUM.unsafeRead pos i
      graphA <- VM.unsafeRead graph (fst posi)
      e@(eTo, eRev, eCap) <- VUM.unsafeRead graphA (snd posi)
      graphB <- VM.unsafeRead graph eTo
      re@(reTo, reRev, reCap) <- VUM.unsafeRead graphB eRev
      return ()

aclMaxFlowFlow graphData@(n, graph, pos) s t =
  aclMaxFlowFlowLimit graphData s t maxInt

aclMaxFlowFlowLimit ::
  (Int, VM.IOVector (VUM.IOVector (Int, Int, Int)), VUM.IOVector (Int, Int)) ->
  Int ->
  Int ->
  Int ->
  IO Int
aclMaxFlowFlowLimit graphData@(n, graph, pos) s t flowLimit
  | s < 0 || n <= s =
    error
      "aclMaxFlowFlow:sを0以上nより小さい値になるように見直してください。"
  | t < 0 || n <= t =
    error
      "aclMaxFlowFlow:tを0以上nより小さい値になるように見直してください。"
  | otherwise = do
    levelIni <- VUM.new n :: IO (VUM.IOVector Int)
    iter <- VUM.new n :: IO (VUM.IOVector Int)
    aloop levelIni iter 0
  where
    aloop :: VUM.IOVector Int -> VUM.IOVector Int -> Int -> IO Int
    aloop levelIni iter flow = do
      --print "aloop"
      if flow >= flowLimit
        then return flow
        else do
          VUM.set levelIni (-1)
          VUM.unsafeWrite levelIni s 0
          level <- bfs levelIni (SQ.singleton s)
          levelt <- VUM.unsafeRead level t
          --print =<< VU.freeze level
          if levelt == -1
            then return flow
            else do
              VUM.set iter (-1)
              nFlow <- bloop level iter flow
              aloop levelIni iter nFlow

    bfs :: VUM.IOVector Int -> SQ.Seq (Int) -> IO (VUM.IOVector Int)
    bfs level sq
      | sq == SQ.empty = return level
      | otherwise = do
        --print "bfs"
        let (sqh SQ.:< sqt) = SQ.viewl sq
        edges <- VM.unsafeRead graph sqh
        --print =<< VU.freeze edges
        let lenEdges = VUM.length edges
        nSq <- cloop level edges 0 lenEdges sqh sqt
        bfs level nSq

    cloop ::
      VUM.IOVector Int ->
      VUM.IOVector (Int, Int, Int) ->
      Int ->
      Int ->
      Int ->
      SQ.Seq (Int) ->
      IO (SQ.Seq (Int))
    cloop level edges i lenEdges v sqt = do
      --print "cloop"
      if i >= lenEdges
        then return sqt
        else do
          edge@(to, rev, cap) <- VUM.unsafeRead edges i
          levelTo <- VUM.unsafeRead level to
          if cap == 0 || levelTo >= 0
            then cloop level edges (i + 1) lenEdges v sqt
            else do
              levelv <- VUM.unsafeRead level v
              VUM.unsafeWrite level to (levelv + 1)
              if to == t
                then return SQ.empty
                else cloop level edges (i + 1) lenEdges v (to SQ.<| sqt)

    bloop :: VUM.IOVector Int -> VUM.IOVector Int -> Int -> IO Int
    bloop level iter flow
      | flow >= flowLimit = return flow
      | otherwise = do
        --print "bloop"
        f <-
          if t == s
            then return (flowLimit - flow)
            else do
              levelV <- VUM.unsafeRead level t
              graphV <- VM.unsafeRead graph t
              let lenGraphV = VUM.length graphV
              dfs graphV lenGraphV level levelV t iter (flowLimit - flow) 0
        if f == 0
          then return flow
          else bloop level iter (flow + f)

    dfs ::
      VUM.IOVector (Int, Int, Int) ->
      Int ->
      VUM.IOVector Int ->
      Int ->
      Int ->
      VUM.IOVector Int ->
      Int ->
      Int ->
      IO Int
    dfs graphV lenGraphV level levelV v iter up res =
      do
        --print "dfs"
        VUM.modify iter succ v
        i <- VUM.unsafeRead iter v
        if i >= lenGraphV
          then return res
          else do
            edge@(to, rev, cap) <- VUM.unsafeRead graphV i
            levelTo <- VUM.unsafeRead level to
            graphTo <- VM.unsafeRead graph to
            let lenGraphTo = VUM.length graphTo
            graphToRev@(nTo, nRev, nCap) <- VUM.unsafeRead graphTo rev
            if levelV <= levelTo || nCap == 0
              then do
                dfs graphV lenGraphV level levelV v iter up res
              else do
                d <-
                  if to == s
                    then do
                      return (min (up - res) nCap)
                    else do
                      dfs
                        graphTo
                        lenGraphTo
                        level
                        levelTo
                        to
                        iter
                        (min (up - res) nCap)
                        0
                if d <= 0
                  then do
                    dfs graphV lenGraphV level levelV v iter up res
                  else do
                    edge@(to2, rev2, cap2) <- VUM.unsafeRead graphV i
                    graphToRev@(nTo2, nRev2, nCap2) <- VUM.unsafeRead graphTo rev
                    VUM.unsafeWrite graphV i (to2, rev2, cap2 + d)
                    VUM.unsafeWrite graphTo rev (nTo2, nRev2, nCap2 - d)
                    let nres = res + d
                    if nres == up
                      then do
                        return nres
                      else do
                        dfs graphV lenGraphV level levelV v iter up nres

aclMaxFlowMinCut graphData@(n, graph, pos) s = do
  visited <- VUM.replicate n False
  let sq = SQ.singleton s
  aloop visited sq
  VU.freeze visited
  where
    aloop visited sq
      | sq == SQ.empty = return ()
      | otherwise = do
        let (sqh SQ.:< sqt) = SQ.viewl sq
        VUM.unsafeWrite visited sqh True
        edges <- VM.unsafeRead graph sqh
        bloop visited edges 0 sq

    bloop visited edges i sq = do
      edge@(to, rev, cap) <- VUM.unsafeRead edges i
      visitedTo <- VUM.unsafeRead visited to
      if cap /= 0 && visitedTo == False
        then do
          VUM.unsafeWrite visited to True
          bloop visited edges i (to SQ.<| sq)
        else bloop visited edges i sq

---MinCostFlow後回し
---Convolution