0x60图论（0x67 Tarjan算法与有向图连通性）例题5：牧师约翰最忙碌的一天

题目描述

有 $N$ 对情侣在同一天准备结婚，每对情侣都预先计划好了婚礼举办的时间，其中第 $i$ 对情侣的婚礼从时刻 $S_i$ 开始，到时刻 $T_i$ 结束。

婚礼有一个必须的仪式,这个仪式要么在婚礼开始时举行，要么在结束时举行。

第 $i$ 对情侣需要 $D_i$ 分钟完成这个仪式，即必须选择 $S_i \sim S_i+D_i$ 或 $T_i−D_i \sim T_i$ 两个时间段之一。

牧师想知道他能否满足每场婚礼的要求，即给每对情侣安排 $S_i \sim S_i+D_i$ 或  $T_i−D_i \sim T_i$ ，使得这些仪式的时间段不重叠。

若能满足，还需要帮牧师求出任意一种具体方案。

输入格式

第一行包含整数 $N$（$1 \le N \le 1000$）。

接下来 $N$ 行，每行包含$S_i \ T_i \ D_i$ ,其中 $S_i$ 和 $T_i$ 是hh:mm形式。

输出格式

第一行输出能否满足，能则输出”YES”，否则输出”NO”。

接下来N行，每行给出一个具体时间段安排。

输入输出样例

输入 #1

2
08:00 09:00 30
08:15 09:00 20

输出 #1

YES
08:00 08:30
08:40 09:00