406898: GYM102606 E Even Degree

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

Description

E. Even Degreetime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

As a expert in graph visualization, Cuber QQ has implemented a graph editing tool that supports adding/deleting nodes, adding/deleting edges and instant graph layout. The following image is a demo of the tool he has built.

These days, he noticed that there was a bug in his system. He cannot delete an edge $$$(u, v)$$$ when both of $$$u$$$ and $$$v$$$ are odd-degree nodes, i.e., he can only delete the edge when at least one of $$$(u, v)$$$ is connected to $$$k$$$ edges, where $$$k$$$ is any even number.

Now, instead of fixing this bug, Cuber QQ wants to play a little game. He tries to delete as many edges as possible, without using extra operations like adding edges or adding nodes or deleting nodes. He thinks such challenge is a piece of cake to him, so he wants to test you and see if you can solve this problem.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5\cdot 10^5$$$, $$$0\le m\le 5\cdot 10^5$$$) — the number of vertices and edges in the graph.

The $$$i$$$-th of the next $$$m$$$ lines contains two space-separated integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i \le n$$$) — the $$$i$$$-th edges in the graph.

It is guaranteed that the vertices in the initial graph all have even degrees, and there are no self-loops or multiple edges in the given graph.

Output

In the first line, output a single integer $$$k$$$ — how many edges at most you can delete.

In the second line, output $$$k$$$ distinct integers $$$e_1,e_2,\ldots,e_k$$$ ($$$1 \le e_i \le m$$$) in order of deletion, where $$$e_i$$$ is the index of $$$i$$$-th edge to delete.

If there are multiple answers, print any of them.

ExampleInput
3 3
1 2
1 3
2 3
Output
2
1 3 

加入题单

上一题 下一题 算法标签: