문자열 분해

검색 시스템의 알고리즘과 시스템을 만들 때는 식을 나누어 분석하는 부분이 중요한 역할을 한다. 이 문제를 푸는 알고리즘은 많이 고안되었으며, 실행 시간, 구현의 난이도, 사용하는 자원의 양이 서로 다르다.

문자열이 사전의 단어들로만 이루어졌는지 확인하는 문제를 생각해 보자. 가장 간단한 방법은 탐욕 알고리즘이다. 매 단계마다 문자열에서 그 자체로 사전에 있는 가장 긴 접두사를 지운다. 사전 단어들을 이어 붙여 만든 충분히 큰 문자열 집합에서는 이 방법이 성공하여 문자열을 단어로 나눈다. 구현도 아주 간단하다. 하지만 잘못된 결과를 내는 문자열도 있다. 예를 들어 사전이 영어 단어 전체라면 "workingrass"는 올바르게 인식되지 않는다. 먼저 "working" 접두사가 지워지고, 남은 "rass"는 단어로 나눌 수 없기 때문이다. 그러나 이 문자열은 "work", "in", "grass"를 이어 붙인 것이다.

모든 사전이 영어 사전인 것은 아니다. 어떤 사전에서는 탐욕 알고리즘이 사전 단어들을 이어 붙인 모든 문자열을 올바르게 나눈다. 주어진 사전이 이런 성질을 갖는지 확인하라. 그렇지 않다면 사전 단어로 나눌 수는 있지만 탐욕 알고리즘으로는 나눌 수 없는 문자열의 예를 하나 제시하라. 그런 문자열이 여럿이라면 가장 짧은 것, 즉 길이가 다른 문자열보다 크지 않은 것을 찾아라. 가장 짧은 것도 여럿이라면 그중 아무거나 하나를 출력하라.

첫째 줄에 사전의 단어 개수 $n$ ($1 \le n \le 250$)이 주어진다. 다음 $n$개 줄에는 사전의 단어가 한 줄에 하나씩 주어진다. 각 단어는 비어 있지 않으며 소문자 라틴 알파벳으로만 이루어져 있다. 각 단어의 길이는 500을 넘지 않는다.

조건을 만족하는 문자열이 존재하면, 그중 길이가 다른 답보다 크지 않은 문자열 하나를 출력한다. 출력하는 문자열은 소문자 라틴 알파벳으로만 이루어져야 한다. 존재하지 않으면 "Good vocabulary!"를 출력한다.