p01424 Palindrome Generator_5106
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
#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>

using namespace std;

int min(int a,unsigned int b){
	return min(a,(int)b);
}
int min(unsigned int a,int b){
	return min((int)a,b);
}

struct edge{
	int to,cost;
	edge(){}
	edge(int a,int b):to(a),cost(b){}
};

vector<edge> G[210210];
vector<edge> rG[210210];

int V;
int N;
string strs[100];

int encode(int i,int j,int a,int l){
	if(l==0){
		return i*2100+j*21;
	}
	if(a==0){//left
		return i*2100+j*21+l;
	}
	if(a==1){//right
		return i*2100+j*21+10+l;
	}
}

vector<int> prv[100],nxt[100];

bool isPalin(string str){
	for(int i=0;i<str.size();i++){
		if(str[i]!=str[str.size()-i-1]) return false;
	}
	return true;
}

bool match(string str1,string str2){
	if(str1.size()!=str2.size()){
		fprintf(stderr,"invalid call for match\n");
		fprintf(stderr,"%s %s\n",str1.c_str(),str2.c_str());
		exit(0);
	}
	for(int i=0;i<str1.size();i++){
		if(str1[i]!=str2[str2.size()-i-1]) return false;
	}
	return true;
}

void getGraph(){
	V=(2100*(N-1)+21*(N-1)+21)+2;
	for(int le=0;le<N;le++){
		for(int ri=0;ri<N;ri++){
			//no remaining chars
			int v=encode(le,ri,0,0);
			for(int i=0;i<nxt[ri].size();i++){
				int id=nxt[ri][i];
				int s=strs[nxt[ri][i]].size();
				int nv=encode(le,id,1,s);
				G[v].push_back(edge(nv,s));
			}
			for(int i=0;i<prv[le].size();i++){
				int id=prv[le][i];
				int s=strs[id].size();
				int nv=encode(id,ri,0,s);
				G[v].push_back(edge(nv,s));
			}
			
			//left is unmatched
			for(int l=1;l<=strs[le].size();l++){
				int v=encode(le,ri,0,l);
				for(int i=0;i<nxt[ri].size();i++){
					int id=nxt[ri][i];
					int m=min(l,strs[id].size());
					int s=strs[id].size();
					string str1=strs[le].substr(l-m,m);
					string str2=strs[id].substr(0,m);
					bool flg=match(str1,str2);
					if(!flg) continue;
					if(l>m){
						int nv=encode(le,id,0,l-m);
						G[v].push_back(edge(nv,s));
					}/*else if(l==m&&m==strs[id].size()){
						int nv=encode(le,id,0,0);
						G[v].push_back(edge(nv,m));
					}*/else{
						int nv=encode(le,id,1,s-m);
						G[v].push_back(edge(nv,s));
					}
				}
			}
			
			//right is unmatched
			for(int l=1;l<=strs[ri].size();l++){
				int v=encode(le,ri,1,l);
				for(int i=0;i<prv[le].size();i++){
					int id=prv[le][i];
					int m=min(l,strs[id].size());
					string str1=strs[id].substr(strs[id].size()-m,m);
					string str2=strs[ri].substr(strs[ri].size()-l,m);
					int s=strs[id].size();
					bool flg=match(str1,str2);
					if(!flg) continue;
					if(l>m){
						int nv=encode(id,ri,1,l-m);
						G[v].push_back(edge(nv,s));
					}/*else if(l==m&&m==strs[id].size()){
						int nv=encode(id,ri,0,0);
						G[v].push_back(edge(nv,m));
					}*/else{
						int nv=encode(id,ri,0,s-m);
						G[v].push_back(edge(nv,s));
					}
				}
			}
		}
	}
	//from empty string
	for(int i=0;i<N;i++){
		//palindrome
		if(isPalin(strs[i])){
			int v=encode(i,i,0,0);
			G[V-2].push_back(edge(v,strs[i].size()));
		}
		
		//left is unmatched
		for(int l=1;l<=strs[i].size();l++){
			string str;
			if(l==strs[i].size()) str="";
			else str=strs[i].substr(l,1000);
			if(!isPalin(str)) continue;
			int v=encode(i,i,0,l);
			G[V-2].push_back(edge(v,strs[i].size()));
		}
		
		//right is unmatched
		for(int l=1;l<=strs[i].size();l++){
			string str=strs[i].substr(0,strs[i].size()-l);
			if(!isPalin(str)) continue;
			int v=encode(i,i,1,l);
			G[V-2].push_back(edge(v,strs[i].size()));
		}
	}
	//to goal
	for(int le=0;le<N;le++) for(int ri=0;ri<N;ri++){
		int v=encode(le,ri,0,0);
		G[v].push_back(edge(V-1,0));
	}
	for(int v=0;v<V;v++){
		for(int j=0;j<G[v].size();j++){
			rG[G[v][j].to].push_back(edge(v,G[v][j].cost));
		}
	}
}

bool from_s[220220];
bool from_t[220220];

queue<int> que;
void reachable(int s,bool *res,bool rev){
	while(!que.empty()) que.pop();
	que.push(s);
	for(int i=0;i<V;i++) res[i]=false;
	res[s]=true;
	while(!que.empty()){
		int v=que.front();
		que.pop();
		if(!rev){
			for(int i=0;i<G[v].size();i++){
				int nxt=G[v][i].to;
				if(res[nxt]) continue;
				res[nxt]=true;
				que.push(nxt);
			}
		}else{
			for(int i=0;i<rG[v].size();i++){
				int nxt=rG[v][i].to;
				if(res[nxt]) continue;
				res[nxt]=true;
				que.push(nxt);
			}
		}
	}
}

bool is_valid[220220];

int cmp[220220];
bool used[220220];

vector<int> vs;
void dfs(int v){
	used[v]=true;
	for(int i=0;i<G[v].size();i++){
		int nxt=G[v][i].to;
		if(!is_valid[nxt]) continue;
		if(used[nxt]) continue;
		dfs(nxt);
	}
	vs.push_back(v);
}

void rdfs(int v,int k){
	used[v]=true;
	cmp[v]=k;
	for(int i=0;i<rG[v].size();i++){
		int nxt=rG[v][i].to;
		if(!is_valid[nxt]) continue;
		if(used[nxt]) continue;
		rdfs(nxt,k);
	}
}

void scc(){
	for(int i=0;i<V;i++) used[i]=false;
	for(int i=0;i<V;i++){
		if(!is_valid[i]) continue;
		if(used[i]) continue;
		dfs(i);
	}
	for(int i=0;i<V;i++) used[i]=false;
	int k=0;
	for(int i=(int)vs.size()-1;i>=0;i--){
		int v=vs[i];
		if(!is_valid[v]) continue;
		if(used[v]) continue;
		rdfs(v,k++);
	}
}

int cnt[220220];
bool checkInf(){
	for(int i=0;i<V;i++){
		if(!is_valid[i]) continue;
		cnt[cmp[i]]++;
		if(cnt[cmp[i]]>=2) return true;
	}
	return false;
}

int dp[220220];
int prvs[220220];
void rec(int v){
	if(dp[v]!=-1) return;
	int M=0;
	int p=-1;
	for(int i=0;i<rG[v].size();i++){
		int prv=rG[v][i].to;
		if(!is_valid[prv]) continue;
		int c=rG[v][i].cost;
		rec(prv);
		if(M<dp[prv]+c) p=prv;
		M=max(M,dp[prv]+c);
	}
	prvs[v]=p;
	dp[v]=M;
}

int solve(){
	getGraph();
	reachable(V-2,from_s,false);
	reachable(V-1,from_t,true);
	if(from_s[V-1]==false) return 0;
	for(int i=0;i<V;i++) is_valid[i]=from_s[i]&from_t[i];
	scc();
	bool is_inf=checkInf();
	if(is_inf) return -1;
	for(int i=0;i<V;i++) dp[i]=-1;
	dp[V-2]=0;
	rec(V-1);
	int res=dp[V-1];
	return res;
}

void input(){
	int M;
	scanf("%d%d",&N,&M);
	char ch[20];
	for(int i=0;i<N;i++){
		scanf("%s",ch);
		strs[i]=string(ch);
	}
	for(int i=0;i<M;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;v--;
		nxt[u].push_back(v);
		prv[v].push_back(u);
	}
}

int main(){
	input();
	int ans=solve();
	printf("%d\n",ans);
	return 0;
}