最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 情报传递

C++ 少儿编程 1155浏览 0评论

友情提示: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$。

您必须 登录 才能发表评论!