/ Vijos / 题库 /

奇度

奇度

时间限制:1秒  内存限制:256M


【问题描述】

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

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

  请你帮助奶牛找到一个道路的子集,使得每条边每个点的度数为奇数。或者输出不存在这样的一个子集。

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

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

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

1   2
 \ /
  3---4

【输入格式】

  第 \(1\) 行:一两个用空格隔开的整数:\(N\) 和 \(M\)。
  第 \(2..M+1\) 行:第 \(i+1\) 行包含两个空格隔开的整数:\(A_i\) 和 \(B_i\)。

【输出格式】

  第一行: 一个整数表示需要保留的道路数量
  第二到 \(K+1\) 行:每行一个数表示保留的道路的编号,范围是 \(1..M\)。

【输入输出样例1】

 Input

4 4
1 2
2 3
3 1
3 4

 Output

3
2
3
4

【数据说明】

  对于 \(100\%\) 的数据,\(1 ≤ N ≤ 50000\),\(1 ≤ M ≤ 50000\)

【来源】

  Mr.he

信息

ID
1457
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者