6443: BZOJ2443:[Usaco2011 Open]奇数度数

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description


奶牛们遭到了进攻!在他们的共和国里,有N(1 <= N <=50,000)个城市,由M
(1 <= M <= 100,000)条无向的道路连接城市A_i和B_i(1 <= A_i <= N;
1 <= B_i <= N;A_i != B_i; 不会有重复的道路出现)。然而,整个共和国不一定是
连通的——有一些城市无法到达另外一些城市。

入侵者想得到共和国的地图。(入侵者很傻,因此,他们的绘制地图的方法是去访问
每一条边,T_T)。奶牛想要折磨一下入侵者,使得他们尽可能难地完成地图绘制。因此,
奶牛会破坏若干条道路。

请你帮助奶牛找到一个道路的子集,使得每条边每个点的度数为奇数。或者输出不存在这
样的一个子集。(奶牛的图论学得真好.= =||)

举个例子,考虑下面的共和国:

1---2
\ /
  3---4

如果我们保留道路1-3,2-3和3-4,破坏道路1-2,那么城市1,2,4都只有一条边相连,城市3有
3条边相连:

1   2
\ /
  3---4


输入格式


* 第一行:两个用空格隔开的整数:N和M

* 第二行到M+1行:第i+1行有两个空格隔开的整数A_i和


输出格式


* 第一行: 一个整数表示需要保留的道路数量

* 第二到K+1行:每行一个数表示保留的道路的编号,范围是1...M。


样例输入

4 4
1 2
2 3
3 1
3 4


样例输出

3
2
3
4

提示

本题需SJ请不要提交!


题目来源

Gold

加入题单

上一题 下一题 算法标签: