#include <iostream>
#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<deque<char> > 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<deque<char> > const & s, map<pair<int,we_t>,vector<pair<int,we_t> > > const & g, It it) {
    int x = s.size();
    repeat (i,x) {
        repeat_from (n,1,s[i].size()+1) {
            for (we_t p : { W, E }) {
                auto v = make_pair(i,p);
                for (auto w : g.at(v)) {
                    int j = w.first;
                    vector<deque<char> > t = s;
                    queue<char> u;
                    repeat (k,n) {
                        if (v.second == W) {
                            u.push(t[i].front());
                            t[i].pop_front();
                        } else {
                            u.push(t[i].back());
                            t[i].pop_back();
                        }
                    }
                    repeat (k,n) {
                        if (w.second == W) {
                            t[j].push_front(u.front());
                        } else {
                            t[j].push_back(u.front());
                        }
                        u.pop();
                    }
                    *(it ++) = t;
                }
            }
        }
    }
}
map<vector<deque<char> >,int> steps(vector<deque<char> > const & s, map<pair<int,we_t>,vector<pair<int,we_t> > > const & g, int n) {
    map<vector<deque<char> >,int> ms;
    ms[s] = 0;
    vector<vector<deque<char> > > vs;
    vs.push_back(s);
    repeat (i,n) {
        vector<vector<deque<char> > > 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<deque<char> > s(x); repeat (i,x) { string a; cin >> a; if (a == "-") a.clear(); s[i] = deque<char>(a.begin(), a.end()); }
        vector<deque<char> > t(x); repeat (i,x) { string a; cin >> a; if (a == "-") a.clear(); t[i] = deque<char>(a.begin(), a.end()); }
        map<vector<deque<char> >,int> s2 = steps(s, g, 2);
        map<vector<deque<char> >,int> t2 = steps(t, g, 2);
        unordered_map<uint64_t,int> t2h;
        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<deque<char> > > 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: 86408