奇度子图(Odd Degrees)

题目描述

奶牛共和国遭到了入侵！共和国由 $N$（$1 \le N \le 50000$）座城镇组成，城镇之间由 $M$（$1 \le M \le 100000$）条无向道路相连，第 $i$ 条道路连接城镇 $A_i$ 与 $B_i$（$1 \le A_i, B_i \le N$，$A_i \ne B_i$，保证无重边）。注意共和国不一定连通。

奶牛们得知入侵者计划清点共和国境内的每一条道路，因此打算关闭一部分道路来制造麻烦。请帮助奶牛们选出一个要保留的道路子集，使得每座城镇在保留下来的道路中都恰好连接奇数条道路，或者判定不存在满足条件的方案。

例如，考虑如下奶牛共和国：

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

如果保留道路 2-3、3-1 和 3-4（关闭 1-2），则城镇 $1, 2, 4$ 的度数均为 $1$，城镇 $3$ 的度数为 $3$，所有城镇的度数均为奇数。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个用空格分隔的整数 $A_i$ 和 $B_i$，按输入顺序编号为 $1 \sim M$。

输出格式

如果不存在合法方案，仅输出一行一个整数 -1。

否则第一行输出一个整数 $K$，表示保留的道路条数；接下来 $K$ 行每行输出一个 $1 \sim M$ 之间的整数，表示保留的道路编号（编号必须两两不同，若有多种合法方案输出任意一种即可）。

样例输入 #1

4 4 
1 2 
2 3 
3 1 
3 4 

样例输出 #1

3 
2 
3 
4 

数据范围

对于 $100\%$ 的数据，$1 \le N \le 50000$，$1 \le M \le 100000$，$1 \le A_i, B_i \le N$，$A_i \ne B_i$，无重边。本题使用 Special Judge 评测。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接