#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <queue>
#include <ctime>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
template <class T> void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template <class T> void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 105;
const int M = 300005;
int n, m, cnt;
string s[N], rs[N];
vector <int> next[N];
vector <int> pre[N];
vector <PII> E[M];
int v[M];
int st[M];
int du[M];
int f[M];
int fa[M];
int wei[M];
int palind[N][11];
int rpalind[N][11];
int pos[N][N][11][2];
set <PII> Set;

int ans;

int abs(int x) {
	return x < 0 ? -x : x;
}

int find(int x, int y) {
	return Set.count(make_pair(x, y));
}

vector <PII> getEdge(int i, int j, int l, int d) {
	vector <PII> ret;
	if (d) {
		if (l > s[j].size()) return ret;
		if (find(i, j) && rpalind[j][s[j].size() - l]) {
			ret.push_back(make_pair(cnt, l));
		}
		foreach (it, next[i]) {
			int len = min(l, (int)s[*it].size());
			if (s[*it].substr(0, len) == rs[j].substr(s[j].size() - l, len)) {
				ret.push_back(make_pair(pos[*it][j][abs(l - (int)s[*it].size())][l >= s[*it].size()], len * 2));
			}
		}
	} else if (l) {
		if (l > s[i].size()) return ret;
		if (find(i, j) && palind[i][s[i].size() - l]) {
			ret.push_back(make_pair(cnt, l));
		}
		foreach (it, pre[j]) {
			int len = min(l, (int)s[*it].size());
			if (rs[*it].substr(0, len) == s[i].substr(s[i].size() - l, len)) {
				ret.push_back(make_pair(pos[i][*it][abs(l - (int)s[*it].size())][s[*it].size() >= l], len * 2));
			}
		}
	}
	return ret;
}

void build_graph() {
	cnt = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++)
			for (int k = 0; k < 11; k++)
				for (int l = 0; l < 2; l++)
					pos[i][j][k][l] = cnt++;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= s[i].size(); j++) {
			int k = s[i].size() - 1;
			string _s = s[i];
			int _i = j;
			int _j = k;
			int ok = 1;
			while (_i < _j) {
				if (_s[_i++] != _s[_j--]) {
					ok = 0;
					break;
				}
			}
			palind[i][j] = ok;
			_i = j;
			_j = k;
			_s = rs[i];
			ok = 1;
			while (_i < _j) {
				if (_s[_i++] != _s[_j--]) {
					ok = 0;
					break;
				}
			}
			rpalind[i][j] = ok;
		}
		if (palind[i][0]) {
			checkmax(ans, (int)s[i].size());
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < 11; k++)
				for (int l = 0; l < 2; l++) {
					E[pos[i][j][k][l]] = getEdge(i, j, k, l);
				}
}

void bfs() {
	queue <int> q;
	memset(v, 0, sizeof(v));
	memset(st, 0, sizeof(st));
	for (int i = 0; i <= cnt; i++) v[i] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int len = min(s[i].size(), s[j].size());
			if (s[i].substr(0, len) == rs[j].substr(0, len)) {
				int p = pos[i][j][abs((int)s[i].size() - (int)s[j].size())][s[j].size() >= s[i].size()];
				q.push(p);
				v[p] = 1;
				st[p] = 1;
				f[p] = min(s[i].size(), s[j].size()) * 2;
			}
		}
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		foreach (it, E[x]) {
			if (!v[it->first]) {
				fa[it->first] = x;
				v[it->first] = 1;
				q.push(it->first);
			}
		}
	}
}

vector <int> q;

void topsort() {
	memset(du, 0, sizeof(du));
	q.clear();
	for (int i = 0; i <= cnt; i++) {
		if (v[i]) {
			foreach (it, E[i]) {
				if (v[it->first]) {
					du[it->first]++;
				}
			}
		}
	}
	int head = 0;
	for (int i = 0; i <= cnt; i++) {
		if (v[i] && !du[i]) {
			q.push_back(i);
		}
	}
	while (head != q.size()) {
		int x = q[head++];
		foreach (it, E[x]) {
			if (v[it->first]) {
				du[it->first]--;
				if (!du[it->first]) {
					q.push_back(it->first);
				}
			}
		}
	}
}

void dp() {
	if (!v[cnt] && ans == -1) {
		puts("0");
	} else if (du[cnt]) {
		puts("-1");
	} else {
		for (int i = 0; i < q.size(); i++) {
			int x = q[i];
			if (f[x] != -1) {
				foreach (it, E[x]) {
					checkmax(f[it->first], f[x] + it->second);
				}
			}
		}
		cout << max(f[cnt], ans) << endl;
	}
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		rs[i] = s[i];
		reverse(rs[i].begin(), rs[i].end());
	}
	Set.clear();
	memset(f, 0xFF, sizeof(f));
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		Set.insert(make_pair(x, y));
		next[x].push_back(y);
		pre[y].push_back(x);
	}
	ans = -1;
	build_graph();
	bfs();
	topsort();
	dp();
}