#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

typedef pair<int,int> P;
typedef pair<vector<string>, int> VI;

int n;
vector<P> t[4][2];
vector<string> start, end;
map<vector<string>, int> half;

int ans;

void enumerateHalf(){
  queue<VI> open;
  open.push(VI(start, 0));
  half[start] = 0;

  while(!open.empty()){
    VI vi = open.front();
    open.pop();
    vector<string> vec = vi.first;
    int step = vi.second;

    for(int from = 0; from < n; from++){
      if(vec[from].size() == 0) continue;

      for(int cut = 0; cut < vec[from].size(); cut++){
        string cut_str[2] = {
          vec[from].substr(0, cut),
          vec[from].substr(cut)
        };
        string rev_str[2] = {cut_str[0], cut_str[1]};
        reverse(rev_str[0].begin(), rev_str[0].end());
        reverse(rev_str[1].begin(), rev_str[1].end());

        for(int from_dir = 0; from_dir < 2; from_dir++){
          if(cut_str[from_dir].size() == 0) continue;

          for(int to_idx = 0; to_idx < t[from][from_dir].size(); to_idx++){
            int to = t[from][from_dir][to_idx].first;
            int to_dir = t[from][from_dir][to_idx].second;
            vector<string> nvec = vec;

            if     (from_dir == 0 && to_dir == 0) nvec[to] = rev_str[from_dir] + nvec[to];
            else if(from_dir == 0 && to_dir == 1) nvec[to] += cut_str[from_dir];
            else if(from_dir == 1 && to_dir == 0) nvec[to] = cut_str[from_dir] + nvec[to];
            else                                  nvec[to] += rev_str[from_dir];

            nvec[from] = cut_str[!from_dir];

            map<vector<string>,int>::iterator tmp_iter = half.find(nvec);

            if(tmp_iter != half.end()) continue;
            half[nvec] = step + 1;

            if(step == 2) continue;
            open.push(VI(nvec, step + 1));
          }
        }
      }
    }
  }
}

void bfs(){
  queue<VI> open;
  open.push(VI(end, 0));

  map<vector<string>,int>::iterator tmp_iter = half.find(end);
  if(tmp_iter != half.end()) ans = min(ans, tmp_iter->second);

  while(!open.empty()){
    VI vi = open.front();
    open.pop();
    vector<string> vec = vi.first;
    int step = vi.second;

    for(int from = 0; from < n; from++){
      if(vec[from].size() == 0) continue;

      for(int cut = 0; cut < vec[from].size(); cut++){
        string cut_str[2] = {
          vec[from].substr(0, cut),
          vec[from].substr(cut)
        };
        string rev_str[2] = {cut_str[0], cut_str[1]};
        reverse(rev_str[0].begin(), rev_str[0].end());
        reverse(rev_str[1].begin(), rev_str[1].end());

        for(int from_dir = 0; from_dir < 2; from_dir++){
          if(cut_str[from_dir].size() == 0) continue;

          for(int to_idx = 0; to_idx < t[from][from_dir].size(); to_idx++){
            int to = t[from][from_dir][to_idx].first;
            int to_dir = t[from][from_dir][to_idx].second;
            vector<string> nvec = vec;

            if     (from_dir == 0 && to_dir == 0) nvec[to] = rev_str[from_dir] + nvec[to];
            else if(from_dir == 0 && to_dir == 1) nvec[to] += cut_str[from_dir];
            else if(from_dir == 1 && to_dir == 0) nvec[to] = cut_str[from_dir] + nvec[to];
            else                                  nvec[to] += rev_str[from_dir];

            nvec[from] = cut_str[!from_dir];

            map<vector<string>,int>::iterator tmp_iter = half.find(nvec);

            if(tmp_iter != half.end()){
              ans = min(ans, step + 1 + tmp_iter->second);
              continue;
            }

            if(step == 2) continue;
            open.push(VI(nvec, step + 1));
          }
        }
      }
    }
  }
}

void solve(){
  half.clear();
  enumerateHalf();

  ans = INT_MAX;
  bfs();
  cout << ans << endl;
}

int main(){
  int m;

  while(cin >> n >> m, n || m){
    for(int i = 0; i < 4; i++){
      for(int j = 0; j < 2; j++){
        t[i][j].clear();
      }
    }

    for(int i = 0; i < m; i++){
      string from, to;
      cin >> from >> to;

      int from_line = from[0] - '0';
      int from_dir = (from[1] == 'W' ? 0 : 1);
      int to_line = to[0] - '0';
      int to_dir = (to[1] == 'W' ? 0 : 1);

      t[from_line][from_dir].push_back(P(to_line, to_dir));
      t[to_line][to_dir].push_back(P(from_line, from_dir));
    }

    start.clear();
    end.clear();

    for(int i = 0; i < n; i++){
      string s;
      cin >> s;
      if(s == "-") s = "";
      start.push_back(s);
    }

    for(int i = 0; i < n; i++){
      string s;
      cin >> s;
      if(s == "-") s = "";
      end.push_back(s);
    }

    solve();
  }
}

Measured memory_bytes: 25732