← 返回题目列表

Codeforces · 19/E

E. 仙女

中文机器翻译题面 查看原题

从前,有一位善良的仙女A。有一天,一位优秀的年轻人B来到她面前,要求预测他的未来。仙女看着她的魔法球,说很快这个优秀的年轻人就会遇到有史以来最美丽的公主,并会娶她。然后她在一张纸上画了n个点,并用线段将其中一些点连接起来,每个线段从某个点开始,到另一个点结束。画完那幅画后,她要求年轻人从纸上擦掉其中的一个片段。然后,她尝试将每个点着色为红色或蓝色,以便不存在与其末端具有相同颜色的点的线段。如果她成功的话,预言就会成真。 B想要见到最美丽的公主,所以他请你帮助他。找到所有能帮助他见到公主的片段。

输入

第一输入行包含两个整数:n — 绘制点的数量和 m — 绘制线段的数量 (1 ≤ n ≤ 104, 0 ≤ m ≤ 104)。接下来的 m 行包含了段的描述。每个描述包含两个不同的空格分隔整数 v, u (1 ≤ v ≤ n, 1 ≤ u ≤ n) — 点的索引,由该段连接。描述中没有段出现两次。

输出

在第一行输出数字 k — 答案中的段数。在第二行中输出 k 个空格分隔的数字 - 这些段的索引按升序排列。每个索引只能输出一次。段按照输入顺序从 1 开始编号。

示例

输入 #1

4 4
1 2
1 3
2 4
3 4

输出 #1

4
1 2 3 4

输入 #2

4 5
1 2
2 3
3 4
4 1
1 3

输出 #2

1
5