기차

기차는 편리합니다. 유럽에서는 작은 마을을 포함해 거의 모든 곳을 기차로 갈 수 있습니다. 캐나다에서는 기차 노선이 그만큼 촘촘하지 않아 여러 번 환승해야 할 때가 많고, 가장 빠른 경로와 어디서 갈아타야 하는지 알기 어렵습니다. 하루 중 시간대에 따라 최적 경로가 완전히 다른 도시들을 지나기도 합니다. 다행히 이를 도와주는 프로그램을 작성할 수 있습니다.

여러 장소 사이를 운행하는 기차 시간표가 주어질 때, 두 장소 사이의 모든 최단 연결을 찾으세요. 어떤 연결이 최단 연결이라는 것은, 그보다 더 늦게 출발해 같은 시각이나 더 이른 시각에 도착하거나, 같은 시각에 출발해 더 이른 시각에 도착하는 다른 연결이 존재하지 않는다는 뜻입니다. 환승에 필요한 시간은 이미 시간표에 반영되어 있으므로 따로 고려할 필요가 없습니다.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 양의 정수 $N$이 주어집니다. 각 테스트 케이스의 첫 줄에는 기차 노선의 수 $T$ ($T \le 20$)가 주어집니다. 각 기차 노선은 다음 정보를 담은 한 줄 이상으로 기술됩니다.

• $S$ ($S \le 20$): 출발지와 종착지를 포함한 노선 위 역의 수.
• hh:mm: 24시간 표기법으로 나타낸 노선의 출발 시각 (00:00부터 23:59까지). 기차는 매일 이 시각에 출발지를 떠납니다. 역 이름은 최대 40자의 알파벳 문자열입니다.
• $S$개 역의 이름을 순서대로 나열하되, 인접한 두 역 사이의 이동 시간으로 구분합니다. 각 이동 시간은 시와 분으로 주어집니다.

$T$개의 노선 다음에는 시간표를 만들 출발지와 도착지의 이름이 주어집니다. 출발지에서 도착지로 가는 노선이 적어도 하나 존재한다고 가정해도 됩니다.

각 테스트 케이스마다, 출발지에서 도착지로 가는 모든 최단 연결의 출발 시각과 이동 시간을 출발 시각 순으로 출력합니다. 여러 경로가 같은 연결 시각을 만들더라도, 서로 다른 (출발 시각, 이동 시간) 쌍은 한 번씩만 출력합니다. 출발 시각은 hh:mm 형식으로 (각각 정확히 두 자리) 출력합니다. 이동 시간은 불필요한 앞자리 0 없이 필요한 만큼의 자릿수만 사용하여 h:mm, hh:mm, hhh:mm 등의 형식으로 출력합니다. 연속한 테스트 케이스의 출력 사이에는 빈 줄을 하나 둡니다.

예를 들어, 첫 번째 테스트 케이스의 첫 노선은 08:00에 Windsor에서 출발하여 London에 09:55, Kitchener에 11:30, Guelph에 12:25, Toronto에 13:30, Montreal에 18:20에 도착합니다. Waterloo에서 Toronto로 가려면 07:00에 출발해 곧바로 이동하여 총 1:45가 걸릴 수 있습니다. 또는 08:00에 출발해 Kitchener와 Guelph를 거쳐 Toronto에 13:30에 도착하면 이동 시간은 5:30입니다. 09:00에 출발해 Hamilton, Niagara를 거쳐 Toronto에 14:00에 도착할 수도 있습니다. 마지막으로 23:00에 출발하면 다음 날 아침 07:05에 Toronto에 도착하여 이동 시간은 8:05가 됩니다.