#include <bits/stdc++.h>
using namespace std;

#define dump(a) (cerr << #a << " = " << (a) << endl)

#define REP(i,a,b) for(int i=(a);i < (int)(b); i++)
#define rep(i,n) REP(i,0,n)
#define ALL(v) begin(v), end(v)

int x, y;
vector<pair<pair<int, bool>, pair<int, bool>>> exchanges;

typedef unsigned long long hash_t;
hash_t rolling_hash(const string &s) {
  constexpr hash_t base = 1000000007;
  hash_t res = 0;
  for(const auto &c : s) {
    res = res * base + c;
  }
  return res;
}

string to_str(const vector<string> &state) {
  string res = "";
  for(const auto &s : state) {
    res += s + ":";
  }
  return res;
}

unordered_map<hash_t, int> bfs(int limit, const vector<string> &start) {
  unordered_map<hash_t, int> res;
  queue<vector<string>> que;

  res.insert({rolling_hash(to_str(start)), 0});
  que.push(start);

  while(!que.empty()) {
    vector<string> state = que.front();
    que.pop();
    const int d = res[rolling_hash(to_str(state))];

    if(d == limit) break;

    for(const auto &element : exchanges) {
      const int p1 = element.first.first;
      const bool d1 = element.first.second;
      const int p2 = element.second.first;
      const bool d2 = element.second.second;

      const string t1 = move(state[p1]);
      const string t2 = move(state[p2]);

      // p1 -> p2
      for(int num = 1; num <= t1.size(); ++num) {
	string tmp = (d1 ? t1.substr(0, num) : t1.substr(t1.size() - num));
	if(d1 == d2) reverse(tmp.begin(), tmp.end());
	state[p1] = (d1 ? t1.substr(num) : t1.substr(0, t1.size() - num));
	state[p2] = (d2 ? tmp + t2 : t2 + tmp);

	const hash_t h = rolling_hash(to_str(state));
	if(!res.count(h)) {
	  res.insert({h, d + 1});
	  que.push(state);
	}
      }

      // p2 -> p1
      for(int num = 1; num <= t2.size(); ++num) {
	string tmp = (d2 ? t2.substr(0, num) : t2.substr(t2.size() - num));
	if(d1 == d2) reverse(tmp.begin(), tmp.end());
	state[p1] = (d1 ? tmp + t1 : t1 + tmp);
	state[p2] = (d2 ? t2.substr(num) : t2.substr(0, t2.size() - num));

	const hash_t h = rolling_hash(to_str(state));
	if(!res.count(h)) {
	  res.insert({h, d + 1});
	  que.push(state);
	}
      }

      state[p1] = move(t1);
      state[p2] = move(t2);
    }
  }

  return res;
}

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  while(cin >> x >> y && x) {
    exchanges.clear();
    exchanges.reserve(y);

    for(int i = 0; i < y; ++i) {
      string a, b;
      cin >> a >> b;

      const int p1 = a[0] - '0';
      const bool d1 = (a[1] == 'W');
      const int p2 = b[0] - '0';
      const bool d2 = (b[1] == 'W');

      exchanges.emplace_back(make_pair(p1, d1), make_pair(p2, d2));
    }

    vector<string> lines(x), goal(x);

    for(auto &e : lines) {
      cin >> e;
      if(e == "-") e = "";
    }

    for(auto &e : goal) {
      cin >> e;
      if(e == "-") e = "";
    }
    
    const auto d1 = bfs(3, lines);
    const auto d2 = bfs(2, goal);

    vector<string> tmp{"cc", "", "bbaadee"};

    int ans = 6;
    for(const auto &e1 : d2) {
      if(ans <= e1.second) continue;

      if(d1.count(e1.first)) {
	ans = min(ans, e1.second + d1.at(e1.first));
      }
    }

    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 31216