지하철

조니는 친구 미셸의 집에 놀러 간다. 아빠는 지하철을 타고 혼자 다녀와도 좋다고 했다. 조니는 지하철 타기를 좋아해서 하루의 절반을 지하에서 보내도 즐겁지만, 아빠는 노선을 갈아타는 횟수를 최대한 줄이라는 조건을 걸었다.

도시에는 역이 아주 많고 역을 잇는 지하철 노선도 여러 개 있다. 모든 열차는 완벽하게 맞물려 운행한다. 한 노선에서 이웃한 두 역 사이를 이동하는 데 정확히 1분이 걸리고, 역에서 노선을 갈아타는 데는 시간이 전혀 걸리지 않는다.

지하철 노선도가 주어진다. 아빠의 조건을 지키면서 조니가 지하에 가장 오래 머무는 경로를 찾아라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 테스트 케이스가 차례로 주어진다.

각 테스트 케이스는 빈 줄로 시작한다. 다음 두 줄은 각각 Stops:와 Lines:로 시작하고, 모든 역 이름과 모든 노선 이름을 쉼표와 공백으로 구분해 나열한다. 그다음에는 노선마다 한 줄이 순서에 상관없이 주어진다. 이 줄은 <line-name> route:로 시작하고 그 노선이 지나는 역을 순서대로 나열한다. 마지막 두 줄은 조니의 집 근처 역과 미셸의 집 근처 역을 알려준다. 두 역은 서로 다르다.

한 테스트 케이스에서 역은 최대 300,000개, 노선은 최대 100,000개이고 모든 노선의 길이를 합한 값은 1,000,000을 넘지 않는다. 노선과 역의 이름은 1자 이상 50자 이하이고 영문자, 숫자, 하이픈(-), 어퍼스트로피('), 앰퍼샌드(&)로 이루어진다. 모든 노선은 양방향으로 운행하지만 진행 방향을 바꾸는 것도 노선을 갈아타는 것으로 센다. 또 어떤 노선도 자기 자신과 교차하지 않아서 한 노선이 같은 역을 두 번 지나지 않는다.

테스트 케이스가 입력에 나온 순서대로 답을 출력한다. 각 테스트 케이스마다 optimal travel from <start> to <finish>: <L> lines, <M> minutes 형식으로 한 줄을 출력한다.

<start>와 <finish>에는 입력에 적힌 두 역 이름을 그대로 쓴다. <L>은 조니가 타는 노선의 개수이고 <M>은 전체 이동 시간을 분으로 나타낸 값이다. <L>은 목적지에 도착하는 데 필요한 가장 적은 노선 개수이고, <M>은 노선을 정확히 <L>개 타는 경로 가운데 이동 시간이 가장 긴 값이다. 열차에 오르는 횟수를 모두 세므로 한 노선을 타고 다른 노선으로 갈아탄 뒤 처음 노선으로 돌아오면 노선 3개를 탄 것이다. <L>이 1이면 lines 대신 line을 쓰고, <M>이 1이면 minutes 대신 minute을 쓴다. 이런 경로는 항상 존재한다고 가정해도 된다.