P3683. 约翰神父最忙碌的一天

题目描述

约翰是镇上唯一的神父。9月1日是约翰一年中最忙碌的日子，因为镇上有一个古老的传说：在这一天结婚的夫妇将受到爱神的永恒祝福。今年有$N$对夫妇计划在这个吉祥的日子里举行婚礼。第$i$对夫妇计划在时间$S_i$到$T_i$之间举行婚礼。根据镇上的传统，婚礼必须有一个特殊仪式，夫妇需站在神父面前接受祝福。第$i$对夫妇需要$D_i$分钟来完成这个仪式。此外，这个仪式必须在婚礼的开始或结束时举行（即必须在$S_i$到$S_i + D_i$之间，或在$T_i - D_i$到$T_i$之间）。你能告诉约翰如何安排他的时间表，以便他能参加所有婚礼的特殊仪式吗？

注意，约翰不能同时参加两场婚礼。

输入格式

第一行包含一个整数$N$（$1 \leq N \leq 1000$）。
接下来的$N$行，每行包含$S_i$、$T_i$和$D_i$。$S_i$和$T_i$的格式为hh:mm。

输出格式

第一行输出“YES”或“NO”，表示约翰是否能参加所有特殊仪式。如果是“YES”，则另外输出$N$行，描述所有仪式的开始和结束时间。

输入样例 1

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

输出样例 1

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

来源

POJ Founder Monthly Contest – 2008.08.31, Dagger and Facer