#include <iostream>
#include <cassert>
#include <vector>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <cstdint>
#include <algorithm>
#include <iterator>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
uint64_t pack(vector<string> const & s) {
    uint64_t t = 0;
    repeat (i, s.size()) {
        t *= 27;
        for (char c : s[i]) {
            t *= 27;
            t += c - 'a' + 1;
        }
    }
    return t;
}
enum we_t { W, E };
template <typename It>
void step(vector<string> const & s, map<pair<int,we_t>,vector<pair<int,we_t> > > const & g, It it) {
    int x = s.size();
    repeat (i,x) {
        repeat (n,s[i].size()+1) {
            string l = s[i].substr(0, n);
            string r = s[i].substr(n);
            for (we_t p : { W, E }) {
                if ((l.empty() and p == W) or (r.empty() and p == E)) continue;
                auto v = make_pair(i,p);
                for (auto w : g.at(v)) {
                    int  j = w.first;
                    we_t q = w.second;
                    vector<string> t = s;
                    t[i]     = p == W ? r : l;
                    string u = p == W ? l : r;
                    if (p == q) reverse(u.begin(), u.end());
                    t[j] = q == W ? u + s[j] : s[j] + u;
                    *(it ++) = t;
                }
            }
        }
    }
}
map<vector<string>,int> steps(vector<string> const & s, map<pair<int,we_t>,vector<pair<int,we_t> > > const & g, int n) {
    map<vector<string>,int> ms;
    ms[s] = 0;
    vector<vector<string> > vs;
    vs.push_back(s);
    repeat (i,n) {
        vector<vector<string> > ws;
        for (auto it : vs) {
            step(it, g, back_inserter(ws));
        }
        vs.clear();
        for (auto it : ws) {
            if (not ms.count(it)) {
                ms[it] = i+1;
                vs.push_back(it);
            }
        }
    }
    return ms;
}
int main() {
    while (true) {
        int x, y; cin >> x >> y;
        if (x == 0 and y == 0) break;
        map<pair<int,we_t>,vector<pair<int,we_t> > > g;
        repeat (i,x) for (we_t j : { W, E }) g[make_pair(i,j)];
        repeat (i,y) {
            char p, P, q, Q; cin >> p >> P >> q >> Q;
            auto a = make_pair(p - '0', P == 'W' ? W : E);
            auto b = make_pair(q - '0', Q == 'W' ? W : E);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        vector<string> s(x); repeat (i,x) { cin >> s[i]; if (s[i] == "-") s[i].clear(); }
        vector<string> t(x); repeat (i,x) { cin >> t[i]; if (t[i] == "-") t[i].clear(); }
        map<vector<string>,int> s2 = steps(s, g, 2);
        map<vector<string>,int> t2 = steps(t, g, 2);
        unordered_map<uint64_t,int> t2h; // required
        for (auto it : t2) t2h[pack(it.first)] = it.second;
        int result = 6;
        for (auto it : s2) {
            uint64_t ha = pack(it.first);
            if (t2h.count(ha)) {
                result = min(result, it.second + t2h[ha]);
            }
            if (it.second == 2) {
                vector<vector<string> > s3;
                step(it.first, g, back_inserter(s3));
                for (auto that : s3) {
                    uint64_t hb = pack(that);
                    if (t2h.count(hb)) {
                        result = min(result, 1 + it.second + t2h[hb]);
                    }
                }
            }
        }
        cout << result << endl;
    }
    return 0;
}

Measured memory_bytes: 4828