토달기

희현이는 선생님이 말한 단어에 알파벳 소문자 한 글자를 끼워 넣어 새 단어를 만드는 놀이를 좋아한다. 한 번의 행동에서는 단어의 맨 앞, 맨 뒤, 또는 중간 아무 위치에 한 글자를 추가할 수 있다. 만들어진 단어는 반드시 사전에 등재되어 있어야 한다.

사전에는 d개의 단어가 있으며, 각 단어는 길이 80 이하의 알파벳 소문자로만 이루어져 있다. 선생님이 처음 말한 세 글자 단어에서 시작해 이 규칙을 반복할 때 만들 수 있는 가장 긴 단어를 구하라.

첫 줄에 사전에 등재된 단어의 수 d와 시작 단어가 주어진다. (1 ≤ d ≤ 1,000) 시작 단어의 길이는 3이고, 시작 단어는 사전에 포함되어 있다.

다음 d개의 줄에는 사전에 등재된 단어가 한 줄에 하나씩 주어진다.

규칙을 지키며 만들 수 있는 단어 중 가장 긴 단어 하나를 출력한다. 가능한 답이 여러 개라면 아무거나 출력해도 된다.

cal에서 시작해 coal, coral, choral, chorale 순서로 한 글자씩 추가하면 가장 긴 단어에 도달할 수 있다.