KMOP

KMP 알고리즘을 알고 있을 것이다. KMP는 1977년에 이 알고리즘을 함께 발표한 Knuth Morris Pratt의 약자이다. KMP는 어떻게 읽을까? Knuth Morris Pratt라고 풀어 말해도 되지만, 약어 자체는 어떻게 발음할까? KMP는 발음할 수 있는 단어가 아니므로 글자를 하나씩 읽어야 한다. 이 문제는 발음할 수 있는 약어를 다룬다.

구절은 단어의 목록이고, 단어는 글자의 나열이다. 각 글자는 모음이거나 자음이다. 단순하게 A, E, I, O, U, Y 여섯 글자를 모음으로 보고, 나머지 글자는 모두 자음으로 본다. 단어가 발음 가능한지는 논쟁의 여지가 있지만, 여기서는 연속된 자음이 세 개 이상 들어 있지 않은 단어를 발음 가능하다고 한다. 예를 들어 LEMPEL은 발음 가능하지만 DIJKSTRA는 그렇지 않다.

$N$개의 단어로 이루어진 구절이 주어진다. 구절의 약어는 각 단어마다 접두사를 하나씩 골라 단어의 출현 순서대로 이어 붙인 것이다. 각 접두사는 1글자 이상 3글자 이하여야 한다. 발음 가능한 약어의 최소 길이를 구하라.

$N = 3$이고 구절이 KNUTH MORRIS PRATT인 예를 보자. 이 구절의 약어는 KMP, KMPR, KMPRA, KMOP, KMOPR, KNUMORPRA 등 27개가 있다. 이 중 KMOP와 KMOPR는 발음 가능하고, 나머지는 그렇지 않다. 세 글자 약어는 KMP 하나뿐인데 발음할 수 없으므로, KMOP가 이 구절의 최소 길이 발음 가능 약어이다.

첫 줄에 구절을 이루는 단어의 개수 $N$이 양의 정수로 주어진다.

다음 $N$개의 줄에는 구절에 나오는 순서대로 단어가 한 줄에 하나씩 주어진다. 각 단어는 대문자로만 이루어진 비어 있지 않은 문자열이다. 모든 문자열 길이의 합은 $10^6$ 이하이다.

구절의 발음 가능한 약어 중 최소 길이를 한 줄에 출력한다. 발음 가능한 약어가 없으면 *을 출력한다.