友情提示:380元/半年,儿童学编程,就上码丁实验室。
【题目描述】
有一个情报网共有$n$个人,通过有向的电话线联络。为保证通信安全,需要满足一些要求,这些要求分为两类:
①从第$a$个人通过一条或多条电话线可以联系到第$b$个人;
②从第$a$个人通过一条或多条电话线不能联系到第$b$个人。
现在作为总工程师的你需要构造一个合法的情报网,使得这个情报网满足给定要求,或者告诉情报机构这样的情报网是不存在的。
【输入】
第一行一个整数$n$表示人数。
第二行一个整数$m$表示第一类要求的个数,接下来$m$行每行两个整数$a,b$表示要求。
第$m+3$行一个整数$t$表示第二类要求的个数,接下来$t$行每行两个整数$a,b$表示要求。
【输出】
若不存在这样的情报网,输出一行“$NO$”(不含引号)。
否则在第一行输出“$YES$”(不含引号),在第二行输出情报网中电话线的数量$P$,接下来$P$行每行两个整数$u,v$,描述一条$u→v$的电话线。由于资源有限,要求$P≤n+m+t$。
【输入样例】
3 2 1 2 2 3 1 1 3
【输出样例】
NO
【提示】
【输入样例2】
3 2 1 2 2 3 1 3 1
【输出样例2】
YES 2 1 2 2 3
【数据规模】
对于20%的数据,$n≤1000$;
对于60%的数据,$n≤25000$;
对于100%的数据,$1≤n,m,t≤10^5,1≤a,b≤n,a≠b$。