using System;
using System.Collections.Generic;
using System.Linq;
using Debug = System.Diagnostics.Debug;
//using System.Numerics;
//using static System.Math;
using Number = System.Int64;

using C = System.Double;
using V = System.Double;

namespace Program {
    public class Solver {
        //const long MOD = (long)1e9 + 7;
        public void Solve() {
            var n = ri;
            var m = ri;
            var s = Enumerate(n, x => rs);
            var rev = Enumerate(n, x => s[x].Reverse().AsString());
            var max = Enumerate(n, x => s[x] == rev[x] ? s[x].Length : 0).Max();
            var g = Enumerate(n, x => new List<int>());
            var rrg = Enumerate(n, x => new List<int>());
            for (int i = 0; i < m; i++) {
                var x = ri - 1; var y = ri - 1;
                g[x].Add(y);
                rrg[y].Add(x);
            }

            var goal = new state() { pre = n, suf = n, pos = 0 };
            var start = new state() { pre = n, suf = n, pos = 1 };
            var set = new HashSet<state>() { };
            var RG = new HashMap<state, List<KeyValuePair<state, int>>>();
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    for (int len = 0; len <= 10; len++) {
                        if (len <= s[i].Length) {
                            //?????? L-len ??????
                            var pre = s[i].Substring(0, s[i].Length - len);
                            //????°?
                            var suf = rev[j];
                            var mi = Math.Min(pre.Length, suf.Length);
                            //pre ??¨ suf ???suffix ????????´????????????
                            if (pre.Reverse().Take(mi).AsString() == suf.Reverse().Take(mi).AsString()) {
                                var top = s[i].Substring(s[i].Length - len);
                                var state = new state() { pre = i, suf = j, pos = len };
                                set.Add(state);
                                //????°?????????°???
                                foreach (var k in rrg[j]) {
                                    if (i == k && top == top.Reverse().AsString()) RG[goal].Add(new KeyValuePair<state, int>(state, top.Length));
                                    var mii = Math.Min(top.Length, rev[k].Length);
                                    if (top.Take(mii).AsString() == rev[k].Take(mii).AsString()) {
                                        var ns = new state() { pre = i, suf = k, pos = state.pos - rev[k].Length };
                                        set.Add(ns);
                                        RG[ns].Add(new KeyValuePair<state, int>(state, 2 * mii));
                                    }

                                }
                            }

                        }
                        if (len <= s[j].Length) {
                            //??????
                            var pre = s[i];
                            //????°? L-len??????
                            var suf = rev[j].Substring(0, rev[j].Length - len);
                            var mi = Math.Min(pre.Length, suf.Length);
                            //pre ??¨ suf ???suffix ????????´????????????
                            if (suf.Reverse().Take(mi).AsString() == pre.Reverse().Take(mi).AsString()) {
                                var top = rev[j].Substring(rev[j].Length - len);
                                var state = new state() { pre = i, suf = j, pos = -len };
                                set.Add(state);
                                // ??????????????°???
                                foreach (var k in g[i]) {
                                    if (j == k && top == top.Reverse().AsString()) RG[goal].Add(new KeyValuePair<state, int>(state, top.Length));
                                    var mii = Math.Min(top.Length, s[k].Length);
                                    if (top.Take(mii).AsString() == s[k].Take(mii).AsString()) {
                                        var ns = new state() { pre = k, suf = j, pos = state.pos + s[k].Length };
                                        set.Add(ns);
                                        RG[ns].Add(new KeyValuePair<state, int>(state, 2 * mii));
                                    }

                                }
                            }
                        }
                    }
            var id = new HashMap<state, int>();
            id[goal] = 0;
            id[start] = 1;
            foreach (var x in set)
                id[x] = id.Count;

            var rg = Enumerate(id.Count, x => new List<KeyValuePair<int, int>>());
            foreach (var x in set)
                if (s[x.pre].Length - s[x.suf].Length - x.pos == 0)
                    rg[id[x]].Add(new KeyValuePair<int, int>(1, 2 * Math.Min(s[x.pre].Length, s[x.suf].Length)));
            foreach (var kv in RG)
                foreach (var a in kv.Value)
                    rg[id[kv.Key]].Add(new KeyValuePair<int, int>(id[a.Key], a.Value));
            solve(id.Count, max, rg);
        }
        void solve(int n, int max, List<KeyValuePair<int, int>>[] g) {
            //for (int i = 0; i < n; i++) foreach (var e in g[i]) Console.WriteLine($"{i} {e.Key} {e.Value}");
            var scc = new SCCGraph(n);
            for (int i = 0; i < n; i++)
                foreach (var e in g[i])
                    scc.AddEdge(i, e.Key);
            scc.Build();
            n = scc.Count;
            var g2 = Enumerate(scc.Count, x => new List<KeyValuePair<int, int>>());
            for (int i = 0; i < g.Length; i++) {
                foreach (var e in g[i])
                    if (!scc.IsSameGroup(i, e.Key)) g2[scc[i]].Add(new KeyValuePair<int, int>(scc[e.Key], e.Value));
            }
            Func<int, int> dfs = null;
            var dp = Enumerate(n, x => -1);
            dfs = pos => {
                if (dp[pos] != -1) return dp[pos];
                var ret = -1 << 20;
                if (pos == scc[1])
                    ret = 0;
                foreach (var t in g2[pos])
                    ret = Math.Max(ret, t.Value + dfs(t.Key));
                if (ret >= 0 && scc.scc[pos].Count > 1)
                    ret = 1 << 20;
                return dp[pos] = ret;
            };
            var ans = Math.Max(max, dfs(scc[0]));
            if (ans >= 1 << 20) ans = -1;
            Console.WriteLine(ans);
        }
        struct state {
            public int pre, suf, pos;
            public override string ToString() {
                return "{pre} {suf} {pos}";
            }

        }
        const long INF = 1L << 60;
        //int[] dx = { 1, 0, -1, 0 };
        //int[] dy = { 0, 1, 0, -1 };
        //*
        int ri { get { return sc.Integer(); } }
        long rl { get { return sc.Long(); } }
        double rd { get { return sc.Double(); } }
        string rs { get { return sc.Scan(); } }
        //*/

        public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
        static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
        static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
    }
}

#region main
static class Ex {
    static public string AsString(this IEnumerable<char> ie) { return new string(ie.ToArray()); }
    static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") {
        return string.Join(st, ie.Select(x => x.ToString()).ToArray());
        //return string.Join(st, ie);
    }
    static public void Main() {
        Console.SetOut(new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        var solver = new Program.Solver();
        solver.Solve();
        Console.Out.Flush();
    }
}
#endregion
#region Ex
namespace Program.IO {
    using System.Globalization;
    using System.IO;
    using System.Text;
    public class Printer: StreamWriter {
        public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
        public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
    }
    public class StreamScanner {
        public StreamScanner(Stream stream) { str = stream; }
        public readonly Stream str;
        private readonly byte[] buf = new byte[1024];
        private int len, ptr;
        public bool isEof = false;
        public bool IsEndOfStream { get { return isEof; } }
        private byte read() {
            if (isEof) return 0;
            if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
            return buf[ptr++];
        }
        public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }

        public string Scan() {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        public string ScanLine() {
            var sb = new StringBuilder();
            for (var b = Char(); b != '\n' && b != 0; b = (char)read())
                if (b != '\r') sb.Append(b);
            return sb.ToString();
        }
        public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); }
        public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); }
        public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); }
    }
}
#endregion
#region HashMap<K,V>
public class HashMap<K, V>: Dictionary<K, V>
where V : new() {
    public HashMap() : base() { }
    public HashMap(int cap) : base(cap) { }
    new public V this[K i] {
        get {
            V v;
            return TryGetValue(i, out v) ? v :
            base[i] = new V();
        }
        set { base[i] = value; }
    }
}
#endregion


#region SCCGraph
public class SCCGraph {
    int n;

    List<int>[] g;
    public List<List<int>> scc;
    int[] group;

    /// <summary>
    /// ?????£?????????????????????
    /// </summary>
    public int Count { get; private set; }

    public SCCGraph(int N) {
        n = N;
        g = new List<int>[n];
        scc = new List<List<int>>();
        for (int i = 0; i < n; i++)
            g[i] = new List<int>();
    }
    public void AddEdge(int f, int t) { g[f].Add(t); }
    public int this[int id] { get { return group[id]; } }
    public void Build() {
        Decomposite();
        scc.Reverse();
        group = new int[n];
        for (int i = 0; i < Count; i++)
            foreach (var x in scc[i]) group[x] = i;

    }
    /// <summary>
    /// ?????£?????????????§£?????????
    /// </summary>
    public int Decomposite() {
        var S = new Stack<int>(n + 2);
        var B = new Stack<int>(n + 2);
        var I = new int[n];
        var iter = new int[n];
        var s = new Stack<int>(n + 2);
        for (int i = 0; i < n; i++) {
            if (I[i] != 0) continue;
            s.Push(i);
            while (s.Count > 0) {
                DFS:
                var u = s.Peek();
                if (I[u] == 0) {
                    B.Push(I[u] = S.Count);
                    S.Push(u);
                    iter[u] = 0;
                }
                while (iter[u] < g[u].Count) {
                    var v = g[u][iter[u]++];
                    if (I[v] == 0) {
                        s.Push(v);
                        goto DFS;
                    }
                    else while (I[v] < B.Peek()) B.Pop();
                }
                if (I[u] == B.Peek()) {
                    var ns = new List<int>();
                    scc.Add(ns);
                    B.Pop();
                    while (I[u] < S.Count) {
                        var p = S.Pop();
                        ns.Add(p);
                        I[p] = n + scc.Count;
                    }
                }
                s.Pop();

            }
        }
        return Count = scc.Count;

    }
    public bool IsSameGroup(int u, int v) { return group[u] == group[v]; }
}
#endregion


Measured memory_bytes: 37680