// OB会夏合宿2011 Day3 H : Palindrome Generator

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

class Node{
public:
	int diff, Lidx, Ridx, cost;
	Node(int diff, int Lidx, int Ridx, int cost) : diff(diff), Lidx(Lidx), Ridx(Ridx), cost(cost) {}
	bool operator < (const Node &nd) const { return cost < nd.cost; }
};

int main(){
	int N, M;
	// [回文からはみ出てる文字数][最左文字列の番号][最右文字列の番号]
	// 文字数 < 10 なら、左に(10-文字数)だけはみ出てる状態
	// 文字数 > 10 なら、右に(文字数-10)だけはみ出てる状態
	int dp[21][100][100];
	string str[100];
	const int INF = 1000000007;
	while(cin >> N >> M){
		for(int i=0;i<N;i++) cin >> str[i];
		vector< vector<int> > f(N, vector<int>()), b(N, vector<int>());
		for(int i=0;i<M;i++){
			int x, y; cin >> x >> y;
			f[x-1].push_back(y-1);
			b[y-1].push_back(x-1); // 逆向きグラフ
		}
		priority_queue<Node> qu;
		memset(dp, 0, sizeof(dp));
		// 各文字列について、回文の中心にできる場所を調べて初期状態に追加
		for(int i=0;i<N;i++){
			qu.push(Node(10+str[i].size(), i, i, str[i].size()));
			for(int j=0;j<str[i].size();j++){
				bool ok = true;
				for(int k=0;k<j-k;k++)
					if(str[i][k]!=str[i][j-k]) ok = false;
				if(ok) qu.push(Node(10+str[i].size()-(j+1), i, i, str[i].size()));
			}
			qu.push(Node(10-str[i].size(), i, i, str[i].size()));
			for(int j=str[i].size()-1;j>=0;j--){
				bool ok = true;
				for(int k=0;j+k<str[i].size()-k-1;k++)
					if(str[i][j+k]!=str[i][str[i].size()-k-1]) ok = false;
				if(ok) qu.push(Node(10-j, i, i, str[i].size()));
			}
		}
		bool first = false;
		while(!qu.empty()){
			Node nd = qu.top(); qu.pop();
			int diff = nd.diff, Lidx = nd.Lidx, Ridx = nd.Ridx, c = nd.cost;
			if(dp[diff][Lidx][Ridx] >= c) continue;
			// 長さが1000超えたらどっかで循環してるんじゃねという嘘っぽい考え
			if(dp[diff][Lidx][Ridx] > 1000) c = INF;
			dp[diff][Lidx][Ridx] = c;
			// 左にはみ出てたら右側に文字列を追加
			if(diff <= 10){
				for(int i=0;i<f[Ridx].size();i++){
					string back = str[Lidx];
					string fwd  = str[f[Ridx][i]];
					bool ok = true;
					int len = 10-diff;
					for(int j=0;j<min(len, (int)fwd.size());j++)
						if(back[len-1-j]!=fwd[j]) ok = false;
					if(!ok) continue;
					int nc = min(INF, c+(int)fwd.size());
					if(dp[diff+fwd.size()][Lidx][f[Ridx][i]] < nc)
						qu.push(Node(diff+fwd.size(), Lidx, f[Ridx][i], nc));
				}
			}
			// 右にはみ出てたら左側に文字列を追加
			if(diff >= 10){
				for(int i=0;i<b[Lidx].size();i++){
					string fwd  = str[Ridx];
					string back = str[b[Lidx][i]];
					bool ok = true;
					int len = diff-10;
					for(int j=0;j<min(len, (int)back.size());j++)
						if(back[back.size()-1-j]!=fwd[fwd.size()-len+j]) ok = false;
					if(!ok) continue;
					int nc = min(INF, c+(int)back.size());
					if(dp[diff-back.size()][b[Lidx][i]][Ridx] < nc)
						qu.push(Node(diff-back.size(), b[Lidx][i], Ridx, nc));
				}
			}
		}
		int mx = 0;
		// 回文のうち長さ最大のものをとる
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				mx = max(mx, dp[10][i][j]);
		cout << (mx < INF ? mx : -1) << endl;
	}
}