# frozen_string_literal: true

# MaxFlowGraph
class MaxFlow
  def initialize(n = 0)
    @n   = n
    @pos_from = []
    @pos_id = []
    @g_to = Array.new(n) { [] }
    @g_rev = Array.new(n) { [] }
    @g_cap = Array.new(n) { [] }
  end

  def add_edge(from, to, cap)
    edge_number = @pos_from.size

    @pos_from << from
    @pos_id << @g_to[from].size

    from_id = @g_to[from].size
    to_id = @g_to[to].size
    to_id += 1 if from == to

    @g_to[from] << to
    @g_rev[from] << to_id
    @g_cap[from] << cap

    @g_to[to] << from
    @g_rev[to] << from_id
    @g_cap[to] << 0

    edge_number
  end

  def push(edge)
    add_edge(*edge)
  end
  alias << push

  # return edge = [from, to, cap, flow]
  def [](i)
    from = @pos_from[i]
    id = @pos_id[i]
    to = @g_to[from][id]
    rid = @g_rev[from][id]
    [from, @g_to[from][id], @g_cap[from][id]+@g_cap[to][rid], @g_cap[to][rid]]
  end
  alias get_edge []
  alias edge []

  def edges
    (0 ... @pos_from.size).map do |i|
      from = @pos_from[i]
      id = @pos_id[i]
      to = @g_to[from][id]
      rid = @g_rev[from][id]
      [from, @g_to[from][id], @g_cap[from][id]+@g_cap[to][rid], @g_cap[to][rid]]
    end
  end

  def change_edge(i, new_cap, new_flow)
    from = @pos_from[i]
    id = @pos_id[i]
    @g_cap[from][id] = new_cap - new_flow
    @g_cap[@g_to[from][id]][@g_rev[from][id]] = new_flow
  end

  def flow(s, t, flow_limit = 1 << 64)
    level = Array.new(@n)
    iter  = Array.new(@n)
    que   = []

    flow = 0
    while flow < flow_limit
      bfs(level, que, s, t)
      break if level[t] == -1

      iter.fill(0)
      while flow < flow_limit
        f = dfs(t, flow_limit - flow, s, level, iter)
        break if f == 0

        flow += f
      end
    end

    flow
  end
  alias max_flow flow

  def min_cut(s)
    visited = Array.new(@n) { false }
    que = [s]
    while (q = que.shift)
      visited[q] = true
      @g_to.size.times do |i|
        to = @g_to[i]
        if @g_cap[q][i] > 0 && !visited[to]
          visited[to] = true
          que << to
        end
      end
    end
    visited
  end

  private

  def bfs(level, que, s, t)
    level.fill(-1)
    level[s] = 0
    que.clear
    que << s

    while (v = que.shift)
      @g_to[v].size.times do |i|
        to = @g_to[v][i]
        next if @g_cap[v][i] == 0 || level[to] >= 0

        level[to] = level[v] + 1
        return nil if to == t

        que << to
      end
    end
  end

  def dfs(v, up, s, level, iter)
    return up if v == s

    res = 0
    level_v = level[v]

    while iter[v] < @g_to[v].size
      i = iter[v]
      to = @g_to[v][i]
      cap = @g_cap[to][@g_rev[v][i]]
      if level_v > level[to] && cap > 0 then
        d = dfs(to, up-res<cap ? up-res : cap, s, level, iter)
        if d > 0 then
          @g_cap[v][i] += d
          @g_cap[to][@g_rev[v][i]] -= d
          res += d
          break if res == up
        end
      end
      iter[v] += 1
    end

    res
  end
end

MaxFlowGraph = MaxFlow
MFGraph      = MaxFlow

n, m = gets.split.map &:to_i
str = (0 ... n).map{ gets.chomp }

g = MaxFlow.new(n*m+2)
s, t = n*m, n*m+1

n.times{ |i|
  m.times{ |j|
    next if str[i][j] == '#'
    (i+j).even? ? g.add_edge(s, i*m+j, 1) : g.add_edge(i*m+j, t, 1)
    [[i+1, j], [i, j+1]].each{ |x, y|
      if x<n && y<m && str[x][y]=='.' then
        (i+j).even? ? g.add_edge(i*m+j, x*m+y, 1) : g.add_edge(x*m+y, i*m+j, 1)
      end
    }
  }
}

puts g.max_flow(s, t)

g.edges.each{ |from, to, _, f|
  if from != s && to != t && f == 1 then
    from, to = to, from if from > to
    a, b, c, d = from/m, from%m, to/m, to%m
    if a == c then
      str[a][b] = '>'
      str[c][d] = '<'
    else
      str[a][b] = 'v'
      str[c][d] = '^'
    end
  end
}

str.each{ |s| puts s }


Measured memory_bytes: 24692