#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​

样例解释

image

样例中的情形如图所示,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​(2​n​(​n​−1),10​^5​),1≤​u​,​v​≤​n​,​u​≠​v​。