#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

template <class Key, class Value>
struct HashMap {

    static const int MAXH = 999983;
    struct Edge {
        Key to;
        Value v;
        Edge *next;
    } *head[MAXH];

    void set(const Key &key, const Value &value) {

        int hv = (unsigned int)key.hash_value() % MAXH;
        Edge *p = new Edge;
        p -> to = key;
        p -> v = value;
        p -> next = head[hv];
        head[hv] = p;
    }

    const Value &get(const Key &key) {

        int hv = (unsigned int)key.hash_value() % MAXH;
        for (Edge *p = head[hv]; p; p = p -> next)
            if (p -> to == key) return p -> v;
    }

    bool exist(const Key &key) {

        int hv = (unsigned int)key.hash_value() % MAXH;
        for (Edge *p = head[hv]; p; p = p -> next)
            if (p -> to == key) return true;
        return false;
    }

    void clear() {

        for (int i = 0; i < MAXH; i++)
        {
            for (Edge *p = head[i], *np; p; p = np)
            {
                np = p -> next;
                delete p;
            }
            head[i] = NULL;
        }
    }
};

const int MAXN = 4;
const int MAXM = MAXN * MAXN * 2;
int n, m, mcnt;
bool trans[MAXN][2][MAXN][2];
//int track[MAXM][2], dir[MAXM][2];

struct State {

    vector<string> s;

    string &operator[](int x) {

        return s[x];
    }

    int hash_value() const {

        unsigned int res = 0, res0;
        for (int i = 0; i < n; i++)
        {
            res0 = 0;
            const string &ref = s[i];
            string::size_type len = ref.length();
            for (int j = 0; j < len; j++)
                res0 = res0 * 131 + ref[j];
            res = res * 13131 + res0;
        }
        return res;
    }

    bool operator==(const State &b) const {

        for (int i = 0; i < n; i++)
            if (s[i] != b.s[i]) return false;
        return true;
    }

    void go(int n0, int d0, int n1, int d1, int k) {

        string out = s[n0].substr(0, k);
        s[n0] = s[n0].erase(0, k);
        if (d0) std::swap(out, s[n0]);
        if (d0 == d1) reverse(out.begin(), out.end());
        if (d1) s[n1] += out;
        else s[n1] = out + s[n1];
    }

    void push_back(const string &b) {

        s.push_back(b);
    }
};

struct Bfs {

    queue<State> q[2], *old, *new_;
    HashMap<State, int> hash;
    int head, tail;
    Bfs *pair;

    void init() {

        hash.clear();
        for (int i = 0; i < 2; i++)
            while (!q[i].empty()) q[i].pop();
        old = q;
        new_ = q + 1;
    }

    int push(const State &ns, int step) {

        if (hash.exist(ns)) return -1;
        if (pair -> hash.exist(ns))
        {
            int t = pair -> hash.get(ns);
            return step + t; 
        }
        hash.set(ns, step);
        new_ -> push(ns);
        return -1;
    }

    int next() {

        while (!old -> empty())
        {
            State &ref = old -> front();
            int nstep = hash.get(ref) + 1;
     //       for (int i = 0; i < mcnt; i++)
            for (int f = 0; f < n; f++)
                for (int t = 0; t < n; t++)
                    for (int fd = 0; fd < 2; fd++)
                        for (int td = 0; td < 2; td++)
                            if (trans[f][fd][t][td])
            {
                string::size_type len = ref[f].length();
                for (int k = 0; k <= len; k++)
                {
                    State v = ref;
                 //   v.go(track[i][0], dir[i][0], track[i][1], dir[i][1], k);
                    v.go(f, fd, t, td, k);
                    int ret = push(v, nstep);
                    if (ret != -1) return ret;
                }
            }
            old -> pop();
        }
        swap(old, new_);
        return -1;
    }
};

Bfs ins[2];

int main() {


    for (;;)
    {
        mcnt = 0;
        scanf("%d %d", &n, &m);
        if (!n && !m) break;
        memset(trans, 0, sizeof trans);
        for (int i = 0; i < m; i++)
        {
            int f, t;
            char fd, td;
            scanf("%d%c %d%c", &f, &fd, &t, &td);
            fd = fd == 'E';
            td = td == 'E';
/*            track[mcnt][0] = f; track[mcnt][1] = t;
            dir[mcnt][0] = fd; dir[mcnt][1] = td;
            mcnt++;

            track[mcnt][0] = t; track[mcnt][1] = f;
            dir[mcnt][0] = td; dir[mcnt][1] = fd;
            mcnt++;
            */
            trans[f][fd][t][td] = true;
            trans[t][td][f][fd] = true;
        }

        State root[2];
        static char buff[20];

        for (int t = 0; t < 2; t++)
        for (int i = 0; i < n; i++)
        {
            scanf("%s", buff);
            root[t].push_back(buff);
            if (root[t][i] == "-") root[t][i] = "";
        }

        for (int i = 0; i < 2; i++) 
        {
            ins[i].init();
            ins[i].pair = ins + !i;
            swap(ins[i].old, ins[i].new_);
            ins[i].push(root[i], 0);
        }
        for (int i = 0; i < 2; i++)
            swap(ins[i].old, ins[i].new_);

        for (int i = 0;; i ^= 1)
        {
            int ret = ins[i].next();
            if (ret != -1) 
            {
                printf("%d\n", ret);
                break;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 28000