#include<iostream>
#include<queue>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define WEST 0
#define EAST 1

typedef unsigned long long ull;

class state{
public:
  string data[4];
  ull h[4];
  int cnt;
  state(){
    cnt=0;
    rep(i,4){data[i]="";h[i]=0;}
  }
  bool operator<(const state &a)const{
    rep(i,4)if (h[i] != a.h[i])return h[i] < a.h[i];
    return false;
  }
  bool operator==(const state &a)const{
    rep(i,4)if (h[i] != a.h[i])return false;
    return true;
  }
};

bool edge[4][4][2][2];//from to, from w or e, to w or e

const ull xxx=10007;
ull compute_hash(string &a){
  ull ret=0;
  rep(i,a.size()){
    ret=ret*xxx + a[i];
  }
  return ret;
}

inline void get_all_hash(state &a,int n){
  rep(i,n){
    a.h[i]=compute_hash(a.data[i]);
  }
}

inline void operate(string moveone,string stayone,
		    state &now,int me,int tar,
		    int dir,int tdir){
  if (dir == tdir){
    reverse(moveone.begin(),moveone.end());
  }
  if (tdir == EAST){
    now.data[tar]+=moveone;
  }else if (tdir == WEST){\
    now.data[tar]=moveone+now.data[tar];
  }
  now.data[me]=stayone;
}

void move(int n,state &now,set<state> & S,queue<state> &Q){
  rep(i,n){
    rep(j,now.data[i].size()+1){
      string tmp[2]={now.data[i].substr(0,j),now.data[i].substr(j)};
      rep(k,2){//which tmp[0] or tmp[1]
	rep(l,n){//target line
	  rep(m,2){//west or east
	    if (!edge[i][l][k][m])continue;
	    state next=now;
	    next.cnt++;
	    operate(tmp[k],tmp[1-k],next,i,l,k,m);
	    get_all_hash(next,n);
	    if (S.find(next) == S.end()){
	      S.insert(next);
	      Q.push(next);
	    }
	  }
	}
      }
    }
  }  
}

int bfs(int n,state ini,state goal,set<state> &G,bool fromstart){
  set<state> S;
  queue<state> Q;
  if (fromstart){
    Q.push(ini);
    S.insert(ini);
  }else {
    Q.push(goal);
    G.insert(goal);
  }

  while(!Q.empty()){
    state now = Q.front();
    Q.pop();
    /*
    cout <<"debug "<< fromstart << endl;
    rep(i,n){
      cout << now.data[i] << endl;
    }
    */

    if (fromstart){
      set<state>::iterator itr = G.find(now);
      if (itr != G.end())return now.cnt+(*itr).cnt;
    }else {
      if (now == ini)return now.cnt;
    }

    if (now.cnt ==3)continue;
    if (fromstart)move(n,now,S,Q);
    else move(n,now,G,Q);
  }
  return -1;
}

int solve(int n,state &ini,state &goal){
  set<state> Goal;
  int ans = bfs(n,ini,goal,Goal,false);
  if (ans != -1)return ans;
  ans=bfs(n,ini,goal,Goal,true);
  return ans;
}

main(){
  int n,m;
  while(cin>>n>>m&&n){
    rep(i,4)rep(j,4)rep(k,2)rep(l,2)edge[i][j][k][l]=false;
    rep(i,m){
      char tfd,ttd;
      int f,t;
      int fd,td;
      cin>>f>>tfd>>t>>ttd;
      if (tfd == 'W')fd=WEST;
      else fd=EAST;
      if (ttd == 'W')td=WEST;
      else td=EAST;
      edge[f][t][fd][td]=true;
      edge[t][f][td][fd]=true;
    }
    state ini,goal;
    rep(i,n){
      cin>>ini.data[i];
      if (ini.data[i] == "-")ini.data[i]="";
    }
    rep(i,n){
      cin>>goal.data[i];
      if (goal.data[i] == "-")goal.data[i]="";
    }
    get_all_hash(ini,n);
    get_all_hash(goal,n);
    
    cout << solve(n,ini,goal) << endl;
  }
}

Measured memory_bytes: 69000