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