### constant

MAX_D = 6

WEST = 0
EAST = 1

EW2D = { 'W' => WEST, 'E' => EAST }

### main

loop do
  x, y = gets.split.map(&:to_i)
  break if (x | y) == 0

  x2 = x * 2
  
  edges = x2.times.map{x2.times.map{nil}}
  nbrs = x2.times.map{[]}
  y.times do
    pis, qis = gets.strip.split
    pi = (pis[0].to_i << 1) + EW2D[pis[1]]
    qi = (qis[0].to_i << 1) + EW2D[qis[1]]
    edges[pi][qi] = edges[qi][pi] = true
    nbrs[pi] << qi
    nbrs[qi] << pi
  end
  #p edges

  st = []
  x.times do
    tr = gets.strip
    st << (tr == '-' ? '' : tr)
  end
  #p st

  gl = []
  x.times do
    tr = gets.strip
    gl << (tr == '-' ? '' : tr)
  end
  #p gl

  dists = Hash.new{MAX_D + 1}
  dists[st] = 0
  q = [st]

  while ! q.empty?
    u = q.shift
    #p [dists[u], u]
    
    if u == gl
      break
    end

    for i in (0...x)
      tri = u[i]
      next if tri == ''

      uiw = i * 2 + WEST
      uie = i * 2 + EAST
      nvd = dists[u] + 1
      
      for j in (0..tri.length)
        triw = tri[0...j]
        trie = tri[j...tri.length]

        if triw != ''
          for view in nbrs[uiw]
            vi = view >> 1
            vew = view & 1

            v = u.clone
            v[i] = trie
            v[vi] = (vew == WEST) ? triw.reverse + v[vi] : v[vi] + triw

            if dists[v] > nvd
              dists[v] = nvd
              q << v
            end
          end
        end

        if trie != ''
          for view in nbrs[uie]
            vi = view >> 1
            vew = view & 1

            v = u.clone
            v[i] = triw
            v[vi] = (vew == EAST) ? v[vi] + trie.reverse : trie + v[vi]

            if dists[v] > nvd
              dists[v] = nvd
              q << v
            end
          end
        end
      end
    end
  end

  puts dists[gl]
end