Grushög 是隆德郊区一个未完工的住宅区。目前，所有必要的基础设施都在建设中，包括最重要的设施：垃圾处理系统。和瑞典的许多地区一样，这里将使用一种 sopsug（自动真空收集系统）来收集垃圾。其构想是通过管道利用气压在地下运输垃圾。

Grushög 有 $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$ 条已有的管道必须包含在你的解中。

数据范围

• $2 \le N \le 300\,000$
• $0 \le M \le 300\,000$
• $0 \le K \le 300\,000$
• $0 \le a_i, b_i \le N - 1$，对于 $i = 0, 1, \dots, M - 1$
• $0 \le c_i, d_i \le N - 1$，对于 $i = 0, 1, \dots, K - 1$

子任务

样例

下图展示了第一和第二个样例测试用例。蓝色边标记了已经建造的管道，虚线红色边标记了无法建造的管道。

左图展示了第一个样例及其对应的样例输出解，图中显示了黑色边（以及蓝色的从 $4$ 到 $1$ 的已有管道）。在这个网络中，所有垃圾都将汇集到建筑 $0$。这并不是唯一的解；例如，从 $1$ 到 $3$ 的管道可以替换为从 $0$ 到 $1$ 的管道，这仍然是一个有效的解。

对于第二个样例输入，我们可以从右图中看到，由于存在环 $(2, 3, 4)$，因此无法构建出解。

样例输入 1

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

样例输出 1

4 1
3 0
1 3
2 3

样例输入 2

5 4 0
1 0
2 3
3 4
4 2

样例输出 2

NO

样例输入 3

3 0 1
0 1

样例输出 3

1 0
2 0

样例输入 4

4 0 2
0 1
1 0

样例输出 4

2 0
3 0
1 3