Problem I: よくわかる二重魔法

紀慧暦2119 年15 の月。宮廷魔術士Sengemon Lugene の手によって、一冊の魔術書が書き記された。この魔術書「In Magiray」は、この世界の魔術法則の根幹に深く関わる「二重魔法」を、誰にでも習得可能な技術として体系化した、という点で革新的な書物であった。まずは、この書物の内容を要約したものを見ていこう。

【エレメント】
世界中のあらゆる物体は、「泉」「風」「羽」「花」「砂」「灯」……といった、極小要素「エレメント」から構成されている。エレメントには多くの種類があり、人間はエレメントと契約を交わすことで、契約を交わした種類のエレメントを用いた二重魔法を発動させることができる。

【二重魔法】
二重魔法とは、その名の通り、２つのエレメントを重ね合わせて解き放つ魔法である。主となるエレ メントを「主属性」、もう一方を「副属性」と呼ぶ。たとえば、主属性が「灯」で副属性が「花」な ら、その二重魔法は（灯，花）と表記される。（灯，花）と（花，灯）は別の二重魔法である。また、主属性と副属性は同じであってもよい。

【キーワード】
「泉→ huda」「風→ loar」「羽→ sheza」「花→ leide」といったように、各々のエレメントに、それぞれ短い「キーワード」を１対１対応させることができる。キーワードは、エレメントの持つ性質を短い言葉に象徴させることで、いくつかの連続するキーワード列を唱えるだけで簡単に二重魔法を発動させることを可能にした、画期的な概念である。

【呪文】
「huda・leide・loar・sheza」のように、１つ以上のキーワードを連続して並べたものを「呪文」という。術者が意図した呪文を唱えることで、対応する二重魔法を発動させることができる。具体的には、呪文の一番最初のキーワードに対応するエレメントを主属性、一番最後のキーワードに対応するエレメントを副属性とする二重魔法が発動する。先ほどの呪文の例だと、発動する二重魔法は（泉，羽）である。なお、呪文が１つのキーワードだけから成る場合には、主属性も副属性も、そのキーワードに対応するエレメントになる。

【エレメント同士の相性】
「huda・leide・loar・sheza」の呪文で（泉，羽）の二重魔法が発動することはすでに述べた。しかし、一見すると、（泉，羽）を使いたいのならば、わざわざ長い呪文を唱えずとも「huda・sheza」だけで良いようにも思える。だが実際には、それは不可能である。なぜなら、「泉（huda）」と「羽（sheza）」は相性が良くないため、これら２つが隣り合った呪文を唱えると、反発作用が起こってエレメント同士が相殺してしまうからである。一方で、「泉（huda）」と「花（leide）」、「花（leide）」と「風（loar）」、「風（loar）」と「羽（sheza）」は、どのペアも好相性なので、「huda・leide・loar・sheza」や「loar・leide・huda」といった呪文では、エレメントの相殺は起こらない。

【呪文論理】
二重魔法を使おうとする者は、あらかじめ、すべての好相性なエレメントのペアそれぞれに対して、 どちらのキーワードが「上位ワード」で、どちらのキーワードが「下位ワード」なのかを定義しておかなければならない。好相性な２つのエレメントのキーワード「A」と「B」に対して、A を上位ワード、B を下位ワードと定義したとき、A > B と表記する。A > B であるとき、一つの呪文内で、B の直後にA を並べることはできない。つまり、「A₁・A₂・A₃・……・A_k」が正しい呪文であるならば、A₁ > A₂，A₂ > A₃，……，A_k-1 > A_k でなくてはならない。ちなみに、A > B かつB > C であっても、A > C である必要はない。

このように、各々の術者が、上位・下位ワードを自分好みに定義することを「呪文論理の構築」と呼 ぶ。これは、あえて呪文の構文に制約をもたせることで、エレメントの流れを明確化し、目的の二重 魔法の成功確率を上げるための工夫である。だが、その代償として、呪文論理を構築すると、どのよ うに呪文を唱えても発動させることのできない二重魔法が生じてしまう可能性がある（ただし、いか なる呪文論理を構築しても使うことのできない二重魔法は存在しないことが証明されている）。この ような事情があるため、どのような呪文論理を構築するかは、今も昔も多くの魔術士を悩ませている 厄介な問題なのである。

とある小さな町で暮らす見習い魔術士の少年ユートは、すべてのエレメントとの契約を終え、いよい よ明日、自分の呪文論理を構築するための儀式を行おうとしている。ユートは単純に、できるだけた くさんの種類の二重魔法を発動させることができるような呪文論理が良い呪文論理である、と考えて いた。

超一級電術技師（現代日本で言うところのスーパープログラマー）であるあなたは、友達のユートか ら、うまく呪文論理を構築することができれば、最大で何種類の二重魔法を使えるようになるのか知 りたいと相談を受けた。これは、今まで世界中の人間が挑戦してきたが、誰も解くことができなかっ たほどの難問である。もしも解くことができれば、あなたの名前は未来永劫、世界中で語り継がれる ことになるであろう。

Input

N M
s₁
s₂
.
.
.
s_N
p₁ q₁ p₂ q₂ .
.
.
p_M M

入力の１行目には、整数N と整数M が、空白区切りで書かれている。これは、エレメントが全部でN 種類、好相性なエレメントのペアが全部でM 組存在することをあらわす。

続くN 行には、１つの文字列が書かれている。１＋ i 行目に書かれた文字列s_i は、i 番目のエレメントに対応するキーワードがs_i であることをあらわす。

続くM 行には、２つの文字列が空白区切りで書かれている。１＋ N ＋ i 行目に書かれた文字列p_i とq_i は、キーワードp_i に対応するエレメントと、キーワードq_i に対応するエレメントのペアが、好相性であることをあらわす。逆に、ここにあらわれなかったエレメントのペアは、好相性ではない。

これらのデータは、以下の条件をみたす。

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 4,950
• s_i は、アルファベットの大文字または小文字のみからなる、1 文字以上15 文字以下の文字列
• i ≠ j 　⇒　s_i ≠ s_j
• p_i ≤ q_i
• i ≤ j 　⇒　(p_i, q_i) ≠ (p_j, q_j) かつ(p_i, q_i) ≠ (q_j, p_j)
• いかなる呪文論理を構築しても発動することのできない二重魔法は存在しない

Output

呪文論理を構築したとき、使用可能になる二重魔法の種類の最大数を出力せよ。

Sample Input 1

4 3
huda
leide
loar
sheza
huda leide
leide loar
loar sheza

Sample Output 1

10

Sample Input 2

3 3
torn
siole
dimi
torn siole
torn dimi
siole dimi

Sample Output 2

9

Sample Input 3

9 10
riris
soa
elah
clar
arma
memori
neoles
qhaon
clue
clar riris
riris memori
riris neoles
soa clar
soa memori
neoles elah
elah qhaon
neoles qhaon
clue riris
arma elah

Sample Output 3

54