Description：

给定一张无向图，要求删掉一条边，使得图变成二分图，问所有的删法。

$n,m\le10000$

Solution：

先随便求出来图的一棵生成树，对这棵树进行二分图染色。

考虑所有非树边，如果加上后都没有矛盾，即都是偶环，那么所有边都可以。

考虑有一条边产生了矛盾，则可以删掉它构成的奇环上的任意一条边。最后的结果一定是被所有矛盾边覆盖，不被任何非矛盾边覆盖的边，于是分别打两个标记判断最后的标记个数是否是一个 $tot$ 一个 $0$ 即可，注意如果有多个矛盾边，则最后删掉的边一定不在矛盾边中，但如果只有一个，那么这个边也可能删掉。还要注意如果没有矛盾可以任意删掉一条边。如果一个边既被矛盾边覆盖也被非矛盾边覆盖，那么他也不能选因为这两个环套在一起一定还可以形成一个不包含这条边的奇环，而删掉这条边不能去掉这个大奇环。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10010

#define MAXM 10010

struct segment

{

	int u,v;

	bool add;

	segment(){add = false;}

}l[MAXM];

struct node

{

	int c[2],fa,v1,tag1,v2,tag2,cnt,siz;

	bool rev;

	node(){c[0] = c[1] = fa = v1 = tag1 = v2 = tag2 = cnt = 0;}

}t[MAXN + MAXM];

void maintain(int rt)

{

	t[rt].siz = t[rt].cnt;

	if(t[rt].c[0] != 0)t[rt].siz += t[t[rt].c[0]].siz;

	if(t[rt].c[1] != 0)t[rt].siz += t[t[rt].c[1]].siz;

	return;

}

void pushdown(int rt)

{

	if(t[rt].rev)

	{

		t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

		swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	}

	if(t[rt].tag1 != 0)

	{

		t[t[rt].c[0]].v1 += t[rt].tag1;t[t[rt].c[1]].v1 += t[rt].tag1;

		t[t[rt].c[0]].tag1 += t[rt].tag1;t[t[rt].c[1]].tag1 += t[rt].tag1;

		t[rt].tag1 = 0;

	}

	if(t[rt].tag2 != 0)

	{

		t[t[rt].c[0]].v2 += t[rt].tag2;t[t[rt].c[1]].v2 += t[rt].tag2;

		t[t[rt].c[0]].tag2 += t[rt].tag2;t[t[rt].c[1]].tag2 += t[rt].tag2;

		t[rt].tag2 = 0;

	}

	return;

}

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

stack<int> s;

void splay(int k)

{

	s.push(k);

	for(int i = k;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(k))

	{

		int y = t[k].fa;

		if(isroot(y)){rotate(k);return;}

		if(id(k) == id(y)){rotate(y);rotate(k);}

		else{rotate(k);rotate(k);}

	}

	return;

}

void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

int findroot(int k){access(k);splay(k);while(t[k].c[0] != 0)k = t[k].c[0];return k;}

void link(int x,int y){makeroot(x);makeroot(y);t[x].fa = y;return;} 

int res[MAXN],tot = 0;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&l[i].u,&l[i].v);

	}

	for(int i = 1;i <= n;++i)

	{

		t[i].cnt = 1;

	}

	for(int i = 1;i <= m;++i)

	{

		if(findroot(l[i].u) != findroot(l[i].v))

		{

			link(l[i].u,n + i);

			link(l[i].v,n + i);

			l[i].add = true;

		}

	}

	int ptr;

	for(int i = 1;i <= m;++i)

	{

		if(l[i].add)continue;

		makeroot(l[i].u);access(l[i].v);splay(l[i].v);

		if((t[l[i].v].siz % 2) == 1)

		{

			ptr = i;

			t[l[i].v].tag1 += 1;

			t[l[i].v].v1 += 1;

			++tot;

		}

		else

		{

			t[l[i].v].tag2 += 1;

			t[l[i].v].v2 += 1;

		}

	}

	if(tot == 0)

	{

		printf("%d\n",m);

		for(int i = 1;i <= m;++i)

		{

			printf("%d ",i);

		}

		puts("");

		return 0;

	}

	int cnt = 0;

	for(int i = 1;i <= m;++i)

	{

		splay(i + n);

		if(t[i + n].v1 == tot && t[i + n].v2 == 0)

		{

			res[++cnt] = i;

		}

	}

	if(tot == 1)

	{

		res[++cnt] = ptr;

	}

	cout << cnt << endl;

	for(int i = 1;i <= cnt;++i)

	{

		printf("%d ",res[i]);

	}

	return 0;

}