/ Vijos / 题库 /

网络的关键边

网络的关键边

描述

考虑一个连通的无向图,可以知道,任意两个节点都可以通过一条路径连接起来。在所有节点中,某些节点向所有与它连通的节点提供A服务(包括向它自己),同时某些节点向所有与它连通的节点提供B服务(也包括向它自己)。注意一个节点也可能同时提供A、B两种服务。

当图中的某条边E被去掉的时候,如果图中有任何一个点无法接受A服务或者接受B服务,我们称E边为关键边。

那么,你需要做的事情就是:
1、输出图中存在多少关键边;
2、从小到大输出所有这样的关键边的编号。

格式

输入格式

输入文件共M+3行。第1行输入4个整数N,M,K和L。N表示图中的节点个数,M是图中边的数目,K是提供A服务的点的个数,L是提供B服务的点的个数。第2行输入K个数,分别表示哪些点提供A服务。第3行输入L个数,分别表示哪些点提供B服务。接下来M行每行输入两个数p,q表示节点p和节点q之间有一条无向边。节点从1至N编号,边按从读入顺序从1至M编号。

输出格式

输出文件第1行输出一个数S,表示该网络中存在S条关键边,接下来输出S行,每行输出一条关键边编号。请按编号从小到大(读入顺序编号)输出。

样例1

样例输入1

9 10 3 4
2 4 5
4 9 8 3
1 2
4 1
2 3
4 2
1 5
5 6
6 7
6 8
7 9
8 7

样例输出1

3
3
6
9

限制

每个测试点2s。

提示

对于15%的数据,n<=30,m<=30,k<=5,l<=5;
对于35%的数据,n<=400,m<=400,k<=30,l<=30;
对于50%的数据,n<=3000,m<=3500,k<=100,k<=100。

对于100%的数据,n<=100000,m<=100000,k<=10000,l<=10000。

保证没有重边和自环。

信息

ID
1769
难度
5
分类
图结构 点击显示
标签
(无)
递交数
103
已通过
38
通过率
37%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

NOIP2012模拟赛第四弹