题目描述

周五晚上，吉尔讨厌所有火车的两个共同点：

1. 火车总是晚点。
2. 公布的时间表总是错误的。 尽管如此，明天凌晨吉尔必须从图特林根前往弗莱堡，以参加区域编程竞赛。由于她担心迟到而被取消参赛资格，她正在寻找能让她最早到达弗莱堡的火车班次。不过，她也不喜欢太早到达车站，因此如果有多个班次到达时间相同，她会选择出发时间最晚的那一班。

吉尔请你帮她解决这个问题，这样她明天可以多睡一会儿。你需要从给定的铁路时刻表中，计算从一个地点到另一个地点的最快路线（即到达时间最早的班次）。如果有多条路线到达时间相同，则选择出发时间最晚的那条。注意：吉尔换乘火车的速度极快，可以视为瞬时完成（即换乘时间为零）。

输入格式

输入文件包含多个测试场景。每个场景由三部分组成：

第一部分：城市列表

• 第一行是一个整数 $C$（$1 \leq C \leq 100$），表示城市的数量。 • 接下来的 $C$ 行，每行包含一个城市名称（由字母组成）。

第二部分：火车班次

• 第一行是一个整数 $T$（$T \leq 1000$），表示火车的数量。 • 接下来是 $T$ 个火车的描述： • 每个火车描述的第一行是一个整数 $t_i$（$t_i \leq 100$），表示该火车的停靠站点数。 • 接下来的 $t_i$ 行，每行包含一个时间（24小时制，格式为 hhmm）和城市名称，表示火车在该时间到达或离开该城市。

第三部分：查询信息

• 第一行是吉尔的最早出发时间（格式为 hhmm）。 • 第二行是出发城市名称。 • 第三行是目的地城市名称（保证出发城市和目的地城市不同）。

输入文件的最后一行是一个单独的 0（表示输入结束），无需处理。

输出格式

对于每个测试场景，输出以下内容：

1. 第一行打印 Scenario #n，其中 $n$ 是场景编号（从 1 开始）。
2. 如果存在符合条件的路线： • 第二行打印 Departure hhmm 出发城市（时间补零，右对齐）。 • 第三行打印 Arrival hhmm 目的地城市（时间补零，右对齐）。
3. 如果当天（即午夜前）没有可行路线，则打印 No connection。
4. 每个场景结束后输出一个空行。

示例输入 1

3
Tuttlingen
Constance
Freiburg
3
2
0949 Tuttlingen
1006 Constance
2
1325 Tuttlingen
1550 Freiburg
2
1205 Constance
1411 Freiburg
0800
Tuttlingen
Freiburg
2
Ulm
Vancouver
1
2
0100 Ulm
2300 Vancouver
0800
Ulm
Vancouver
0

示例输出 1

Scenario #1
Departure 0949 Tuttlingen
Arrival   1411 Freiburg

Scenario #2
No connection

提示

数据范围： • 城市数量 $C$：$1 \leq C \leq 100$。 • 火车数量 $T$：$T \leq 1000$。 • 每列火车的停靠站点数 $t_i$：$t_i \leq 100$。

时间格式： • 所有时间均为 24 小时制，格式为 hhmm（如 0949 表示 9:49 AM，2300 表示 11:00 PM）。

换乘规则： • 吉尔可以在同一城市的不同火车之间瞬时换乘（无需额外时间）。

最优路线选择：

1. 优先选择到达时间最早的路线。
2. 如果有多条路线到达时间相同，则选择出发时间最晚的那条。

来源

2000年中欧地区编程竞赛