Problem: A palidrome craftsperson starts to work in the early morning, with the clear air allowing him to polish up his palindromes.

On this morning, he is making his pieces to submit to the International Contest for Palindrome Craftspeople.

By the way, in order to make palindromes, he uses a special dictionary which contains a set of words and a set of ordered pairs of the words. Any words and any ordered pairs of consecutive words in his palindromes must appear in the dictionary.

We already have his dictionary, so let's estimate how long a palindrome he can make.



Input

The first line in the data set consists of two integers N (1 \leq N \leq 100) and M (0 \leq M \leq 1\,000). N describes the number of words in the dictionary and M describes the number of ordered pairs of words.

The following N lines describe the words he can use. The i-th line (1-based) contains the word i, which consists of only lower-case letters and whose length is between 1 and 10, inclusive.

The following M lines describe the ordered pairs of consecutive words he can use. The j-th line (1-based) contains two integers X_j and Y_j (1 \leq X_j, Y_j \leq N). X_j describes the (1-based) index of the former word in the palindrome and Y_j describes that of the latter word.

Output

Print the maximal length of the possible palindrome in a line. If he can make no palidromes, print "0". If he can make arbitrary long palindromes, print "-1".

Examples

Input

2 2
ab
ba
1 1
1 2


Output

4


Input

2 2
ab
ba
1 1
2 2


Output

0


Input

2 2
ab
a
1 1
1 2


Output

-1

Solution (in CPP):

Solution:
#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;
}