{"raw_statement":[{"iden":"statement","content":"A ski base is planned to be built in Walrusland. Recently, however, the project is still in the constructing phase. A large land lot was chosen for the construction. It contains _n_ ski junctions, numbered from 1 to _n_. Initially the junctions aren't connected in any way.\n\nIn the constructing process _m_ bidirectional ski roads will be built. The roads are built one after another: first the road number 1 will be built, then the road number 2, and so on. The _i_\\-th road connects the junctions with numbers _a__i_ and _b__i_.\n\nTrack is the route with the following properties:\n\n* The route is closed, that is, it begins and ends in one and the same junction.\n* The route contains at least one road.\n* The route doesn't go on one road more than once, however it can visit any junction any number of times.\n\nLet's consider the ski base as a non-empty set of roads that can be divided into one or more tracks so that exactly one track went along each road of the chosen set. Besides, each track can consist only of roads from the chosen set. Ski base doesn't have to be connected.\n\nTwo ski bases are considered different if they consist of different road sets.\n\nAfter building each new road the Walrusland government wants to know the number of variants of choosing a ski base based on some subset of the already built roads. The government asks you to help them solve the given problem."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 105, 1 ≤ _m_ ≤ 105). They represent the number of junctions and the number of roads correspondingly. Then on _m_ lines follows the description of the roads in the order in which they were built. Each road is described by a pair of integers _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_) — the numbers of the connected junctions. There could be more than one road between a pair of junctions."},{"iden":"output","content":"Print _m_ lines: the _i_\\-th line should represent the number of ways to build a ski base after the end of construction of the road number _i_. The numbers should be printed modulo 1000000009 (109 + 9)."},{"iden":"examples","content":"Input\n\n3 4\n1 3\n2 3\n1 2\n1 2\n\nOutput\n\n0\n0\n1\n3"},{"iden":"note","content":"Let us have 3 junctions and 4 roads between the junctions have already been built (as after building all the roads in the sample): 1 and 3, 2 and 3, 2 roads between junctions 1 and 2. The land lot for the construction will look like this:\n\nThe land lot for the construction will look in the following way:\n\nWe can choose a subset of roads in three ways:\n\nIn the first and the second ways you can choose one path, for example, 1 - 2 - 3 - 1. In the first case you can choose one path 1 - 2 - 1."}],"translated_statement":[{"iden":"statement","content":"在海狸国计划建造一个滑雪基地。然而，目前该项目仍处于建设阶段。已选定一块大面积土地用于建设，该土地包含 #cf_span[n] 个滑雪交汇点，编号从 #cf_span[1] 到 #cf_span[n]。初始时，这些交汇点之间没有任何连接。\n\n在建设过程中，将依次修建 #cf_span[m] 条双向滑雪道路。道路按顺序修建：先修建第 #cf_span[1] 条道路，然后是第 #cf_span[2] 条，依此类推。第 #cf_span[i] 条道路连接编号为 #cf_span[ai] 和 #cf_span[bi] 的两个交汇点。\n\n#cf_span(class=[tex-font-style-underline], body=[Track]) 是满足以下性质的路线：\n\n将 #cf_span(class=[tex-font-style-underline], body=[滑雪基地]) 定义为一个非空的道路集合，该集合可以被划分为一个或多个 track，使得集合中的每条道路恰好属于一个 track，并且每个 track 仅由集合中的道路组成。滑雪基地不必连通。\n\n两个滑雪基地被认为是不同的，当且仅当它们由不同的道路集合构成。\n\n在每修建一条新道路后，海狸国政府希望知道：基于已修建道路的某个子集，有多少种方式可以构建一个滑雪基地。请你帮助政府解决该问题。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 105, 1 ≤ m ≤ 105]），分别表示交汇点数量和道路数量。接下来 #cf_span[m] 行，按修建顺序描述每条道路。每条道路由一对整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n, ai ≠ bi]）描述，表示连接的两个交汇点。同一对交汇点之间可能存在多条道路。\n\n请输出 #cf_span[m] 行：第 #cf_span[i] 行表示在修建完第 #cf_span[i] 条道路后，构建滑雪基地的方案数。答案需对 #cf_span[1000000009]（#cf_span[109 + 9]）取模。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 105, 1 ≤ m ≤ 105]），分别表示交汇点数量和道路数量。接下来 #cf_span[m] 行，按修建顺序描述每条道路。每条道路由一对整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n, ai ≠ bi]）描述，表示连接的两个交汇点。同一对交汇点之间可能存在多条道路。"},{"iden":"output","content":"请输出 #cf_span[m] 行：第 #cf_span[i] 行表示在修建完第 #cf_span[i] 条道路后，构建滑雪基地的方案数。答案需对 #cf_span[1000000009]（#cf_span[109 + 9]）取模。"},{"iden":"examples","content":"输入\n3 4\n1 3\n2 3\n1 2\n1 2\n输出\n0\n0\n1\n3"},{"iden":"note","content":"假设共有 3 个交汇点，且已修建了 4 条道路（如样例中最终状态）：连接 1 和 3、2 和 3，以及两条连接 1 和 2 的道路。该土地的布局如下：\n\n该土地的布局如下：\n\n我们可以以三种方式选择道路子集：\n\n在第一种和第二种方式中，可以选择一条路径，例如 1 - 2 - 3 - 1。在第一种情况下，可以选择一条路径 1 - 2 - 1。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ G = (V, E) $ be an undirected multigraph with $ n $ vertices and $ m $ edges, where edges are added sequentially. Let $ E_i \\subseteq E $ denote the set of the first $ i $ edges added.\n\nA **ski base** is a subset $ S \\subseteq E_i $ such that the subgraph $ (V, S) $ can be partitioned into one or more **edge-disjoint cycles** (i.e., each edge in $ S $ belongs to exactly one cycle, and cycles may share vertices but not edges). Equivalently, $ S $ must induce a subgraph where every connected component is Eulerian (all vertex degrees are even) and non-empty.\n\nLet $ f(i) $ denote the number of non-empty ski bases after adding the $ i $-th edge, modulo $ 10^9 + 9 $.\n\nWe model the problem using linear algebra over $ \\mathbb{F}_2 $:\n\n- Let $ \\mathcal{C} $ be the cycle space of the graph $ G_i = (V, E_i) $, which is a vector space over $ \\mathbb{F}_2 $.\n- The dimension of $ \\mathcal{C} $ is $ \\dim(\\mathcal{C}) = |E_i| - |V| + c_i $, where $ c_i $ is the number of connected components in $ G_i $.\n- Each element of $ \\mathcal{C} $ corresponds to a subset of edges forming an Eulerian subgraph (possibly empty).\n- The number of non-empty Eulerian subgraphs is $ 2^{\\dim(\\mathcal{C})} - 1 $.\n\nThus, after adding the $ i $-th edge:\n\n$$\nf(i) = 2^{|E_i| - n + c_i} - 1 \\pmod{10^9 + 9}\n$$\n\nWe maintain:\n\n- $ c_i $: number of connected components (using Union-Find),\n- $ \\text{rank}_i = |E_i| - n + c_i $: dimension of the cycle space.\n\nInitialize: $ c_0 = n $, $ \\text{rank}_0 = 0 $, $ f(0) = 0 $.\n\nFor each edge $ e_i = (a_i, b_i) $ added:\n\n- If $ a_i $ and $ b_i $ are in different components: union them → $ c_i = c_{i-1} - 1 $, $ \\text{rank}_i = \\text{rank}_{i-1} + 1 $\n- If $ a_i $ and $ b_i $ are in the same component: cycle formed → $ c_i = c_{i-1} $, $ \\text{rank}_i = \\text{rank}_{i-1} + 1 $\n\nThen:\n\n$$\nf(i) = (2^{\\text{rank}_i} - 1) \\mod (10^9 + 9)\n$$\n\n**Output:** $ f(1), f(2), \\dots, f(m) $\n\n---\n\n**Formal Statement:**\n\nLet $ G_i = (V, E_i) $, where $ V = \\{1, 2, \\dots, n\\} $, and $ E_i = \\{e_1, e_2, \\dots, e_i\\} $, with $ e_j = (a_j, b_j) $.\n\nLet $ c_i $ be the number of connected components of $ G_i $.\n\nDefine the cycle space dimension: \n$$\nr_i = |E_i| - n + c_i\n$$\n\nThen the number of non-empty ski bases after $ i $ edges is: \n$$\nf(i) = 2^{r_i} - 1 \\pmod{10^9 + 9}\n$$\n\nCompute $ f(i) $ for $ i = 1 $ to $ m $, updating $ c_i $ via Union-Find and $ r_i $ incrementally.","simple_statement":null,"has_page_source":false}