Problem G
Thesaurus
After staying up all night, Yraglac has finally finished writing the essay for his assignment. However, he just noticed at the last minute that his essay exceeds the maximum permissible length!
Since Yraglac has little time left, he doesn’t want to spend too much time changing his essay. At the same time, he doesn’t want to change the meaning of his essay. He came up with a genius plan for solving his predicament: he will replace every word with the shortest possible synonym!
The essay consists of $N$ words. There can be repeated words in the essay, and some of the words in the essay may not have any synonyms. The thesaurus consists of $M$ different word pairs, where a word pair $(a, b)$ denotes that $a$ is a synonym of $b$ and vice versa. Note that synonyms are transitive, so if $a$ is a synonym of $b$ and $b$ is a synonym of $c$, then $a$ is a synonym of $c$.
What is the minimum number of characters (excluding spaces) in the essay assuming every word is replaced with the shortest possible synonym?
Input
The first line of the input contains two integers $N, M$, where $1\leq N, M\leq 5\, 000$.
The next line of the input represents the essay, which contains $N$ space-separated strings.
The remaining $M$ lines of the input represents the thesaurus. Each line contains two space-separated strings $a$ and $b$, denoting that they are synonyms.
It is guaranteed that no string in the input contains more than $1\, 000$ characters and that all strings consists of only lowercase English characters.
Output
Output a single integer denoting the minimum number of characters in the essay excluding spaces if every word is replaced with the shortest possible synonym.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 4 to be or not to be that is the investigation investigation question that foobar foobar fb to blah |
28 |
