짐비는 자신이 운영하는 채팅방에 금칙어 필터를 도입하려고 한다. 필터에 등록된 금칙어는 개이며, 모두 영어 소문자로 이루어진 길이 의 문자열이다.
필터는 메시지에 금칙어가 등장하는 동안 다음 과정을 반복한다.
선택할 수 있는 부분이 여러 개라면 어느 것을 먼저 삭제해도 된다. 삭제로 인해 새롭게 금칙어가 등장하면 그 부분도 삭제할 수 있다.
더 이상 금칙어가 등장하지 않을 때 남은 문자열을 처리 결과라고 한다. 모든 문자가 삭제되었다면 처리 결과는 빈 문자열이다.
짐비는 같은 메시지라도 삭제하는 순서에 따라 처리 결과가 달라질 수 있다는 사실을 발견했다. 예를 들어 금칙어가 aba일 때, 메시지 ababa에서 앞쪽의 aba를 삭제하면 ba가 남지만, 뒤쪽의 aba를 삭제하면 ab가 남는다.
금칙어 목록이 주어질 때, 서로 다른 두 가지 이상의 처리 결과를 만들 수 있는 가장 짧은 메시지의 길이를 구하라. 메시지는 영어 소문자로만 이루어져야 한다. 그런 메시지가 존재하지 않으면 -1을 출력하라.
입력은 다음과 같은 형식으로 주어진다.
삭제 순서에 따라 처리 결과가 달라질 수 있는 가장 짧은 메시지의 길이를 출력한다. 그런 메시지가 존재하지 않으면 -1을 출력한다.
메시지 ababa에서 다음과 같이 서로 다른 처리 결과를 얻을 수 있다. 대괄호는 삭제하는 부분을 나타낸다.
[aba]babaab[aba]ab
ba와 ab에는 금칙어가 없으므로 두 문자열 모두 처리 결과이다. 길이가 보다 짧은 메시지로는 서로 다른 처리 결과를 만들 수 없다.
이 금칙어 목록에서는 어떤 메시지든 삭제 순서와 관계없이 처리 결과가 같다.
예를 들어 aba에서 앞의 ab를 삭제하거나 뒤의 ba를 삭제하면 모두 a가 남는다.
첫째 줄에 금칙어의 개수 과 각 금칙어의 길이 이 공백으로 구분되어 주어진다.
둘째 줄부터 개의 줄에 걸쳐 금칙어 가 한 줄에 하나씩 주어진다.
메시지 abcd에서 다음과 같이 서로 다른 처리 결과를 얻을 수 있다.
[abc]dda[bcd]a
길이가 이하인 메시지에서는 금칙어를 삭제할 수 있는 부분이 최대 하나이므로, 답은 이다.