Twins Idol

Time Limit : 1 sec, Memory Limit : 262144 KB

E: Twins Idol / ツインズアイドル

アイドル事務所841プロダクションには,多くの個性的なアイドル達が所属している. 双子のアイドルであるアキ&マキは,841プロに所属するアイドルであり,2人ともとてもゲーム好きである. ある日2人は,次のようなゲームを自分達で自作して楽しむことにした. このゲームは,2人で協力するタイプのゲームであるため,双子の息の合ったプレイが期待される.

まず,ゲームを始める前に,2人が別々に自分の好きなようにフィールドを床に描く. フィールドは,アルファベットの1文字が書かれたいくつかのボードと,ボード間をつなぐルートで構成される. 彼女らは,このルート上を辿ることで,ボード間を移動できる. ただし,ルートには矢印がついており,その矢印の方向に向かってしか移動できない. アキのフィールドとマキのフィールドの間にルートは存在しないため,互いのフィールドを行き来することはできない.

まず,アキとマキが,自分のフィールド内の好きなボードに立つところからゲームが始まる. そして,以下の決まりに従って,2人が同時に行動していく.

  • 2人の立っているボードの文字が等しい場合
    • スコアとして,1点を得る.
    • 2人は現在立っているボードを離れて,別のボードに移動しなければならない.
    • ただし,別のボードに移動しようとした際,2人の内どちらかが移動できなかった場合,ゲームを終了する.
  • 2人の立っているボードの文字が異なる場合
    • スコアを得ることはできない.
    • 2人はそれぞれ,「現在のボードにとどまる」か「別のボードに移動する」かを選択して行動する.2人が同じ行動を取る必要はない.
    • ただし,別のボードに移動しようとした際,移動できなかった場合,ゲームを終了する.
  • 現在以降のターンを使用して,現在のボードから,どう移動しても点数を増やせないとき
    • ゲームを終了する.

アキ&マキは,このゲームでなるべく高いスコアを出したいと考えている. 2人が最大でどれだけの得点を取得できるか,841プロの新人敏腕プロデューサである君が,お得意のプログラミングによって華麗にヒントを与えてあげよう.

Input

入力は次の形式で表される.

AKI_FIELD
MAKI_FIELD

AKI_FIELDMAKI_FIELDは,それぞれアキとマキのフィールドを表す. 各フィールドの入力は,次の形式で表される.

N M
c1 c2, ..., cN
a1 b1
...
ai bi
...
aM bM

全ての数値は整数値である. N (1 <= N <= 100) はボードの数であり,各ボードには,1, 2, ..., Nの番号が付いている. M (0 <= M <= 5000) はボード間のルートの数を表す. 次の1行には,各ボードに書かれている文字が,ボード1から順番に空白で区切られて入力される. 各文字は,アルファベットの小文字か大文字のいずれかである. 大文字と小文字は,別の文字として扱わなければならない. 続いて,M行にわたって,ルート情報が入力される. 各ルートは,ボードaiからボードbiに向かって伸びている(1 <= ai, bi <= N). aibiは異なる値であり,一度入力されたルートが,再び入力されることはない. ただし,一度入力されたルートの逆方向のルートが入力されることはある.

Output

アキ&マキが取得できる最大の得点を答えよ. ただし,無限に点数を増やせる場合は,-1を出力せよ.

Sample Input 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

Sample Output 1

3

Sample Input 2

2 2
a b
1 2
2 1
4 3
a b a b
1 2
2 3
3 4

Sample Output 2

4

Sample Input 3

3 3
Y Y I
1 2
2 3
3 1
3 3
I O R
1 3
3 2
2 1

Sample Output 3

-1

Source: Ritsumeikan University Competitive Programming Camp 2013, Day3 , Problem set from Ritsumeikan University teams, Shiga, Japan, 2013-03-13
Problem Setter:  Respect2D