Intelligible Double Magic

The 15th month of 2119. A spellbook was written by the court magician Sengemon Lugene. This magic book "In Magiray" was an innovative book in that it systematized "double magic", which is deeply related to the basis of the magic law of this world, as a technique that anyone can learn. First, let's take a look at a summary of the contents of this book.

【element】 Every object in the world is composed of tiny elements such as "spring", "wind", "feather", "flower", "sand", "light", and so on. There are many types of elements, and by signing a contract with an element, humans can activate double magic using the type of element with which they have a contract.

[Double magic] Double magic, as the name implies, is magic that superimposes two elements and releases them. The main element is called the "main attribute" and the other is called the "sub-attribute". For example, if the primary attribute is "light" and the secondary attribute is "flower", the double magic is written as (light, flower). (Light, flower) and (flower, light) are different double magics. Moreover, the primary attribute and the sub-attribute may be the same.

【keyword】 Each element can have a one-to-one correspondence with a short "keyword" such as "spring → huda", "wind → loar", "feather → sheza", and "flower → leide". A keyword is an epoch-making concept that makes it possible to easily activate double magic simply by chanting a few consecutive keyword strings by symbolizing the nature of the element in short words.

【incantation】 A spell is a sequence of one or more keywords, such as "huda, leide, loar, sheza". By casting the spell intended by the caster, you can activate the corresponding double spell. Specifically, double magic is activated with the element corresponding to the first keyword of the spell as the main attribute and the element corresponding to the last keyword as the sub attribute. In the example of the spell I mentioned earlier, the double magic that is activated is (fountain, feather). If the spell consists of only one keyword, both the primary attribute and the sub-attribute are the elements corresponding to that keyword.

[Compatibility between elements] I have already mentioned that the spell "huda, leide, loar, sheza" activates the double magic of (fountain, feather). However, at first glance, if you want to use (fountain, feather), it seems that you can just use "huda / sheza" without having to cast a long spell. But in reality, that is not possible. This is because "huda" and "sheza" are not compatible, and if you cast a spell in which these two are next to each other, a repulsive action will occur and the elements will cancel each other out. On the other hand, "fountain (huda)" and "flower (leide)", "flower (leide)" and "wind (loar)", "wind (loar)" and "feather (sheza)" are all good. Because of their compatibility, spells such as "huda, leide, loar, sheza" and "loar, leide, huda" do not offset elements.

[Spell logic] Those who want to use double magic should define in advance which keyword is the "upper word" and which keyword is the "lower word" for each pair of compatible elements. There must be. When A is defined as the upper word and B is defined as the lower word for the keywords "A" and "B" of two compatible elements, it is written as A> B. When A> B, A cannot be placed immediately after B in a spell. In other words, if "A1, A2, A3 ... Ak" is the correct spell, it must be A1> A2, A2> A3, ..., Ak-1> Ak. By the way, even if A> B and B> C, it does not have to be A> C.

In this way, each surgeon defines the upper and lower words to his or her own taste, which is called "construction of spell logic". This is a device to clarify the flow of elements and increase the success probability of the target double magic by intentionally restricting the syntax of the spell. However, the price is that building spell logic can result in double spells that can't be cast no matter how you cast the spell (although you can use it no matter what spell logic you build. It has been proven that there is no double magic that cannot be done). Given these circumstances, what kind of spell logic to build is a thorny issue that has plagued many magicians both now and in the past.

Uto, an apprentice magician boy living in a small town, has signed contracts with all the elements and is about to perform a ritual to build his spell logic tomorrow. Ute simply thought that spell logic that could cast as many types of double magic as possible was good spell logic.

As a super-first-class electrician (super programmer in modern Japan), how many types of double magic can you use if you can successfully build spell logic from your friend Ute? I was consulted to know. This is a difficult problem that humans around the world have challenged, but no one could solve. If you can solve it, your name will be handed down all over the world in the future.

Input

N M s1 s2 .. .. .. sN p1 q1 p2 q2. .. .. pM M

On the first line of input, the integer N and the integer M are written separated by blanks. This means that there are a total of N types of elements and a total of M pairs of compatible elements.

One character string is written in the following N lines. The character string si written on the 1 + i line indicates that the keyword corresponding to the i-th element is si.

On the following M line, two strings are written separated by blanks. The character strings pi and qi written on the 1 + N + i lines indicate that the element corresponding to the keyword pi and the pair of elements corresponding to the keyword qi are compatible. Conversely, pairs of elements that do not appear here are not compatible.

These data satisfy the following conditions.

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 4,950
• si is a string of 1 to 15 characters consisting of only uppercase or lowercase letters of the alphabet.
• i ≠ j ⇒ si ≠ sj
• pi ≤ qi
• i ≤ j ⇒ (pi, qi) ≠ (pj, qj) and (pi, qi) ≠ (qj, pj)
• There is no double magic that cannot be activated by constructing any spell logic.

Output

Output the maximum number of double magic types available when you build spell logic.

Examples

Input

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

Output

10

Input

3 3 torn siole dimi torn siole torn dimi siole dimi

Output

9

Input

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

Output

54

inputFormat

Input

N M s1 s2 .. .. .. sN p1 q1 p2 q2. .. .. pM M

On the first line of input, the integer N and the integer M are written separated by blanks. This means that there are a total of N types of elements and a total of M pairs of compatible elements.

One character string is written in the following N lines. The character string si written on the 1 + i line indicates that the keyword corresponding to the i-th element is si.

On the following M line, two strings are written separated by blanks. The character strings pi and qi written on the 1 + N + i lines indicate that the element corresponding to the keyword pi and the pair of elements corresponding to the keyword qi are compatible. Conversely, pairs of elements that do not appear here are not compatible.

These data satisfy the following conditions.

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 4,950
• si is a string of 1 to 15 characters consisting of only uppercase or lowercase letters of the alphabet.
• i ≠ j ⇒ si ≠ sj
• pi ≤ qi
• i ≤ j ⇒ (pi, qi) ≠ (pj, qj) and (pi, qi) ≠ (qj, pj)
• There is no double magic that cannot be activated by constructing any spell logic.

outputFormat

Output

Output the maximum number of double magic types available when you build spell logic.

Examples

Input

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

Output

10

Input

3 3 torn siole dimi torn siole torn dimi siole dimi

Output

9

Input

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

Output

54

样例

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

54