题目背景

我也不知道为什么是 0-index。

题目描述

给定一个 $N$ 个点的有向图，标号依次为 $0,1,\cdots n-1$。对于任意 $u\neq v$，均有一条 $u$ 指向 $v$ 的边。

现分别给定大小为 $M$ 的边集 $S_1$ 和大小为 $K$ 的边集 $S_2$（保证 $S_1\cap S_2 =\empty$），构造该有向图一个大小为 $N-1$ 的边集 $S$（或者判断无解），使得：

• $S_1\sube S$
• $S_2\cap S =\empty$
• 存在一个点 $x$，使得对于任意点 $y\neq x$，均可通过 $S$ 中的边到达 $x$。

输入格式

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

接下来 $M$ 行，每行两个不相等的整数 $a_i,b_i$，表示 $S_1$ 中的一条 $a_i$ 指向 $b_i$ 的边。

接下来 $K$ 行，每行两个不相等的整数 $c_i,d_i$，表示 $S_2$ 中的一条 $c_i$ 指向 $d_i$ 的边。

输出格式

如果无解，输出一行 NO。

否则，输出 $N-1$ 行，每行两个整数 $u_i,v_i$，表示 $S$ 中的一条 $u_i$ 指向 $v_i$ 的边。

$S$ 中的每条边可以任意顺序输出，但应确保输出的 $N-1$ 条边互不相同，且在 $S_1$ 中的边仍需输出。如有多组解，可以输出任意一组。

样例输入 #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

样例解释 #2

根据上述条件，若仅保留 $S$ 中的边且均视为无向边，生成的新图应当连通，由于边数为 $N-1$，则新图不应有环。$S_1$ 中的边 $(2,3)(3,4)(4,2)$ 已经构成环，故无解。

样例输入 #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

数据范围

对于 $100\%$ 的数据，$2\le N\le 3\times 10^5$，$0\le M\le 3\times 10^5$，$0\le K\le 3\times 10^5$，$0\le a_i,b_i\le N-1$，$0\le c_i,d_i\le N-1$，$S_1\cap S_2=\empty$。

$subtask1$ $(12pts)$: $M=0$，$K=1$。

$subtask2$ $(10pts)$: $M=0$，$K=2$。

$subtask3$ $(19pts)$: $K=0$。

$subtask4$ $(13pts)$: $N\le 100$。

$subtask5$ $(17pts)$: 保证存在一个满足条件的集合 $S$ 使得对于任意点 $x\neq 0$，均可通过 $S$ 中的边到达 $0$。

$subtask6$ $(11pts)$: $M=0$。

$subtask7$ $(18pts)$: 无特殊限制。