题目描述

题目译自 European Girls' Olympiad in Informatics 2023 Day2 T3. Sopsug

在隆德郊外的格鲁肖格（Grushög），一个尚未完工的住宅区正在建设中。目前，所有必要的基础设施都在铺设，其中最重要的一项是垃圾处理系统。与瑞典许多地区一样，这里将采用垃圾吸运系统（sopsug，一种自动真空收集系统），通过地下管道利用气压运输垃圾。

格鲁肖格有 $N$ 栋楼，编号从 $0$ 到 $N-1$。你的任务是为某些楼对建造管道。如果你在楼 $u$ 和楼 $v$ 之间建造了一条管道，$u$ 的所有垃圾将送往 $v$（但反方向不行）。你的目标是建造一个包含 $N-1$ 条管道的网络，确保所有垃圾最终汇集到一栋楼。换句话说，网络需要形成一棵有根树，管道方向指向根节点。

然而，已经有 $M$ 条管道建好，这些管道必须包含在你的网络中。这些管道是有方向的，只能按指定方向使用。

此外，有 $K$ 对楼之间无法建造管道。这些楼对是有序的，因此如果从 $u$ 到 $v$ 无法建管道，从 $v$ 到 $u$ 可能仍然可行。

输入格式

第一行包含三个整数 $N, M, K$。

接下来的 $M$ 行，每行包含两个不同的整数 $a_i, b_i$，表示已有一条从 $a_i$ 到 $b_i$ 的管道。

接下来的 $K$ 行，每行包含两个不同的整数 $c_i, d_i$，表示从 $c_i$ 到 $d_i$ 无法建造管道。

输入中的 $M+K$ 个有序对均不相同。注意，$(u, v)$ 和 $(v, u)$ 被视为不同的对。

输出格式

如果无法构建满足条件的网络，输出 NO。

否则，输出 $N-1$ 行，每行包含两个整数 $u_i, v_i$，表示从 $u_i$ 到 $v_i$ 有一条管道。你可以按任意顺序输出管道。如果存在多个解，你可以输出任意一个。记住，$M$ 条已有管道必须包含在你的解决方案中。

5 1 8
4 1
3 1
3 4
3 2
0 2
0 4
2 4
1 0
2 0

4 1
3 0
1 3
2 3

5 4 0
1 0
2 3
3 4
4 2

NO

以下图示展示了样例 1 和样例 2。蓝色边表示已建好的管道，红色虚线边表示无法建造的管道。

左侧图示显示了样例输出中的解决方案，除已建好的从 $4$ 到 $1$ 的管道（蓝色）外，新增了黑色边的管道。在此网络中，所有垃圾最终汇集到楼 $0$。这不是唯一解，例如，可以将从 $1$ 到 $3$ 的管道替换为从 $0$ 到 $1$ 的管道，仍然有效。

右侧图示显示由于存在循环 $(2, 3, 4)$，无法构建满足条件的网络。

3 0 1
0 1

1 0
2 0

4 0 2
0 1
1 0

2 0
3 0
1 3

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 300000$
• $0 \leq M \leq 300000$
• $0 \leq K \leq 300000$
• $0 \leq a_i, b_i \leq N-1$（对于 $i = 0, 1, \ldots, M-1$）
• $0 \leq c_i, d_i \leq N-1$（对于 $i = 0, 1, \ldots, K-1$）

详细子任务附加限制及分值如下表所示。