'''
当做一个2-SAT问题看待,
每一对情侣看做一个变量x(i) x(i)要么取0,要么取1,取1表示选择开始的区间做仪式,取0表示选择结束的区间
做仪式, x(i)不论取0还是取1, 情侣对应的开始区间和结束区间都会被选择一个,所以一组合法的x序列就对应了
一种合法的选择方式,是否合法需要验证是否会出现区间覆盖的矛盾
把所有x(i) 和 ~x(i)表示的区间都算出来,暴力枚举一遍所有发生了覆盖的区间,如果 A B发生覆盖
那么 A and B 不能成立,等价于 ~(A and B) = 1 要成立,等价于 ~A or ~B 成立,因此添加
一个2-SAT需要满足的命题 ~A or ~B, 构造一个约束
利用2-SAT模型计算x序列的合法解即可
'''
from typing import List, Tuple
import sys
sys.setrecursionlimit(999999)
class TWO_SAT:
# max_node_num表示xi有多少个,所有命题应该是x(1), x(2), ...... x(max_node_num序列)
# edges为边序列, i -> j 边表示 x(i) or x(j) 成立 (也表示x(j) or x(i)成立,两个是等价的)
# 若i是负的,代表 非x(i)
def __init__(self, edges, max_node_num):
self.max_node_num = max_node_num
self.edges = edges
# 返回一组x向量的取值,[0, x(1), x(2), x(3), ...... x(max_node_num)]
# 返回None代表无解
def getSolution(self):
e = []
n = self.max_node_num
for a, b in self.edges:
aa = -a if a < 0 else a+n
bb = -b+n if b < 0 else b
e.append((aa, bb))
aa = -a+n if a < 0 else a
bb = -b if b < 0 else b+n
e.append((bb, aa))
max_node_num = 2*self.max_node_num
link = [[] for _ in range(max_node_num + 1)]
dfn = [0x7fffffff] * (max_node_num + 1)
low = [0x7fffffff] * (max_node_num + 1)
node2sccid = [0] * (max_node_num + 1)
global_time = [0]
for a, b in self.edges:
aa = -a if a < 0 else a+n
bb = -b+n if b < 0 else b
link[aa].append(bb)
aa = -a+n if a < 0 else a
bb = -b if b < 0 else b+n
link[bb].append(aa)
stack = [0] * (max_node_num+1)
stack_size = [0]
visit = [0] * (max_node_num + 1)
scc_id_cnt = [1]
def dfs(cur):
global_time[0] += 1
dfn[cur], low[cur] = global_time[0], global_time[0]
stack[stack_size[0]] = cur
stack_size[0] += 1
pos = stack_size[0] - 1
for next in link[cur]:
if visit[next] == 1:
continue
if dfn[next] == 0x7fffffff:
dfs(next)
low[cur] = min(low[cur], low[next])
else:
low[cur] = min(low[cur], dfn[next])
if low[cur] == dfn[cur]:
# dfn 和 low 相等时候,一直退栈退到cur出栈为止
for node in stack[pos:stack_size[0]]:
node2sccid[node] = scc_id_cnt[0]
visit[node] = 1
scc_id_cnt[0] += 1
stack_size[0] = pos
for node in range(1, max_node_num + 1):
if len(link[node]) == 0:
continue
if dfn[node] == 0x7fffffff:
dfs(node)
x = [0] * (n+1)
for node in range(1, n+1):
if node2sccid[node] == node2sccid[node+n] and node2sccid[node] != 0:
return None
if node2sccid[node] < node2sccid[node+n]:
x[node] = 1
return x
def minute_val(s):
a, b = map(int, s.split(':'))
return a * 60 + b
def minute_val2str(val):
return '{:02d}:{:02d}'.format(val // 60 , val % 60)
def is_overlap(s1, t1, s2, t2):
return max(s1, s2) < min(t1, t2)
n = int(input())
ss = sys.stdin.readlines()
node2str = {}
node2pair = {}
edges = []
for i, s in enumerate(ss):
node = i + 1
part = s.split()
start, end = map(minute_val, part[:2])
period = int(part[2])
node2str[node] = minute_val2str(start) + ' ' + minute_val2str(start + period)
node2str[-node] = minute_val2str(end-period) + ' ' + minute_val2str(end)
node2pair[node] = (start, start + period)
node2pair[-node] = (end-period, end)
for a in range(-n, n+1):
if a == 0:
continue
s1, t1 = node2pair[a]
for b in range(a+1, n+1):
if b == 0:
continue
s2, t2 = node2pair[b]
if is_overlap(s1, t1, s2, t2):
edges.append((-a, -b))
algo = TWO_SAT(edges, n)
ans = algo.getSolution()
if ans is not None:
print('YES')
for node in range(1, n+1):
if ans[node] == 1:
print(node2str[node])
else:
print(node2str[-node])
else:
print('NO')