构造有向图

题目描述

你需要构造一个$n$个点的有向图，满足两类要求（第一类要求有$m$条，第二类要求有$t$条）：

1. 从点$a$通过一条或多条边可以到达点$b$；
2. 从点$a$通过一条或多条边不能到达点$b$；

同时，你需要保证构造的图的边数$p \leq 100000$。

输入格式

第一行一个整数$n$。

第二行一个整数$m$，表示第一类要求的个数，接下来$m$行每行两个整数$a$，$b$。

第$m+3$行一个整数$t$，表示第二类要求的个数，接下来$t$行每行两个整数$a$，$b$。

输出格式

若不存在这样的图，输出一行$NO$。

反之，第一行输出$YES$，第二行输出该图的边数$p$，接下来$p$行每行两个整数$u$，$v$，表示该图中有$u \to v$的一条有向边。

数据范围与提示

本题采用子任务捆绑测试。对于每个子任务，你只有通过了这个子任务的所有测试点，才能获得这个子任务的分数。

• 子任务$1$（$20$分）：$n$，$m$，$t \leq 100$；
• 子任务$2$（$40$分）：$n$，$m$，$t \leq 25000$；
• 子任务$3$（$40$分）：$n$，$m$，$t \leq 10^{5}$。

对于$100\%$的数据，$1 \leq n$，$m$，$t \leq 10^{5}$，$1 \leq a$，$b \leq n$，$a \neq b$。

样例

3
2
1 2
2 3
1
1 3

NO

3
2
1 2
2 3
1
3 1

YES
2
1 2
2 3