트럭의 역사

Advanced Cargo Movement, Ltd.는 여러 종류의 트럭을 사용한다. 어떤 트럭은 채소 배달에, 다른 트럭은 가구나 벽돌 운반에 쓰인다. 회사는 각 트럭 종류를 설명하는 자체 코드를 가지고 있다. 이 코드는 정확히 7개의 소문자 알파벳으로 이루어진 문자열이다(각 위치의 글자마다 특별한 의미가 있지만, 이 문제에서는 중요하지 않다). 회사 역사의 초기에는 단 하나의 트럭 종류만 사용되었지만, 이후 그것으로부터 다른 종류들이 파생되었고, 다시 그 새로운 종류들로부터 또 다른 종류들이 파생되는 식으로 이어졌다.

오늘날 이 회사는 자신의 역사를 연구할 역사학자를 고용할 만큼 부유하다. 역사학자들이 알아내고자 한 것 중 하나는 이른바 '파생 계획', 즉 트럭 종류들이 어떤 순서로 파생되었는가이다. 그들은 두 트럭 종류 사이의 거리를 두 코드에서 서로 다른 글자가 있는 위치의 개수로 정의했다. 또한 각 트럭 종류는 정확히 다른 한 종류로부터 파생되었다고 가정한다(단, 어느 종류로부터도 파생되지 않은 최초의 종류는 예외이다). 파생 계획의 품질은 다음과 같이 정의된다.

$\frac{1}{\sum_{(t_o, t_d)} d(t_o, t_d)}$

여기서 합은 파생 계획에 속한 모든 쌍에 대해 취하며, $t_o$는 원본 종류, $t_d$는 그로부터 파생된 종류이고, $d(t_o, t_d)$는 두 종류 사이의 거리이다.

트럭 종류들의 코드가 주어질 때, 가능한 파생 계획 중 가장 높은 품질을 구하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 트럭 종류의 개수 $N$($2 \le N \le 2000$)이 적힌 줄로 시작한다. 그 다음 $N$개의 줄에는 각각 하나의 트럭 종류 코드(7개의 소문자 알파벳으로 이루어진 문자열)가 주어진다. 코드들은 트럭을 유일하게 구별하며, $N$개의 줄 중 서로 같은 것은 없다. 입력은 트럭 종류의 개수 자리에 $0$이 주어지는 줄로 끝난다.

각 테스트 케이스마다 The highest possible quality is 1/Q. 형식의 줄을 하나 출력한다. 여기서 $1/Q$는 가장 좋은 파생 계획의 품질이며, $Q$는 가능한 모든 파생 계획에서 거리의 합이 최소가 되는 값이다.