题目描述

火车旅行很酷。在欧洲，你可以乘火车到达几乎任何地方，包括小镇。但在加拿大，火车服务就没那么好了。有时你需要多次换乘，而且往往很难找到最快的路线和换乘点。根据时间的不同，路线甚至可能经过完全不同的城市。幸运的是，你可以编写一个程序来帮助你。给定不同地点之间的火车时刻表，你的任务是找出两地之间的所有最短连接路线。最短连接路线是指没有其他路线可以让你更晚出发却在相同或更早时间到达，或者相同时间出发但更早到达的路线。换乘时间无需考虑，因为它已经包含在时刻表中。

输入格式

第一行输入一个正整数$N$，表示测试用例的数量。每个测试用例的第一行包含$T\leq20$，表示火车路线的数量。每条火车路线由以下内容描述：

• $S\leq20$：该路线包含的车站数量（包括起点和终点）。
• $hh:mm$：路线的发车时间（24小时制，范围从$00:00$到$23:59$）。假设火车每天在这个时间从起点发车。
• 车站名称列表：由不超过$40$个字母字符组成的字符串，相邻车站之间用旅行时间（小时和分钟）分隔。

最后，每个测试用例给出一个起点和终点名称，要求生成从该起点到终点的时刻表。假设至少存在一条从指定起点到终点的路线。

输出格式

输出从起点到终点的所有最短连接路线的出发时间和旅行时间，按出发时间排序。即使存在多条路线具有相同的出发和到达时间，也只需列出一次。出发时间应以$hh:mm$格式给出（即两位数表示小时和分钟），而旅行时间应以$h:mm$、$hh:mm$、$hhh:mm$等格式给出，以避免不必要的前导零。连续测试用例的输出之间用空行分隔。

示例输入

1  
7  
6 08:00 Windsor 1:55 London 1:35 Kitchener 0:55 Guelph 1:05 Toronto 4:50 Montreal  
2 08:00 Waterloo 0:45 Kitchener  
3 09:00 Waterloo 1:45 Hamilton 1:05 Niagara  
2 12:00 Niagara 2:00 Toronto  
2 07:00 Waterloo 1:45 Toronto  
2 23:00 Waterloo 0:55 Guelph  
2 06:00 Guelph 1:05 Toronto  
Waterloo Toronto  

示例输出

07:00 1:45  
08:00 5:30  
09:00 5:00  
23:00 8:05  

示例说明

示例中的第一条路线从Windsor在$08:00$发车，依次经过London（$09:55$到达）、Kitchener（$11:30$）、Guelph（$12:25$）、Toronto（$13:30$）和Montreal（$18:20$）。从Waterloo到Toronto的最短连接路线包括：

1. $07:00$出发，直达Toronto，旅行时间$1:45$；
2. $08:00$出发，经Kitchener、Guelph到Toronto，$13:30$到达，旅行时间$5:30$；
3. $09:00$出发，经Hamilton、Niagara到Toronto，$14:00$到达，旅行时间$5:00$；
4. $23:00$出发，次日$07:05$到达Toronto，旅行时间$8:05$。