#5703. 「COCI 2024/2025 #3」Autobus

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #3 T1「Autobus」

Mr. Malnar 决定去造访他尚未去过的少数城市之一——位于波兰西南部的 Wroclaw。由于他已经很久没有乘坐长途汽车旅行了，他非常怀念这种体验；然而，当他得知 Zagreb 和 Wroclaw 之间没有直达的长途汽车线路时，感到十分失望。

最好的选择是在奥地利的 Graz 市进行中转。Mr. Malnar 找到了一份时刻表，即一份在 Zagreb-Graz 和 Graz-Wroclaw 路线运营的长途汽车线路列表。特定路线上的长途汽车每天运行，正好在出发时间分钟的开始时刻出发，并在到达时间分钟的最后时刻精确到达。中转所需的时间可以忽略不计，也就是说，如果你在想换乘的汽车出发之前到达目的地，就可以上车（第一辆车的到达时间必须严格小于第二辆车的出发时间）。

请确定从 Zagreb 到 Wroclaw 所需的最短旅行时间。

输入格式

第一行包含一个正整数 $n$ $(1 \leq n \leq 200)$，表示长途汽车线路的数量。

在接下来的 $n$ 行中，依次给出了由符号 $\texttt{-}$ 连接的两个城市的名称，第一个代表出发城市，第二个代表目的地城市，后面跟着以 $\texttt{h:mm--h:mm}$ 格式表示的出发时间和到达时间，其中 $\texttt{h}$ 表示小时，$\texttt{mm}$ 表示该时间的分钟数。请注意，分钟将始终显示为两位数字。如果分钟数是个位数，则会包含前导零。保证每次行程（无需换乘）最多持续 $24$ 小时。

输出格式

如果能够从 Zagreb 前往 Wroclaw，请在第一行以 $\texttt{h:mm}$ 格式（如上所述）输出旅行时间。

如果无法实现，请在第一行输出 NEMOGUCE（克罗地亚语意为 "不可能"）。

样例 1

输入

4
Zagreb-Graz 15:30--23:59
Graz-Wroclaw 10:42--19:15
Zagreb-Graz 14:13--20:19
Graz-Wroclaw 2:25--5:00

输出

13:31

样例 2

输入

3
Zagreb-Graz 6:05--16:40
Zagreb-Graz 20:00--21:40
Zagreb-Graz 9:56--22:36

输出

NEMOGUCE

数据范围与提示

详细子任务附加限制及分值如下表所示。