小明在学校的编程课上了解到了关于二分图的相关知识,所谓的二分图是一种特殊的图,图中的所有顶点可以分为两个不相交的集合,而图中的所有边的两个顶点都分属于这两个集合。
换句话来说,二分图是可以进行黑白染色的图,即给图中所有顶点都涂上黑色或者白色,使得每条边的两个端点都异色。
现在小明想知道,对于任意的一个n个顶点m条边的无向图,通过删去一条边使其变为二分图的方案数是多少?
输入输出格式
输入格式:
第一行输入两个数n、m,表示图的顶点数和边数
接下来m行,每行两个数x、y,表示一条边(编号1~m)
输出格式:
第一行输出一个数k,表示答案方案数
第二行输出k个数,表示k条边的编号,升序排列
输入输出样例
输入样例:
4 4
1 2
1 3
2 4
3 4
输出样例:
4
1 2 3 4
样例说明:
有4种删除方案,删除{1, 2, 3, 4}号边中的任意一个都可以使图变为二分图。
测试点
一共10个测试点,每个测试点10分
每个测试点时间限制为1s,空间限制为128MB
测试点:
测试点1~10:1≤n≤105,1≤m≤106