题目大意

有$n$对新人要举行仪式，每对都有两个时间段可以选择

问：输出是否可以所有新人的仪式时间不重叠

如果可以满足楼上的条件，还需输出方案

数据范围

$1\leqslant n\leqslant 1000$

题解

对于两个冲突的时间段就只能选择其中一个，$2-SAT$

$2-SAT$有对称性，我们可以$get$到一个做题顺序

1．构图1

2．求图1的极大强连通子图(tarjan)

3．把每个子图收缩成单个节点，根据原图关系构造一个有向无环图2

4．判断是否有解，无解则输出（退出）

5. 在图2的道路全部反向，构造新图3

6．对图3进行拓扑排序

7．在图3中自底向上进行选择、删除

8．输出  

对于第5步

我们知道造出图2之后，如果选择一个节点，那么会把"选择"标记一路传下去，那么如果传到两个互相矛盾的节点，这个方案就是不成立的

然而如果改成反向的道路，就是不选择一个节点，那么会把"不选择"标记一路传下去，两个彼此矛盾的节点都不选择是成立的

所以我们传递的是"不选择"标记

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n,edge_tot,scc_tot,dfn_tot,top;
int l[2050],r[2050],belong[2050],opp[2050];
int dfn[2050],low[2050],q[2050],flag[2050];
struct edge{int to,next;}e[2000500],e2[2000500];
int last[2050],last2[2050],d[2050];
int colour[2050];

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline bool coin(int x,int y){
    if ((l[x]>=r[y])||(r[x]<=l[y])) return 0;
    return 1;
}
inline void init(){
    n=read();int x;
    for(int i=1;i<=n;++i){
        l[(i<<1)-1]=read();l[(i<<1)-1]=l[(i<<1)-1]*60+read();
        r[i<<1]=read();r[i<<1]=r[i<<1]*60+read();
        x=read();
        l[i<<1]=r[i<<1]-x;r[(i<<1)-1]=l[(i<<1)-1]+x;
    }
}
inline void insert(int u,int v) {e[++edge_tot].to=v;e[edge_tot].next=last[u];last[u]=edge_tot;}
inline void reinsert(int u,int v) {d[v]++;e2[++edge_tot].to=v;e2[edge_tot].next=last2[u];last2[u]=edge_tot;}
inline void build(){
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j){
            if (coin((i<<1)-1,(j<<1)-1)) {insert((i<<1)-1,j<<1);insert((j<<1)-1,i<<1);}
            if (coin((i<<1)-1,j<<1)) {insert((i<<1)-1,(j<<1)-1);insert(j<<1,i<<1);}
            if (coin(i<<1,(j<<1)-1)) {insert(i<<1,j<<1);insert((j<<1)-1,(i<<1)-1);}
            if (coin(i<<1,j<<1)) {insert(i<<1,(j<<1)-1);insert(j<<1,(i<<1)-1);}
        }
}
void tarjan(int x){
    dfn[x]=low[x]=++dfn_tot;
    q[++top]=x;flag[x]=1;
    for(int i=last[x];i;i=e[i].next)
        if (!dfn[e[i].to]) {tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
        else if (flag[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
    if(low[x]==dfn[x]){
        int now=0;scc_tot++;
        while (now!=x){
            now=q[top--];
            flag[now]=0;
            belong[now]=scc_tot;
        }
    }
}
inline void rebuild(){
    edge_tot=0;
    for(int i=1;i<=2*n;++i)
        for(int j=last[i];j;j=e[j].next)
            if (belong[i]!=belong[e[j].to]) reinsert(belong[e[j].to],belong[i]);
    for(int i=1;i<=n;++i){
        opp[belong[(i<<1)-1]]=belong[i<<1];
        opp[belong[i<<1]]=belong[(i<<1)-1];
    }
}
void dfs(int x){
    if (colour[x]) return;
    colour[x]=-1;
    for(int i=last2[x];i;i=e2[i].next) dfs(e2[i].to);
}
inline void topsort(){
    for(int i=1;i<=scc_tot;++i) if (!d[i]) q[++top]=i;
    while (top){
        int now=q[top--];
        if (colour[now]) continue;
        colour[now]=1;dfs(opp[now]);
        for(int i=last2[now];i;i=e2[i].next){
            d[e2[i].to]--;
            if (!d[e2[i].to]) q[++top]=e2[i].to;
        }
    }
}
inline void write(){
    for(int i=1;i<=n;++i){
        if (colour[belong[(i<<1)-1]]==1) printf("%.2d:%.2d %.2d:%.2d\n",l[(i<<1)-1]/60,l[(i<<1)-1]%60,r[(i<<1)-1]/60,r[(i<<1)-1]%60);
        else printf("%.2d:%.2d %.2d:%.2d\n",l[i<<1]/60,l[i<<1]%60,r[i<<1]/60,r[i<<1]%60);
    }
}
int main(){
    init();
    build();
    for(int i=1;i<=2*n;++i) if (!dfn[i]) tarjan(i);
    for(int i=1;i<=n;++i)
        if (belong[i*2-1]==belong[i*2]) {puts("NO");return 0;}
    puts("YES");
    rebuild();
    topsort();
    write();
    return 0;
}