小明在学校的编程课上了解到了关于二分图的相关知识,所谓的二分图是一种特殊的图,图中的所有顶点可以分为两个不相交的集合,而图中的所有边的两个顶点都分属于这两个集合。
换句话来说,二分图是可以进行黑白染色的图,即给图中所有顶点都涂上黑色或者白色,使得每条边的两个端点都异色。
现在小明想知道,对于任意的一个 n 个顶点 m 条边的无向图,通过删去一条边使其变为二分图的方案数是多少?
第一行输入两个数 n、m,表示图的顶点数和边数。
接下来 m 行,每行两个数 x、y,表示一条边(编号 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
如图,删去两条黑色边的任意一条(边编号为 11、12),均可使图成为二分图。
