奇度
时间限制: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
- 通过率
- ?
- 上传者