アイドル事務所841プロダクションには，多くの個性的なアイドル達が所属している． 双子のアイドルであるアキ＆マキは，841プロに所属するアイドルであり，2人ともとてもゲーム好きである． ある日2人は，次のようなゲームを自分達で自作して楽しむことにした． このゲームは，2人で協力するタイプのゲームであるため，双子の息の合ったプレイが期待される．
まず，ゲームを始める前に，2人が別々に自分の好きなようにフィールドを床に描く． フィールドは，アルファベットの1文字が書かれたいくつかのボードと，ボード間をつなぐルートで構成される． 彼女らは，このルート上を辿ることで，ボード間を移動できる． ただし，ルートには矢印がついており，その矢印の方向に向かってしか移動できない． アキのフィールドとマキのフィールドの間にルートは存在しないため，互いのフィールドを行き来することはできない．
まず，アキとマキが，自分のフィールド内の好きなボードに立つところからゲームが始まる． そして，以下の決まりに従って，2人が同時に行動していく．
アキ＆マキは，このゲームでなるべく高いスコアを出したいと考えている． 2人が最大でどれだけの得点を取得できるか，841プロの新人敏腕プロデューサである君が，お得意のプログラミングによって華麗にヒントを与えてあげよう．
入力は次の形式で表される．
AKI_FIELDとMAKI_FIELDは，それぞれアキとマキのフィールドを表す． 各フィールドの入力は，次の形式で表される．
全ての数値は整数値である． N (1 <= N <= 100) はボードの数であり，各ボードには，1, 2, ..., Nの番号が付いている． M (0 <= M <= 5000) はボード間のルートの数を表す． 次の1行には，各ボードに書かれている文字が，ボード1から順番に空白で区切られて入力される． 各文字は，アルファベットの小文字か大文字のいずれかである． 大文字と小文字は，別の文字として扱わなければならない． 続いて，M行にわたって，ルート情報が入力される． 各ルートは，ボードaiからボードbiに向かって伸びている(1 <= ai, bi <= N)． aiとbiは異なる値であり，一度入力されたルートが，再び入力されることはない． ただし，一度入力されたルートの逆方向のルートが入力されることはある．
アキ＆マキが取得できる最大の得点を答えよ． ただし，無限に点数を増やせる場合は，-1を出力せよ．
5 5 a c b c a 1 2 1 3 2 3 3 4 3 5 4 3 b a c c 1 3 2 3 3 4
3
2 2 a b 1 2 2 1 4 3 a b a b 1 2 2 3 3 4
4
3 3 Y Y I 1 2 2 3 3 1 3 3 I O R 1 3 3 2 2 1
-1