{"problem":{"name":"C. Ski Base","description":{"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, num","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF91C"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint _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).\n\n[samples]\n\n## Note\n\nLet 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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]）取模。\n\n## Input\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## Output\n\n请输出 #cf_span[m] 行：第 #cf_span[i] 行表示在修建完第 #cf_span[i] 条道路后，构建滑雪基地的方案数。答案需对 #cf_span[1000000009]（即 #cf_span[109 + 9]）取模。\n\n[samples]\n\n## Note\n\n假设有 3 个交汇点，并且已修建了 4 条道路（如样例中最终状态）：1 和 3 之间、2 和 3 之间，以及两条连接 1 和 2 的道路。该土地的布局如下：\n\n该土地的布局如下：\n\n我们可以以三种方式选择道路子集：\n\n在第一种和第二种方式中，你可以选择一条路径，例如 1 - 2 - 3 - 1。在第一种情况下，你可以选择一条路径 1 - 2 - 1。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"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) $ admits a decomposition into one or more **edge-disjoint cycles** (tracks), where each edge in $ S $ belongs to exactly one cycle. (Note: A cycle may be of length 2 — i.e., a pair of parallel edges — and multiple edges are allowed.)\n\nThe number of ski bases after $ i $ roads are built is equal to the number of subsets $ S \\subseteq E_i $ such that every connected component of $ (V, S) $ is **Eulerian** (i.e., every vertex has even degree in the subgraph induced by $ S $).\n\nThis is equivalent to: \n> The number of subsets $ S \\subseteq E_i $ such that the degree of every vertex in $ (V, S) $ is even.\n\nThis is a well-known problem in linear algebra over $ \\mathbb{F}_2 $: \nLet $ A \\in \\mathbb{F}_2^{n \\times i} $ be the incidence matrix of the graph after $ i $ edges, where each column corresponds to an edge and has exactly two 1’s (at the endpoints). \nThe set of valid subsets $ S $ corresponds to the kernel (null space) of $ A $ over $ \\mathbb{F}_2 $. \nThe number of such subsets is $ 2^{\\dim(\\ker A)} = 2^{i - \\mathrm{rank}(A)} $.\n\nLet $ r_i = \\mathrm{rank}_{\\mathbb{F}_2}(A_i) $, where $ A_i $ is the incidence matrix after $ i $ edges. \nThen the number of ski bases after $ i $ edges is:\n\n$$\n2^{i - r_i} \\mod 1000000009\n$$\n\nWe maintain the rank $ r_i $ incrementally using Gaussian elimination over $ \\mathbb{F}_2 $, tracking linear independence of each new edge vector (represented as a bitmask of size $ n $, or via union-find with parity tracking).\n\nAlternatively, using **DSU with parity (union-find for bipartiteness)**: \nWe can use a DSU that tracks connected components and parity (bipartiteness). \nEach edge $ (u, v) $:\n\n- If $ u $ and $ v $ are in different components: merge them; rank increases by 1.\n- If $ u $ and $ v $ are in the same component:\n - If the path between them has odd length → adding this edge creates an odd cycle → **linearly dependent** → rank does **not** increase.\n - If the path has even length → adding this edge creates an even cycle → **linearly dependent** → rank does **not** increase.\n\nWait — in $ \\mathbb{F}_2 $, **every** edge that connects two vertices already in the same connected component introduces a linear dependency. So:\n\n> The rank $ r_i $ is equal to $ n - c_i $, where $ c_i $ is the number of connected components in the graph after $ i $ edges, **only if** the graph is a forest. But with cycles, the rank is $ n - c_i + \\text{number of independent cycles} $.\n\nActually, for the **incidence matrix over $ \\mathbb{F}_2 $**, the rank is:\n\n$$\nr_i = n - c_i + b_i\n$$\n\nWait — no. Standard result:\n\n> The rank of the incidence matrix of a connected undirected graph over $ \\mathbb{F}_2 $ is $ n - 1 $ if the graph is bipartite, and $ n - 1 $ still? Actually, over $ \\mathbb{F}_2 $, the rank of the incidence matrix of a connected graph is $ n - 1 $ **if and only if** the graph is bipartite? No.\n\nActually, over $ \\mathbb{F}_2 $, the rank of the incidence matrix of a connected graph with $ n $ vertices is always $ n - 1 $, regardless of bipartiteness. But that’s only for simple graphs without multiple edges? No — multiple edges don’t change the rank if they are linearly dependent.\n\nActually, the correct result is:\n\n> The rank of the incidence matrix of a graph (over $ \\mathbb{F}_2 $) is $ n - c $, where $ c $ is the number of connected components, **if and only if** all connected components are **bipartite**? No.\n\nWait — correction:\n\nIn $ \\mathbb{F}_2 $, the row space of the incidence matrix has dimension $ n - c $, **and** the all-ones vector is in the kernel if there is an odd cycle? No.\n\nActually, the **nullity** (dimension of the cycle space) is $ m - n + c $, and the **rank** is $ n - c $, **but only for forests**.\n\nStandard result: \nFor an undirected graph with $ c $ connected components, the rank of the incidence matrix over $ \\mathbb{F}_2 $ is:\n\n$$\n\\mathrm{rank} = n - c\n$$\n\n**only if** the graph has no odd cycles? No — that’s not true.\n\nActually, **over $ \\mathbb{F}_2 $**, the rank of the incidence matrix is always $ n - c $, **regardless of cycles**.\n\nWait — no. Consider a triangle (3-cycle). Incidence matrix:\n\nVertices: 1,2,3 \nEdges: (1,2), (2,3), (3,1)\n\nIncidence matrix (rows=vertices, cols=edges):\n\n```\n e1 e2 e3\n1: 1 0 1\n2: 1 1 0\n3: 0 1 1\n```\n\nSum of rows: (0,0,0) mod 2 → rows are linearly dependent. Rank = 2 = 3 - 1 → still $ n - c $.\n\nAnother example: two parallel edges between 1 and 2.\n\nEdges: e1=(1,2), e2=(1,2)\n\nIncidence matrix:\n\n```\n e1 e2\n1: 1 1\n2: 1 1\n```\n\nRows are equal → rank = 1 = 2 - 1 → still $ n - c $.\n\nSo the rank of the incidence matrix over $ \\mathbb{F}_2 $ is always $ n - c $, where $ c $ is the number of connected components.\n\nThen the dimension of the cycle space (kernel) is $ m - (n - c) = m - n + c $.\n\nBut we are interested in the number of **edge subsets with all degrees even** — that is, the **cycle space**.\n\nAnd its size is $ 2^{m - n + c} $.\n\nWait — yes!\n\n> The number of Eulerian subgraphs (subsets of edges with all even degrees) is $ 2^{m - n + c} $, where $ c $ is the number of connected components.\n\nThis is a standard result in graph theory over $ \\mathbb{F}_2 $: the dimension of the cycle space is $ |E| - |V| + c $, so the number of such subsets is $ 2^{|E| - |V| + c} $.\n\nTherefore, after adding $ i $ edges:\n\nLet $ c_i $ = number of connected components in the graph after $ i $ edges.\n\nThen the number of ski bases is:\n\n$$\n2^{i - n + c_i} \\mod 1000000009\n$$\n\nWe can maintain $ c_i $ using Union-Find (DSU), and update it as edges are added.\n\nInitially: $ c_0 = n $, $ i = 0 $, so number of ski bases = $ 2^{0 - n + n} = 2^0 = 1 $ (empty set? But problem says \"non-empty set\" — wait!)\n\nWait! The problem says: \n> \"a non-empty set of roads\"\n\nSo we must **exclude the empty set**.\n\nBut in the sample: \nAfter building roads, they say \"we can choose a subset in three ways\" — and show 3 non-empty Eulerian subgraphs.\n\nSo the count should be:\n\n$$\n\\text{Answer}_i = \\left(2^{i - n + c_i} - 1\\right) \\mod 1000000009\n$$\n\nWait — but let’s test with sample:\n\nSample: n=3, m=4\n\nRoads: \n1. (1,3) → c=2, i=1 → 2^{1-3+2} = 2^0 = 1 → minus 1 = 0? But expected after first road? Probably 0, since one edge can't form a cycle.\n\n2. (2,3) → c=1, i=2 → 2^{2-3+1} = 2^0 = 1 → minus 1 = 0\n\n3. (1,2) → c=1, i=3 → 2^{3-3+1} = 2^1 = 2 → minus 1 = 1\n\n4. (1,2) again → parallel edge, c=1, i=4 → 2^{4-3+1} = 2^2 = 4 → minus 1 = 3 → matches sample!\n\nSo after 4th road: 3 ski bases — correct.\n\nAfter 3rd road: 1 ski base — which is the triangle 1-2-3-1.\n\nAfter 2nd road: 0 — correct, no cycle.\n\nAfter 1st road: 0 — correct.\n\nSo the formula is:\n\n> After $ i $ roads are built, let $ c_i $ be the number of connected components. \n> Then the number of non-empty ski bases is: \n> $$\n> \\boxed{2^{i - n + c_i} - 1 \\mod 1000000009}\n> $$\n\nWe maintain $ c_i $ using DSU with union by size/rank, and count components.\n\nWe also need to compute powers of 2 modulo $ 10^9+9 $ up to $ m \\leq 10^5 $, so precompute powers of 2.\n\nAlgorithm:\n\n- Initialize DSU with $ n $ components.\n- Precompute $ \\text{pow2}[k] = 2^k \\mod 1000000009 $ for $ k = 0 $ to $ m $.\n- For each new edge $ (a, b) $:\n - If $ a $ and $ b $ are in different components: merge them, $ c_i = c_{i-1} - 1 $\n - Else: $ c_i = c_{i-1} $\n - Compute $ \\text{answer}_i = (\\text{pow2}[i - n + c_i] - 1) \\mod 1000000009 $\n - Output answer_i\n\nNote: $ i - n + c_i $ can be negative? Initially, $ i=0 $: $ 0 - n + n = 0 $, ok. \nAfter first edge: if connects two components: $ 1 - n + (n-1) = 0 $ → $ 2^0 -1 = 0 $, ok. \nSo exponent is always ≥ 0.\n\nBecause: \n$ i \\geq n - c_i $ always? \nIn a graph, number of edges ≥ number of edges in spanning forest: $ i \\geq n - c_i $, so $ i - n + c_i \\geq 0 $.\n\nYes, because a spanning forest has $ n - c_i $ edges, and we have $ i $ edges, so $ i \\geq n - c_i \\Rightarrow i - n + c_i \\geq 0 $.\n\nThus, exponent is non-negative integer.\n\nFinal formal statement:\n\n---\n\n**Definitions:** \nLet $ n $ be the number of vertices, $ m $ the number of edges added sequentially. \nLet $ c_i $ denote the number of connected components in the graph after $ i $ edges have been added. \nLet $ \\mathbb{F} = \\mathbb{Z}/1000000009\\mathbb{Z} $.\n\n**Given:** \n- $ 2 \\leq n \\leq 10^5 $, $ 1 \\leq m \\leq 10^5 $ \n- Sequence of $ m $ edges $ (a_i, b_i) $, $ 1 \\leq i \\leq m $\n\n**Objective:** \nFor each $ i \\in \\{1, 2, \\dots, m\\} $, compute: \n$$\n\\left(2^{i - n + c_i} - 1\\right) \\mod 1000000009\n$$ \nwhere $ c_i $ is the number of connected components after adding the first $ i $ edges.\n\n**Implementation:** \nUse DSU to maintain $ c_i $ incrementally. Precompute powers of 2 modulo $ 10^9+9 $ up to $ m $.\n\n---","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF91C","tags":["combinatorics","dsu","graphs"],"sample_group":[["3 4\n1 3\n2 3\n1 2\n1 2","0\n0\n1\n3"]],"created_at":"2026-03-03 11:00:39"}}