#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>
#include <bitset>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;


const int MN = 1010;

int n;

vector<int> gs[MN], rgs[MN];

char ch[MN];

vector<int> nowg;

void makeg(int x) {
    nowg.clear();
    int a = x / 1000;
    int b = x % 1000;
    if (n <= max(a, b)) return;
    int id1 = a*1000 + b;
    if (ch[a] == '$' or ch[b] == '$' or ch[a] != ch[b]) return;
    for (int c: gs[a]) {
        for (int d: rgs[b]) {
            int id2 = c*1000 + d;
            if (ch[c] != ch[d]) continue;
            nowg.push_back(id2);
        }
    }
}
/**
 * SCC, ??????????????£?????????????§£????????????????????????
 *
 * ?????¨??????????§???????
 *
 * template?????°???int V?????????????????§??°
 */
template<int V>
struct SCC {
    vector<int> rg[V];
    /// i-j?????????????????????
    void add(int i, int j) {
//        g[i].push_back(j);
        rg[j].push_back(i);
    }

    vector<int> vs;
    bitset<V> used;
    void dfs(int v) {
        used[v] = true;
        makeg(v);
        auto nv = nowg;
        for (int d: nv) {
            if (used[d]) continue;
            dfs(d);
        }
        vs.push_back(v);
    }
    int res[V]; /// res[i] = ??????i????±????????????£????????????ID
//    vector<int> scc[V]; /// scc[i] = i??????????????£?????????????±?????????????
    void rdfs(int v, int k) {
        used[v] = true;
        res[v] = k;
//        scc[k].push_back(v);
        for (int d: rg[v]) {
            if (used[d]) continue;
            rdfs(d, k);
        }
    }

    /**
     * ??????0..v-1????????????SCC?????????
     *
     * ???????????¨???????????£?????????????????°???????????????
     * ???????????????????????¨res[0..v-1], scc[0..v-1]????????±?????\???
     */
    int exec(int v) {
        vs.reserve(v+1);
//        fill_n(used, v, false);
        used.reset();
        for (int i = 0; i < v; i++) {
            if (used[i]) continue;
            dfs(i);
        }
//        fill_n(used, v, false);
        used.reset();
        int k = 0;
        for (int i = vs.size()-1; i >= 0; i--) {
            if (used[vs[i]]) continue;
            rdfs(vs[i], k);
            k++;
        }
        return k;
    }
};

const int MV = 1000010;
const int INF = 1<<28;

SCC<MV> scc;

bitset<MV> SVf, SVf2;
bitset<MV> TVf, TVf2;
bitset<MV> TV2f, TV2f2;

int solve() {
    scc.exec(MV);
    for (int i = 0; i < MV; i++) {
        scc.rg[i].clear();
    }
    for (int i = 0; i < MV; i++) {
        if (SVf[i]) {
            SVf2[scc.res[i]] = true;
        }
        if (TVf[i]) {
            TVf2[scc.res[i]] = true;
        }
        if (TV2f[i]) {
            TV2f2[scc.res[i]] = true;
        }
        makeg(i);
        for (int j: nowg) {
            scc.rg[scc.res[i]].push_back(scc.res[j]);
        }
    }

    int sre = 0;
    for (int i = MV-1; i >= 0; i--) {
        int ma = -INF;
        if (TVf2[i]) ma = -1;
        if (TV2f2[i]) ma = 0;
        bool loop = false;
        for (int j: scc.rg[i]) {
            if (i == j) {
                loop = true;
                continue;
            }
            if (scc.res[j] == -INF) continue;
            ma = max(ma, scc.res[j]+2);
        }
        if (ma < -INF/2) ma = -INF;
        if (ma == -INF) {
            scc.res[i] = -INF;
            continue;
        }
        if (loop) ma = INF;
        scc.res[i] = ma;
        if (ma == -INF) continue;
        if (SVf2[i]) {
            sre = max(sre, ma+2);
        }
    }
    if (sre > INF/2) sre = -1;
    return sre;
}

int main() {
    static int sz[MN];
    static bool fi[MN] = {}, la[MN] = {};
    fill_n(ch, MN, '$');

    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        sz[i] = (int)s.size();
        for (int j = 0; j < sz[i]; j++) {
            ch[i*10 + j] = s[j];
        }
        for (int j = 0; j < sz[i]-1; j++) {
            gs[i*10+j].push_back(i*10+j+1);
            rgs[i*10+j+1].push_back(i*10+j);
        }
        fi[i*10] = true;
        la[i*10 + sz[i] - 1] = true;
    }

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y; x--; y--;
        gs[x*10+sz[x]-1].push_back(y*10);
        rgs[y*10].push_back(x*10+sz[x]-1);
    }

    n *= 10;

    // fill_n(scc.res, MV, 0);
    // for (int a = 0; a < n; a++) {
    //     for (int b = 0; b < n; b++) {
    //         int id1 = a*1000 + b;
    //         if (ch[a] == '$' or ch[b] == '$' or ch[a] != ch[b]) continue;
    //         bool islast = false;
    //         for (int c: gs[a]) {
    //             if (c == b) {
    //                 islast = true;
    //             }
    //             for (int d: rgs[b]) {
    //                 int id2 = c*1000 + d;
    //                 if (ch[c] != ch[d]) continue;
    //                 scc.res[id1]++;
    //             }
    //         }
    //     }
    // }
    // for (int i = 0; i < MV; i++) {
    //     scc.g[i].reserve(scc.res[i]);
    // }
    // fill_n(scc.res, MV, 0);

    // for (int a = 0; a < n; a++) {
    //     for (int b = 0; b < n; b++) {
    //         int id1 = a*1000 + b;
    //         if (ch[a] == '$' or ch[b] == '$' or ch[a] != ch[b]) continue;
    //         bool islast = false;
    //         for (int c: gs[a]) {
    //             if (c == b) {
    //                 islast = true;
    //             }
    //             for (int d: rgs[b]) {
    //                 int id2 = c*1000 + d;
    //                 if (ch[c] != ch[d]) continue;
    //                 scc.res[id2]++;
    //             }
    //         }
    //     }
    // }
    // for (int i = 0; i < MV; i++) {
    //     scc.rg[i].reserve(scc.res[i]);
    // }

    for (int a = 0; a < n; a++) {
        for (int b = 0; b < n; b++) {
            int id1 = a*1000 + b;
            if (ch[a] == '$' or ch[b] == '$' or ch[a] != ch[b]) continue;
            if (fi[a] and la[b]) {
                SVf[id1] = true;
            }
            if (a == b) {
                TVf[id1] = true;
            }
            bool islast = false;
            for (int c: gs[a]) {
                if (c == b) {
                    islast = true;
                }
                for (int d: rgs[b]) {
                    int id2 = c*1000 + d;
                    if (ch[c] != ch[d]) continue;
                    scc.add(id1, id2);
                }
            }
            if (islast) {
                TV2f[id1] = true;
            }
        }
    }
/*    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            makeg(i*1000+j);
            assert(nowg.size() == scc.g[i*1000+j].size());
        }
    }*/
    cout << solve() << endl;
    return 0;
}

Measured memory_bytes: 43864