#include<stdio.h>
#include<string>
#include<cstring>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
struct NODE{
    int lid ,llen;
    int rid, rlen;
    string rem;
    NODE(){}
    NODE(int _l,int _ll ,int _r,int _rl,string &s){
        lid = _l;llen = _ll;rid =_r;rlen = _rl;rem = s;
    }
};
bool operator<(const NODE &a,const NODE &b){
    if(a.lid != b.lid) return a.lid < b.lid;
    if(a.rid != b.rid) return a.rid < b.rid;
    if(a.llen != b.llen) return a.llen < b.llen;
    if(a.rlen != b.rlen) return a.rlen < b.rlen;
    return a.rem < b.rem;
}
map<NODE,int> hash;
map<NODE,int> fin;
int conn[101][101];
int n;
string str[101] , rev[101];
bool judge(string &s ,string &t){
    int r = min(t.size() , s.size());
    for(int i = 0 ,ps = 0 , pt = t.size()-1 ; i < r;i++,ps++,pt--)
        if(s[ps] != t[pt])
            return false;
    return true;
}
bool end(NODE &s){
    if(conn[s.lid][s.rid] == false) return false;
    for(int i = 0; i <s.rem.size()/2 ;i++)
        if(s.rem[i] != s.rem[s.rem.size()-i-1])
            return false;
    return true;
}
int dfs(NODE s,int dep){
    fin[s]++;
    //for(int i= 0; i< dep*2;i++)
    //    putchar('-');
    //printf("l = %d ll = %d r= %d rl = %d %s\n",s.lid,s.llen,s.rid,s.rlen,s.rem.c_str());
    if(hash.count(s) > 0 && fin[s] == 2) {
        if(hash[s] >= 0) {if(fin[s] !=0)return -2; return hash[s];}
        else{
            if(end(s)) return hash[s] = -2;
            return hash[s];
        }
    }
    hash[s] = -1;
    int ret = -1;
    if(end(s)){
        hash[s] =ret = s.rem.size();
    //    puts("ok");
    }

    if(s.llen == 0){
        for(int i = 0 ; i< n ;i++){
            if(conn[s.lid][i] && judge(str[i] , s.rem)){
                if(str[i].size() < s.rem.size()){
                    int nlen = s.rem.size() - str[i].size();
                    string nsub = s.rem.substr(0,nlen);
                    NODE ns = NODE(i , 0 , s.rid ,  nlen , nsub);
                    int ntmp = dfs(ns,dep+1);// + str[i].size();
                    if(ntmp == -2){
                        fin[s]--;
                        return hash[s] = -2;
                    }else if(ntmp == -1) continue;
                    else {
                        ret = max(ret, ntmp + (int)str[i].size()*2);
                    }
                }else{
                    int nlen = str[i].size() - s.rem.size();
                    string nsub = str[i].substr(s.rem.size());
                    NODE ns = NODE(i , nlen , s.rid , 0 ,nsub);
                    int ntmp = dfs(ns,dep+1);
                    if(ntmp == -2){
                        fin[s]--;
                        return hash[s] = -2;
                    }else if(ntmp == -1) continue;
                    else ret = max(ret , ntmp + (int)s.rem.size()*2);
                }
            }
        }
    }else{
        for(int i = 0 ; i< n ;i++){
            if(conn[i][s.rid] && judge(s.rem,rev[i])){
                //printf("jiong");
                if(rev[i].size() < s.rem.size()){
                    int nlen = s.rem.size() - rev[i].size();
                    string nsub = s.rem.substr(rev[i].size());
                    NODE ns = NODE(s.lid , nlen , i ,  0 , nsub);
                    int ntmp = dfs(ns,dep+1);// + str[i].size();
                    if(ntmp == -2){
                        fin[s]--;
                        return hash[s] = -2;
                    }else if(ntmp == -1) continue;
                    else ret = max(ret, ntmp + (int)rev[i].size()*2);
                }else{
                    int nlen = rev[i].size() - s.rem.size();
                    string nsub = rev[i].substr(0,nlen);
                    NODE ns = NODE(s.lid ,0  , i , nlen ,nsub);
                    int ntmp = dfs(ns,dep+1);
                    if(ntmp == -2){
                        return hash[s] = -2;
                    }else if(ntmp == -1) continue;
                    else ret = max(ret , ntmp + (int)s.rem.size()*2);
                }
            }
        }
    }
    //for(int i= 0; i< dep*2;i++)
    //    putchar('-');
    //printf("l = %d ll = %d r= %d rl = %d %s %d\n",s.lid,s.llen,s.rid,s.rlen,s.rem.c_str(),ret);
    fin[s]--;
    return hash[s] = ret;
}
char ts[1000];
int main(){
    //string sa = "ab" ,sb = "ba";
    //printf("%d\n",judge(sa,sb));
    int m;
    while(scanf("%d%d",&n,&m) == 2){
    memset(conn,0,sizeof(conn));
    fin.clear();
    hash.clear();
    for(int i = 0; i < n; i++){
        scanf("%s",ts);
        str[i] = ts;
        //reverse(ts,ts+strlen(ts));
        rev[i] = ts;
    }
    str[n] = "!";
    rev[n] = "!";
    for(int i = 0; i< n ;i++)
        conn[i][n] = conn[n][i] = 1;
    for(int i = 0; i < m;i++){
        int a,b;scanf("%d%d",&a,&b);
        --a;--b;
        conn[a][b] = 1;
    }
    string em = "";
    NODE start = NODE(n,0,n,0,em);
    int ret = dfs(start,0);
    if(ret == -2)
        puts("-1");
    else if(ret == -1)
        puts("0");
    else printf("%d\n",ret);
    }
    return 0;
}

Measured memory_bytes: 0