大哥绝招——千里追魂剑!
题目描述
给定一张有 n 个点、m 条边的图,其中有些边已经定向。请给其余的边定向,使整张图强连通。图中可能有重边和自环。
输入格式
第一行两个整数 n,m。
接下来 m 行,每行三个整数 xi,yi,ci。若 ci=0,需要给连接 xi 和 yi 的边定向。若 ci=1,该边已经从 xi 指向 yi。
输出格式
若无解,输出一行 NO。
否则,第一行输出 YES。接下来按输入顺序输出 m 行,第 i 行两个整数 ai,bi,表示第 i 条边从 ai 指向 bi。必须满足 {ai,bi}={xi,yi}。若 ci=1,必须有 ai=xi 且 bi=yi。
样例
3 3
1 2 0
2 3 0
1 3 1
YES
2 1
3 2
1 3
原赛样例 2、3 另见比赛下发文件。
数据范围
1≤n≤106,0≤m≤2×106,1≤xi,yi≤n,ci∈{0,1}。
以下是原赛子任务设置。
| 子任务 |
n 上限 |
m 上限 |
特殊性质 |
原赛分值 |
| 1 |
20 |
无 |
20 |
| 2 |
100 |
200 |
保证有解 |
5 |
| 3 |
300 |
600 |
| 4 |
2000 |
4000 |
10 |
| 5 |
无 |
20 |
| 6 |
106 |
2×106 |
所有 ci=0 |
| 7 |
无 |
本题输入输出量较大。原赛下发的 checker.cpp 可与 testlib.h 一起编译,通过同一份输出同时作为选手和标准输出,检查已有定向方案。这样运行时无法判断首行 YES 或 NO 是否正确。
原 PDF 题面