题目描述

你经营着一个连接$n$个城市（编号$1$至$n$）的铁路系统。每班列车严格按时刻表运行（直达不停靠），各车站仅提供直达列车的发车时刻表。乘客从城市$p$到$q$可通过换乘实现，换乘时间视为$0$，但需满足后列车发车时间不早于前列车到站时间。

最优连接定义为：不存在其他从$p$出发时间不早于$A$且到达$q$时间不早于$B$的路线。仅考虑当日可达的路线。

输入格式

• 第一行：$n$（城市数，$2 \leq n \leq 10^5$）
• 后续$n$组时刻表（城市$1$到$n$）：
  • 首行为$m$（车次数量）
  • 随后$m$行：发车时间$A$（hh:mm）、到站时间$B$（$A<B$）、目的城市$t$（$1 \leq t \leq n$）
• 所有时刻表按发车时间非递减排序
• 总车次数不超过$10^6$

输出格式

• 第一行：$r$（最优连接数量）
• 随后$r$行：每行包含发车时间$A$和到站时间$B$（hh:mm格式），按$A$递增排序（相同路线仅输出一次）

样例输入

3
3
09:00 15:00 3
10:00 12:00 2
11:00 20:00 3
2
11:30 13:00 3
12:30 14:00 3
0

样例输出

2
10:00 14:00
11:00 20:00

提示

输入数据量较大，建议使用scanf而非cin以避免超时

题目来源

2002年西南欧地区竞赛