{"problem":{"name":"E. Even Degree","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10260E"},"statements":[{"statement_type":"Markdown","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## Input\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.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.\n\n## Output\n\nIn 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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10260E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}