#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define foreach(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define all(c) begin(c),end(c)
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

struct Edge{
	int src,dst;
	Edge(){}
	Edge(int s,int d):src(s),dst(d){}
};
typedef vector<vector<Edge>> Graph;

void DFS(const Graph& g,int v,vi& vis,vi& order)
{
	if(vis[v]) return;
	vis[v]=1;
	foreach(e,g[v])
		DFS(g,e->dst,vis,order);
	order.push_back(v);
}

vvi SCC(const Graph& g)
{
	int n=g.size();
	vi vis(n),order;
	rep(i,n) DFS(g,i,vis,order);
	Graph t(n);
	rep(i,n) foreach(e,g[i])
		t[e->dst].push_back(Edge(e->dst,e->src));
	fill(all(vis),0);
	vvi res;
	per(i,n) if(!vis[order[i]]){
		res.resize(res.size()+1);
		DFS(t,order[i],vis,res.back());
	}
	return res;
}

bool input(Graph& g,string& s)
{
	int n,m; cin>>n>>m;
	if(cin.eof()) return false;
	rep(i,n){
		char c; cin>>c;
		s+=c;
	}
	g.resize(n);
	rep(i,m){
		int s,d; cin>>s>>d; s--,d--;
		g[s].emplace_back(s,d);
	}
	return true;
}

int solve(Graph g1,string s1,Graph g2,string s2)
{
	vl f(128);
	rep(i,26){
		f['A'+i]=1ll<<i;
		f['a'+i]=1ll<<26+i;
	}
	
	vvi scc1=SCC(g1),scc2=SCC(g2);
	int m1=scc1.size(),m2=scc2.size();
	vl bs1(m1),bs2(m2);
	rep(i,m1) rep(j,scc1[i].size()) bs1[i]|=f[s1[scc1[i][j]]];
	rep(i,m2) rep(j,scc2[i].size()) bs2[i]|=f[s2[scc2[i][j]]];
	{
		ll b1=0,b2=0;
		rep(i,m1) if(scc1[i].size()>1) b1|=bs1[i];
		rep(i,m2) if(scc2[i].size()>1) b2|=bs2[i];
		if(b1&b2) return -1;
	}
	
	Graph c1(m1),c2(m2); // 成分グラフ
	{
		vi color1(g1.size()),color2(g2.size());
		rep(i,m1) rep(j,scc1[i].size()) color1[scc1[i][j]]=i;
		rep(i,m2) rep(j,scc2[i].size()) color2[scc2[i][j]]=i;
		rep(i,g1.size()) for(Edge e:g1[i]){
			int s=color1[e.src],d=color1[e.dst];
			c1[s].emplace_back(s,d);
		}
		rep(i,g2.size()) for(Edge e:g2[i]){
			int s=color2[e.src],d=color2[e.dst];
			c2[s].emplace_back(s,d);
		}
	}
	
	auto chmax=[](int& a,int b){a=max(a,b);};
	vvi dp(m1,vi(m2));
	rep(i,m1) rep(j,m2) dp[i][j]=!!(bs1[i]&bs2[j]);
	rep(i,m1) rep(j,m2){
		for(Edge e:c1[i]) chmax(dp[e.dst][j],dp[i][j]);
		for(Edge e:c2[j]) chmax(dp[i][e.dst],dp[i][j]);
		for(Edge e1:c1[i]) for(Edge e2:c2[j])
			chmax(dp[e1.dst][e2.dst],dp[i][j]+!!(bs1[e1.dst]&bs2[e2.dst]));
	}
	
	int res=0;
	rep(i,m1) rep(j,m2) chmax(res,dp[i][j]);
	return res;
}

int main()
{
	for(;;){
		Graph g1,g2; string s1,s2;
		if(!input(g1,s1) || !input(g2,s2))
			break;
		cout<<solve(g1,s1,g2,s2)<<endl;
	}
}

Measured memory_bytes: 1524