Trains

Trains are great. In Europe you can get almost anywhere by train, even to small towns. In Canada train service is not as extensive, so you often have to change trains several times, and it can be hard to know the quickest route and where to switch. Depending on the time of day, the route may even pass through completely different cities. Fortunately, you can write a program to help.

Given the schedules of trains that run between various places, find all of the shortest connections between two given places. A connection is a shortest connection if there is no other connection that lets you leave later and arrive at the same time or earlier, or leave at the same time and arrive earlier. You do not need to account for the time needed to change trains, because it is already built into the schedule.

The first line of input contains a positive integer $N$, the number of test cases. Each test case begins with a line containing $T$ ($T \le 20$), the number of train routes. Each train route is described by one or more lines that contain:

• $S$ ($S \le 20$): the number of stations on the route, including the origin and the terminus.
• hh:mm: the departure time of the route in 24-hour notation (from 00:00 to 23:59). A train leaves the origin at this time every day. A station name is a string of at most 40 alphabetic characters.
• The names of the $S$ stations in order, separated by the travel time between each pair of adjacent stations. Each travel time is given in hours and minutes.

After the $T$ routes, the test case gives the name of an origin and a destination for which a schedule should be produced. You may assume there is at least one route from the origin to the destination.

For each test case, output the departure time and travel time of every shortest connection from the origin to the destination, ordered by departure time. List each distinct pair of departure and travel time only once, even if several routings produce the same connection times. Print the departure time as hh:mm (exactly two digits each). Print the travel time as h:mm, hh:mm, hhh:mm, and so on, using only as many hour digits as needed with no unnecessary leading zeros. Leave one empty line between the outputs of successive test cases.

For example, in the first test case the first route starts in Windsor at 08:00 and arrives in London at 09:55, Kitchener at 11:30, Guelph at 12:25, Toronto at 13:30, and Montreal at 18:20. To travel from Waterloo to Toronto you can leave at 07:00 and go directly, for a total time of 1:45. You can instead leave at 08:00 and travel through Kitchener and Guelph to Toronto, arriving at 13:30 for a travel time of 5:30. You can leave at 09:00 for Hamilton, Niagara, and Toronto, arriving at 14:00. Finally, you can leave at 23:00 and arrive in Toronto at 07:05 the next morning, for a travel time of 8:05.