#1016. 简单环
简单环
题目描述
给出一个无向图,由 n 个顶点(编号 1 到 n)和 m 条边(编号 1 到 m)组成。
图不一定是连通的。但保证图不包含重边和自环。
图中的一个环被称为简单环,当且仅当环中的每个顶点恰好只包含一次。因此遍历一个简单环上的点,必然不会经过同一顶点 2 次。
求所有仅可以被包含于一个简单环中的边。
输入格式
第一行输入两个整数n,m(1≤n≤100000,0≤m≤min(n(n-1)/2,100000)) 之后m行,每行输入两个数u,v,依次表示第1~m条边的两个端点。
输出格式
第一行输出一个整数,表示满足题意的边的数量; 若边的数量不为0,则第二行按增序依次输出满足题意的边的编号,以空格隔开。
输入样例
7 9
1 2
2 3
2 4
2 5
3 4
4 5
5 6
1 7
2 7
输出样例
3
1 8 9
样例解释
样例中的情形如图所示,1-2、1-7、2-7三条边仅属于一个简单环1-2-7;
5-6不属于任何简单环;
其它边都可包含于多个简单环中。
数据范围
对于35%的数据,n,m≤10;
对于50%的数据,n,m≤500;
对于100%的数据,1≤n≤10^5^,0≤m≤min(2n(n−1),10^5),1≤u,v≤n,u≠v。
Statistics
Related
In following contests: