P15125 [ICPC 2024 LAC] KMOP

你可能知道 KMP 算法。你也可能知道 “KMP” 是一个首字母缩写词，代表 “Knuth Morris Pratt”，他们于 1977 年共同发表了该算法。你如何发音 “KMP”？当然，你可以直接说 “Knuth Morris Pratt”，但发音这个缩写本身呢？由于 “KMP” 不是一个可发音的单词，你被迫逐个字母念出来。在这个问题中，我们关注的是可发音的首字母缩写词。 我们需要一些定义来形式化这个要求。一个**短语**是一个单词列表，而一个**单词**是一个字母序列。每个字母要么是元音，要么是辅音。判断一个字母是元音还是辅音取决于语言和其他因素。为简单起见，我们说六个字母 “A”、“E”、“I”、“O”、“U” 和 “Y” 是元音，其余所有字母都是辅音。尽管一个给定的单词是否可发音存在争议，但我们说一个单词是**可发音的**，当它不包含超过两个连续的辅音。例如，“LEMPEL” 是一个可发音的单词，而 “DIJKSTRA” 则不是。 给定一个由 $N$ 个单词组成的短语，该短语的一个**首字母缩写词**是 $N$ 个前缀的连接，每个单词一个前缀，按它们在短语中出现的顺序排列。每个前缀必须至少有一个字母，至多有三个字母。你的任务是确定一个可发音的首字母缩写词的最小长度。 以 $N = 3$ 为例，考虑短语 “KNUTH MORRIS PRATT”。这个短语有 27 个可能的首字母缩写词，例如 “KMP”、“KMPR”、“KMPRA”、“KMOP”、“KMOPR” 和 “KNUMOPRA” 等。其中一些缩写词是可发音的（“KMOP” 和 “KMOPR”），而另一些则不是（“KMP”、“KMPR”、“KMPRA” 和 “KNUMOPRA”）。由于唯一的三字母缩写词 “KMP” 不可发音，因此 “KMOP” 是该短语的一个最小长度的可发音缩写词。

第一行包含一个正整数 $N$，表示短语中的单词数量。 接下来的 $N$ 行，每行包含一个由大写字母组成的非空字符串，表示短语中的一个单词。单词按它们在短语中出现的顺序给出。所有字符串的长度之和不超过 $10^6$。

输出一行，包含一个整数，表示可发音的首字母缩写词的最小长度；如果短语不存在可发音的首字母缩写词，则输出字符 “*”（星号）。