#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define EMPTY 0 //空文字のインデックス
#define NUM 105
#define BALANCE 10

/*
 * diff = 右の余り-左の余り+10
 * バランスしているとき、diffは10
 *
 * */

struct Data{
	Data(int arg_next_id,int arg_add_len){
		next_node_id = arg_next_id;
		add_len = arg_add_len;
	}
	int next_node_id,add_len;
};

struct Node{

	int left_id,right_id,diff;
	vector<Data> NEXT;
};

struct Info{

	char word[11];
	int length;
};

struct State{
	State(int arg_node_id,int arg_sum_value){
		node_id = arg_node_id;
		sum_value = arg_sum_value;
	}
	int node_id,sum_value;
};

int V,E;
const int start = 0,goal = 1;
bool check[NUM][NUM];
Info info[NUM];
vector<Node> NODES;
map<pair<int,int>,int> MAP[21]; //map[diff][make_pair(left_id,right_id)] = node_id
map<pair<int,int>,int> dp[21];  //dp[diff][make_pair(left_id,right_id)] = 最大長

#define SIZE 200005

vector<int> G[SIZE];
vector<int> reverse_G[SIZE];
bool can_goal[SIZE];
bool cycle_FLG;
bool visited[SIZE];

void cycle_dfs(int start_id,int current_id){

	if(cycle_FLG)return;

	for(int i = 0; i < G[current_id].size(); i++){
		if(G[current_id][i] == start_id){

			cycle_FLG = true;
			return;
		}
		if(visited[G[current_id][i]])continue;
		visited[G[current_id][i]] = true;

		cycle_dfs(start_id,G[current_id][i]);
	}
}

void goal_dfs(int node_id){

	can_goal[node_id] = true;

	for(int i = 0; i < reverse_G[node_id].size(); i++){

		if(visited[reverse_G[node_id][i]])continue;
		visited[reverse_G[node_id][i]] = true;

		goal_dfs(reverse_G[node_id][i]);
	}
}

void start_dfs(int node_id){

	for(int i = 0; i < G[node_id].size(); i++){

		if(visited[G[node_id][i]])continue;
		visited[G[node_id][i]] = true;

		start_dfs(G[node_id][i]);
	}
}



int main(){

	scanf("%d %d",&V,&E);

	for(int i = 0; i <= V; i++){
		for(int k = 0; k <= V; k++){
			check[i][k] = false;
		}
	}

	int length;

	//空文字
	info[0].word[0] = '\0';
	info[0].length = 0;

	for(int i = 1; i <= V; i++){

		scanf("%s",info[i].word);

		for(length = 0; info[i].word[length] != '\0'; length++);

		info[i].length = length;
	}

	int from,to;

	for(int loop = 0; loop < E; loop++){

		scanf("%d %d",&from,&to);

		check[from][to] = true;
	}

	int num_nodes = 2;
	Node start_node,goal_node;

	start_node.diff = BALANCE;
	start_node.left_id = 0;
	start_node.right_id = 0;

	goal_node.diff = BALANCE;
	goal_node.left_id = 0;
	goal_node.right_id = 0;

	NODES.push_back(start_node);
	NODES.push_back(goal_node);


	//まず、スタートから遷移する最初のノードを作る

	/*★1つの単語★*/

	//全体が回文になっているものを探す。接続に制約があるので、回文になっている単語は全てノード化する

	for(int i = 1; i <= V; i++){

		bool FLG = true;
		for(int k = 0; k < info[i].length/2; k++){
			if(info[i].word[k] != info[i].word[info[i].length-1-k]){
				FLG = false;
				break;
			}
		}

		if(FLG){

			//ノード作成
			Node node;

			node.left_id = i;
			node.right_id = i;
			node.diff = BALANCE;

			NODES.push_back(node);

			MAP[BALANCE][make_pair(i,i)] = num_nodes; //マップにIDを登録

			//スタートからエッジを張る
			NODES[start].NEXT.push_back(Data(num_nodes,info[i].length));
			G[start].push_back(num_nodes);
			reverse_G[num_nodes].push_back(start);

			//バランスしたので、ゴールにエッジを張る
			NODES[num_nodes].NEXT.push_back(Data(goal,0));
			G[num_nodes].push_back(goal);
			reverse_G[goal].push_back(num_nodes);

			num_nodes++;
		}
	}


	//左端固定
	for(int i = 1; i <= V; i++){

		for(int right = 0; right <= info[i].length-2; right++){
			bool FLG = true;

			//0～rightが回文になっているか
			int tmp_len = right+1;

			for(int k = 0; k < tmp_len/2; k++){
				if(info[i].word[k] != info[i].word[tmp_len-1-k]){
					FLG = false;
					break;
				}
			}

			if(FLG){

				//ノード作成
				Node node;

				node.left_id = i;
				node.right_id = i;
				node.diff = (info[i].length-(right+1))+BALANCE;

				NODES.push_back(node);

				MAP[node.diff][make_pair(node.left_id,node.right_id)] = num_nodes; //マップにIDを登録

				//スタートからエッジを張る
				NODES[start].NEXT.push_back(Data(num_nodes,info[i].length));
				G[start].push_back(num_nodes);
				reverse_G[num_nodes].push_back(start);

				num_nodes++;
			}
		}
	}

	//右端固定
	for(int i = 1; i <= V; i++){

		for(int left = 1; left <= info[i].length-1; left++){
			bool FLG = true;

			//left～info[i].length-1が回文になっているか
			int tmp_len = info[i].length-left;

			for(int k = 0; k < tmp_len/2; k++){
				if(info[i].word[left+k] != info[i].word[info[i].length-1-k]){
					FLG = false;
					break;
				}
			}

			if(FLG){

				//ノード作成
				Node node;

				node.left_id = i;
				node.right_id = i;
				node.diff = -left+BALANCE;

				NODES.push_back(node);

				MAP[node.diff][make_pair(node.left_id,node.right_id)] = num_nodes; //マップにIDを登録

				//スタートからエッジを張る
				NODES[start].NEXT.push_back(Data(num_nodes,info[i].length));
				G[start].push_back(num_nodes);
				reverse_G[num_nodes].push_back(start);

				num_nodes++;
			}
		}
	}

	/*★2つの単語★*/
	for(int L = 1; L <= V; L++){
		for(int R = 1; R <= V; R++){
			if(!check[L][R])continue;

			bool FLG = true;
			int tmp_len = min(info[L].length,info[R].length);

			for(int k = 0; k < tmp_len; k++){
				if(info[L].word[info[L].length-1-k] != info[R].word[k]){
					FLG = false;
					break;
				}
			}

			if(!FLG)continue;

			//ノード作成
			Node node;

			node.left_id = L;
			node.right_id = R;
			node.diff = (info[R].length-info[L].length)+BALANCE;

			auto at = MAP[node.diff].find(make_pair(node.left_id,node.right_id));

			if(at != MAP[node.diff].end()){ //★注意★

				continue;
			}

			NODES.push_back(node);

			MAP[node.diff][make_pair(L,R)] = num_nodes; //マップにIDを登録

			//スタートからエッジを張る
			NODES[start].NEXT.push_back(Data(num_nodes,info[L].length+info[R].length));
			G[start].push_back(num_nodes);
			reverse_G[num_nodes].push_back(start);


			if(node.diff == BALANCE){

				//バランスしたので、ゴールにエッジを張る
				NODES[num_nodes].NEXT.push_back(Data(goal,0));
				G[num_nodes].push_back(goal);
				reverse_G[goal].push_back(num_nodes);
			}

			num_nodes++;
		}
	}

	//発生し得る状態を全列挙
	queue<int> Q;

	for(int i = 0; i < NODES[start].NEXT.size(); i++){

		Q.push(NODES[start].NEXT[i].next_node_id);
	}

	while(!Q.empty()){

		int node_id = Q.front();
		Q.pop();

		if(NODES[node_id].diff <= BALANCE){ //右に文字追加

			for(int i = 1; i <= V; i++){

				if(!check[NODES[node_id].right_id][i])continue;

				//少なくとも重なる部分が全て一致するか調べる
				bool FLG = true;
				int left_diff = abs(NODES[node_id].diff-BALANCE);
				int tmp_len = min(left_diff,info[i].length);
				int left_id = NODES[node_id].left_id;

				for(int k = 0; k < tmp_len; k++){

					if(info[left_id].word[left_diff-1-k] != info[i].word[k]){
						FLG = false;
						break;
					}
				}

				if(!FLG)continue;

				Node node;
				node.diff = info[i].length-left_diff+BALANCE;
				node.left_id = NODES[node_id].left_id;
				node.right_id = i;

				auto at = MAP[node.diff].find(make_pair(node.left_id,node.right_id));

				if(at != MAP[node.diff].end()){ //出現済:エッジだけ張る

					int next_node = MAP[node.diff][make_pair(node.left_id,node.right_id)];

					NODES[node_id].NEXT.push_back(Data(next_node,info[i].length));
					G[node_id].push_back(next_node);
					reverse_G[next_node].push_back(node_id);

					continue;
				}

				NODES.push_back(node); //初登場

				MAP[node.diff][make_pair(node.left_id,node.right_id)] = num_nodes;

				//node_idからエッジを張る
				NODES[node_id].NEXT.push_back(Data(num_nodes,info[i].length));
				G[node_id].push_back(num_nodes);
				reverse_G[num_nodes].push_back(node_id);


				if(node.diff == BALANCE){ //バランスしていれば、ゴールにエッジを張る

					NODES[num_nodes].NEXT.push_back(Data(goal,0));
					G[num_nodes].push_back(goal);
					reverse_G[goal].push_back(num_nodes);

				}

				Q.push(num_nodes);

				num_nodes++;
			}

		}

		if(NODES[node_id].diff >= BALANCE){ //左に文字追加

			for(int i = 1; i <= V; i++){

				if(!check[i][NODES[node_id].left_id])continue;

				//少なくとも重なる部分が全て一致するか調べる
				bool FLG = true;
				int right_diff = NODES[node_id].diff-BALANCE;
				int tmp_len = min(right_diff,info[i].length);
				int right_id = NODES[node_id].right_id;

				for(int k = 0; k < tmp_len; k++){

					if(info[right_id].word[info[right_id].length-right_diff+k] != info[i].word[info[i].length-1-k]){
						FLG = false;
						break;
					}
				}

				if(!FLG)continue;

				Node node;
				node.diff = right_diff-info[i].length+BALANCE;
				node.left_id = i;
				node.right_id = NODES[node_id].right_id;

				auto at = MAP[node.diff].find(make_pair(node.left_id,node.right_id));

				if(at != MAP[node.diff].end()){  //出現済:エッジだけ張る

					int next_node = MAP[node.diff][make_pair(node.left_id,node.right_id)];

					NODES[node_id].NEXT.push_back(Data(next_node,info[i].length));
					G[node_id].push_back(next_node);
					reverse_G[next_node].push_back(node_id);

					continue;
				}

				NODES.push_back(node); //初出現なのでノード追加
				MAP[node.diff][make_pair(node.left_id,node.right_id)] = num_nodes;

				//node_idからエッジを張る
				NODES[node_id].NEXT.push_back(Data(num_nodes,info[i].length));
				G[node_id].push_back(num_nodes);
				reverse_G[num_nodes].push_back(node_id);

				if(node.diff == BALANCE){ //バランスしていれば、ゴールにエッジを張る

					NODES[num_nodes].NEXT.push_back(Data(goal,0));
					G[num_nodes].push_back(goal);
					reverse_G[goal].push_back(num_nodes);
				}

				Q.push(num_nodes);

				num_nodes++;
			}
		}
	}

	//ゴールできるか調べる
	for(int i = 0; i < num_nodes; i++){

		visited[i] = false;
	}
	visited[start] = true;
	start_dfs(start);

	if(!visited[goal]){

		printf("0\n");
		return 0;
	}

	//ゴールできるノードを探す
	for(int i = 0; i < num_nodes; i++){

		can_goal[i] = false;
		visited[i] = false;
	}
	visited[goal] = true;
	goal_dfs(goal);


	//ゴールできるものの中で、閉路に属するノードがないか調べる
	for(int i = 0; i < num_nodes; i++){
		if(can_goal[i] == false)continue;

		for(int k = 0; k < num_nodes; k++){

			visited[k] = false;
		}
		cycle_FLG = false;

		visited[i] = true;
		cycle_dfs(i,i);

		if(cycle_FLG){

			printf("-1\n");
			return 0;
		}
	}

	//dp計算する
	int ans = 0;

	//DAGになってるはずなのでdp計算
	queue<State> final_Q;

	dp[NODES[start].diff][make_pair(NODES[start].left_id,NODES[start].right_id)] = 0;
	final_Q.push(State(start,0));

	while(!final_Q.empty()){

		State state = final_Q.front();
		final_Q.pop();

		auto at = dp[NODES[state.node_id].diff].find(make_pair(NODES[state.node_id].left_id,NODES[state.node_id].right_id));

		if(at != dp[NODES[state.node_id].diff].end() && state.sum_value < dp[NODES[state.node_id].diff][make_pair(NODES[state.node_id].left_id,NODES[state.node_id].right_id)]){

			continue;
		}

		if(state.node_id == goal){

			ans = max(ans,state.sum_value);
		}

		for(int i = 0; i < NODES[state.node_id].NEXT.size(); i++){

			int next_node = NODES[state.node_id].NEXT[i].next_node_id;
			if(!can_goal[next_node])continue;

			int next_value = state.sum_value+NODES[state.node_id].NEXT[i].add_len;

			at = dp[NODES[next_node].diff].find(make_pair(NODES[next_node].left_id,NODES[next_node].right_id));

			if(at == dp[NODES[next_node].diff].end()){

				dp[NODES[next_node].diff][make_pair(NODES[next_node].left_id,NODES[next_node].right_id)] = next_value;

				final_Q.push(State(next_node,next_value));

			}else{

				if(dp[NODES[next_node].diff][make_pair(NODES[next_node].left_id,NODES[next_node].right_id)] < next_value){

					dp[NODES[next_node].diff][make_pair(NODES[next_node].left_id,NODES[next_node].right_id)] = next_value;
					final_Q.push(State(next_node,next_value));
				}
			}
		}
	}

	printf("%d\n",ans);

	return 0;
}



Measured memory_bytes: 17068