#P11877. [2023年联测]定向

    ID: 11028 传统题 2000ms 888MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-深度优先搜索low-link图构造

[2023年联测]定向

大哥绝招——千里追魂剑!

题目描述

给定一张有 nn 个点、mm 条边的图,其中有些边已经定向。请给其余的边定向,使整张图强连通。图中可能有重边和自环。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,每行三个整数 xi,yi,cix_i,y_i,c_i。若 ci=0c_i=0,需要给连接 xix_i 和 yiy_i 的边定向。若 ci=1c_i=1,该边已经从 xix_i 指向 yiy_i。

输出格式

若无解,输出一行 NO。

否则,第一行输出 YES。接下来按输入顺序输出 mm 行,第 ii 行两个整数 ai,bia_i,b_i,表示第 ii 条边从 aia_i 指向 bib_i。必须满足 {ai,bi}={xi,yi}\{a_i,b_i\}=\{x_i,y_i\}。若 ci=1c_i=1,必须有 ai=xia_i=x_i 且 bi=yib_i=y_i。

样例

3 3
1 2 0
2 3 0
1 3 1
YES
2 1
3 2
1 3

原赛样例 2、3 另见比赛下发文件。

数据范围

1≤n≤1061\le n\le10^6,0≤m≤2×1060\le m\le2\times10^6,1≤xi,yi≤n1\le x_i,y_i\le n,ci∈{0,1}c_i\in\{0,1\}。

以下是原赛子任务设置。

子任务 nn 上限 mm 上限 特殊性质 原赛分值
1 2020 无 20
2 100100 200200 保证有解 5
3 300300 600600
4 20002000 40004000 10
5 无 20
6 10610^6 2×1062\times10^6 所有 ci=0c_i=0
7 无

本题输入输出量较大。原赛下发的 checker.cpp 可与 testlib.h 一起编译,通过同一份输出同时作为选手和标准输出,检查已有定向方案。这样运行时无法判断首行 YES 或 NO 是否正确。

原 PDF 题面