30097 - 二分图

通过次数

1

提交次数

1

时间限制 : 1 秒
内存限制 : 128 MB

小明在学校的编程课上了解到了关于二分图的相关知识,所谓的二分图是一种特殊的图,图中的所有顶点可以分为两个不相交的集合,而图中的所有边的两个顶点都分属于这两个集合。

换句话来说,二分图是可以进行黑白染色的图,即给图中所有顶点都涂上黑色或者白色,使得每条边的两个端点都异色。

现在小明想知道,对于任意的一个 n 个顶点 m 条边的无向图,通过删去一条边使其变为二分图的方案数是多少?

输入

第一行输入两个数 nm,表示图的顶点数和边数。

接下来 m 行,每行两个数 xy,表示一条边(编号 1 \sim m)。

输出

第一行输出一个数 k,表示答案方案数。

第二行输出 k 个数,表示 k 条边的编号,升序排列。

样例

输入

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

输出

2
11 12

提示

样例说明

如图,删去两条黑色边的任意一条(边编号为 1112),均可使图成为二分图。

数据范围

  • 1 \le n \le 10^5
  • 1 \le m \le 10^6