题目背景

译自 COCI 2024/2025 #3 T1。$\texttt{1s,0.5G}$。满分为 $50$。

题目描述

马尔纳先生决定前往位于波兰西南部的 Wrocław；但是从 Zagreb（他所在的城市）到 Wrocław 并没有直达的巴士线路，于是他只能经过奥地利城市 Graz 并进行换乘。

马尔纳先生找到了一份在 Zagreb-Graz 和 Graz-Wrocław 之间运行的巴士时刻表，其中包含了 $n$ 趟巴士的运行信息；每趟巴士每天都会在特定的运行线路和特定的时间运行。具体地，对于每趟巴士，该时刻表给出了它的运行线路（Zagreb-Graz 或 Graz-Wrocław），以及它的发车时间（精确到分钟，该巴士会在该分钟初发车）和到达时间（精确到分钟，该巴士会在该分钟末到达）。

换乘所需的时间可以忽略不计，即如果在下一趟巴士出发前到达换乘站点，就可以顺利换乘；但是第一趟巴士的到达时间必须严格早于第二趟巴士的发车时间。

确定马尔纳先生从 Zagreb 到 Wrocław 所需要的最短时间；或报告不存在任何一种乘坐巴士的方案使他可以到达 Wrocław。

输入格式

第一行，一个正整数 $n$。

接下来 $n$ 行，每行先给出两个使用 $\texttt{-}$ 连接的城市名称，表示该趟巴士运行的线路；接着给出发车时间和到达时间，格式为 $\texttt{h:mm--h:mm}$，其中 $\texttt{h}$ 表示小时，$\texttt{mm}$ 表示分钟（注意，其中的分钟数始终包含两位数字；换言之，如果分钟数是个位数，那么会补上一个前导 $0$）。保证每趟巴士运行时长最多为 $24$ 小时。

输出格式

如果存在一种乘坐巴士的方案使得马尔纳先生可以从 Zagreb 到达 Wrocław，那么输出一行一个字符串形如 $\texttt{h:mm}$，表示旅程所需要的最短时间。

如果不存在任何一种乘坐巴士的方案，输出一行一个字符串 $\texttt{NEMOGUCE}$。

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

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

NEMOGUCE

提示

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 200$；
• 每趟巴士运行时长最多为 $24$ 小时。