{"raw_statement":[{"iden":"statement","content":"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.\n\nThese 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.\n\nNow, 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.\n\nThe first line contains two integers $n$ and $m$ ($1 <= n <= 5 dot.op 10^5$, $0 <= m <= 5 dot.op 10^5$) — the number of vertices and edges in the graph.\n\nThe $i$-th of the next $m$ lines contains two space-separated integers $u_i$ and $v_i$ ($1 <= u_i, v_i <= n$) — the $i$-th edges in the graph.\n\nIt 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.\n\nIn the first line, output a single integer $k$ — how many edges at most you can delete.\n\nIn the second line, output $k$ distinct integers $e_1, e_2, \\\\dots, e_k$ ($1 <= e_i <= m$) in order of deletion, where $e_i$ is the index of $i$-th edge to delete.\n\nIf there are multiple answers, print any of them.\n\n"},{"iden":"input","content":"The first line contains two integers $n$ and $m$ ($1 <= n <= 5 dot.op 10^5$, $0 <= m <= 5 dot.op 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 <= u_i, v_i <= 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."},{"iden":"output","content":"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, \\\\dots, e_k$ ($1 <= e_i <= 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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $.  \nLet $ d(v) $ denote the degree of vertex $ v \\in V $.  \nLet $ E = \\{e_1, e_2, \\dots, e_m\\} $, where $ e_i = (u_i, v_i) $, indexed from 1 to $ m $.  \n\n**Constraints**  \n1. Initially, $ d(v) $ is even for all $ v \\in V $.  \n2. No self-loops or multiple edges.  \n3. An edge $ e_i = (u, v) $ can be deleted **only if** at least one of $ u $ or $ v $ has even degree **at the time of deletion**.  \n4. Only edge deletions are allowed; no additions or node deletions.  \n\n**Objective**  \nMaximize the number of deletable edges.  \nOutput the maximum number $ k $ of edges that can be deleted, and a sequence of edge indices $ e_{i_1}, e_{i_2}, \\dots, e_{i_k} $ (in deletion order) such that each deletion is valid under the constraint.","simple_statement":"You are given a graph with n nodes and m edges, where every node has even degree.  \nYou can delete an edge only if at least one of its two endpoints has even degree.  \nYou cannot add or remove nodes or edges otherwise.  \nFind the maximum number of edges you can delete, and output the order of deletion.","has_page_source":false}