나비족 길찾기

판도라의 나비족 마을은 거대한 홈트리(hometree) 안에 자리 잡고 있다. 각 홈트리는 나비족이 즐겨 먹는 한 종류의 과일을 기른다. 네이티리의 어머니 모아트는 주어진 두 홈트리 사이에서, 숲에 존재하는 모든 서로 다른 과일 종류를 정확히 한 번씩 모을 수 있는 가장 짧은 경로를 찾아 달라고 부탁한다. 경로는 어떤 홈트리를 지날 때마다 그 홈트리가 기르는 과일을 모으므로, 유효한 경로는 숲 어딘가에 등장하는 과일 종류마다 정확히 하나의 홈트리를 지나야 한다. 그러한 경로의 길이를 계산하라. 판도라에는 홈트리가 매우 많으므로, 가능한 모든 경로를 나열해 가장 짧은 것을 고르는 방식으로는 풀 수 없다.

입력은 하나 이상의 독립적인 인스턴스로 이루어진다. 각 인스턴스는 GRAPH BEGIN이라고 적힌 줄로 시작하고 GRAPH END라고 적힌 줄로 끝난다.

이 두 표시 줄 사이의 각 줄은 하나의 홈트리를 설명한다. 이름, 그 홈트리가 기르는 정수 과일 종류, 그리고 (선택적으로) 새로 추가되는 연결을 나타낸다. 연결이 있는 줄은 다음 형태이다.

<이름> <과일> <거리> <이웃1> <이웃2> ...

이는 홈트리 <이름>(과일 <과일>을 기름)과, 나열된 각 이웃까지 길이 <거리>인 간선을 선언한다. 한 줄에 적힌 모든 이웃까지의 거리는 같다. <이름> <과일> 형태의 줄은 새로운 연결을 추가하지 않는 홈트리를 선언한다.

모든 간선은 양방향이며 모든 거리는 양의 정수이다. 임의의 홈트리에서 다른 모든 홈트리로 도달할 수 있음이 보장된다. 각 홈트리는 어떤 줄의 첫 번째 항목으로 적어도 한 번 등장하며, 등장할 때마다 과일 종류는 항상 같다. 같은 홈트리가 여러 줄의 첫 번째 항목으로 나타나 간선을 더 추가할 수도 있다. 개별 연결은 최대 한 번만 나열된다.

GRAPH END 뒤의 줄들은 질의이며, 한 줄에 하나씩 두 홈트리의 이름을 담는다. 질의가 끝나면 또 다른 GRAPH BEGIN으로 새로운 인스턴스가 시작될 수 있으며, 이때는 완전히 처음부터 다시 시작한다.

과일 종류는 정수이고, 모든 정수가 반드시 등장할 필요는 없다. 실제로 어떤 홈트리가 기르는 과일 종류만 모으면 된다.

각 질의에 대해, 주어진 순서 그대로 두 홈트리의 이름을 출력한 뒤, 서로 다른 모든 과일 종류를 정확히 한 번씩 모으는 두 홈트리 사이 최단 경로의 길이를 출력한다. 길이는 소수점 아래 한 자리를 가진 수로 출력한다(예: 4.0). 모든 거리가 양의 정수이므로 이 길이는 항상 정수이며 끝에 .0이 붙는다. 그러한 경로가 없으면 길이 대신 NONE을 출력한다.

예를 들어 아래 첫 번째 인스턴스에서 경로 a → b → c → d는 네 가지 과일 종류(1, 2, 3, 5)를 모두 모으며 길이는 4.0이다. 그러나 a와 c 사이에는 유효한 경로가 없다. a → b → c → d → c는 모든 과일 종류를 모으지만 과일 1을 두 번 모으므로 허용되지 않는다.

각 홈트리의 음영 상자는 그 홈트리가 기르는 과일 종류를 나타낸다.