단어 사다리

시간 제한1초메모리 제한128 MB

요약

주어진 단어 목록에서 한 글자를 바꾸거나 더하거나 지우는 이동만 허용할 때, 두 단어 사이 최단 사다리 길이의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, BFS, 해시맵, 문자열
정답자: 아직 제출이 없습니다

문제

당신은 어느 퍼즐 회사에서 일하게 되었습니다. 이 회사에는 단어 사다리(Word Ladder)라고 부르는 퍼즐이 있습니다. 푸는 사람은 주어진 시작 단어에서 출발해 한 번에 한 글자씩 바꾸어 목표 단어에 도달하며, 이때 사슬(chain)에 등장하는 어떤 단어도 두 번 이상 나타나서는 안 됩니다. 한 단어에서 다른 단어로 한 걸음 이동하는 방법은 다음 세 가지입니다.

한 글자를 바꾼다
한 글자를 추가한다
한 글자를 제거한다

예를 들어 COT에서 CAT으로 가는 것은 한 걸음이고, CAT에서 SCAT으로 가는 것도 한 걸음, SCAT에서 SAT으로 가는 것도 한 걸음입니다. 다음은 COT에서 SCAT으로 가는 하나의 단어 사다리입니다.

COT ⇒ CAT ⇒ SAT ⇒ SCAT

다음은 COT에서 SCAT으로 가는 또 다른 단어 사다리입니다.

COT ⇒ CAT ⇒ SCAT

단어 사다리의 길이는 그 안에 들어 있는 단어의 개수입니다. 따라서 위의 두 예는 각각 길이 4인 사다리와 길이 3인 사다리를 보여 줍니다. 두 번째 사다리는 COT과 SCAT 사이에서 가능한 가장 짧은 사다리입니다. 더 짧은 사다리가 더 긴 사다리보다 좋은 것으로 여겨집니다.

이 회사는 두 단어가 주어지면 똑똑한 풀이자가 항상 그 둘 사이의 가장 좋은(즉, 가장 짧은) 사다리를 찾아낸다는 것을 알고 있습니다. 풀이자에게 도전 과제를 주기 위해, 회사는 긴 단어 사다리를 찾고 있습니다. 제한된 어휘가 주어졌을 때, 그 어휘에 속한 단어만 사용하여 똑똑한 풀이자가 찾아낼 수 있는 가장 긴 단어 사다리의 길이, 즉 모든 가장 좋은 사다리들 가운데 가장 긴 것의 길이를 구하세요.

입력

입력은 여러 개의 데이터 집합으로 이루어집니다. 각 데이터 집합은 어휘에 들어 있는 단어의 수를 나타내는 정수 $N$ ( $1 \le N \le 500$ )으로 시작하고, 그다음 줄부터 단어가 한 줄에 하나씩 주어집니다.

각 단어는 1글자 이상 50글자 이하의 소문자 알파벳으로만 이루어집니다. 그 밖의 다른 문자나 공백은 없습니다.

입력의 끝은 0 하나만 있는 줄로 표시됩니다.

출력

각 데이터 집합에 대해, 똑똑한 풀이자가 찾아낼 수 있는 가장 긴 사다리의 길이를 나타내는 정수 하나를 한 줄에 출력하세요.

예제1

예제 1

입력

4
cat
cot
scat
sat
7
welcome
to
the
acm
regional
programming
contest
0

예상 출력

3
1