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.
In 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_.
Track is the route with the following properties:
* The route is closed, that is, it begins and ends in one and the same junction.
* The route contains at least one road.
* The route doesn't go on one road more than once, however it can visit any junction any number of times.
Let'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.
Two ski bases are considered different if they consist of different road sets.
After 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.
## Input
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.
## Output
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).
[samples]
## Note
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:
<center></center>The land lot for the construction will look in the following way:
<center></center>We can choose a subset of roads in three ways:
<center></center>In 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.
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.
A **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.)
The 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 $).
This is equivalent to:
> The number of subsets $ S \subseteq E_i $ such that the degree of every vertex in $ (V, S) $ is even.
This is a well-known problem in linear algebra over $ \mathbb{F}_2 $:
Let $ 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).
The set of valid subsets $ S $ corresponds to the kernel (null space) of $ A $ over $ \mathbb{F}_2 $.
The number of such subsets is $ 2^{\dim(\ker A)} = 2^{i - \mathrm{rank}(A)} $.
Let $ r_i = \mathrm{rank}_{\mathbb{F}_2}(A_i) $, where $ A_i $ is the incidence matrix after $ i $ edges.
Then the number of ski bases after $ i $ edges is:
$$
2^{i - r_i} \mod 1000000009
$$
We 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).
Alternatively, using **DSU with parity (union-find for bipartiteness)**:
We can use a DSU that tracks connected components and parity (bipartiteness).
Each edge $ (u, v) $:
- If $ u $ and $ v $ are in different components: merge them; rank increases by 1.
- If $ u $ and $ v $ are in the same component:
- If the path between them has odd length → adding this edge creates an odd cycle → **linearly dependent** → rank does **not** increase.
- If the path has even length → adding this edge creates an even cycle → **linearly dependent** → rank does **not** increase.
Wait — in $ \mathbb{F}_2 $, **every** edge that connects two vertices already in the same connected component introduces a linear dependency. So:
> 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} $.
Actually, for the **incidence matrix over $ \mathbb{F}_2 $**, the rank is:
$$
r_i = n - c_i + b_i
$$
Wait — no. Standard result:
> 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.
Actually, 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.
Actually, the correct result is:
> 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.
Wait — correction:
In $ \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.
Actually, the **nullity** (dimension of the cycle space) is $ m - n + c $, and the **rank** is $ n - c $, **but only for forests**.
Standard result:
For an undirected graph with $ c $ connected components, the rank of the incidence matrix over $ \mathbb{F}_2 $ is:
$$
\mathrm{rank} = n - c
$$
**only if** the graph has no odd cycles? No — that’s not true.
Actually, **over $ \mathbb{F}_2 $**, the rank of the incidence matrix is always $ n - c $, **regardless of cycles**.
Wait — no. Consider a triangle (3-cycle). Incidence matrix:
Vertices: 1,2,3
Edges: (1,2), (2,3), (3,1)
Incidence matrix (rows=vertices, cols=edges):
```
e1 e2 e3
1: 1 0 1
2: 1 1 0
3: 0 1 1
```
Sum of rows: (0,0,0) mod 2 → rows are linearly dependent. Rank = 2 = 3 - 1 → still $ n - c $.
Another example: two parallel edges between 1 and 2.
Edges: e1=(1,2), e2=(1,2)
Incidence matrix:
```
e1 e2
1: 1 1
2: 1 1
```
Rows are equal → rank = 1 = 2 - 1 → still $ n - c $.
So the rank of the incidence matrix over $ \mathbb{F}_2 $ is always $ n - c $, where $ c $ is the number of connected components.
Then the dimension of the cycle space (kernel) is $ m - (n - c) = m - n + c $.
But we are interested in the number of **edge subsets with all degrees even** — that is, the **cycle space**.
And its size is $ 2^{m - n + c} $.
Wait — yes!
> 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.
This 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} $.
Therefore, after adding $ i $ edges:
Let $ c_i $ = number of connected components in the graph after $ i $ edges.
Then the number of ski bases is:
$$
2^{i - n + c_i} \mod 1000000009
$$
We can maintain $ c_i $ using Union-Find (DSU), and update it as edges are added.
Initially: $ 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!)
Wait! The problem says:
> "a non-empty set of roads"
So we must **exclude the empty set**.
But in the sample:
After building roads, they say "we can choose a subset in three ways" — and show 3 non-empty Eulerian subgraphs.
So the count should be:
$$
\text{Answer}_i = \left(2^{i - n + c_i} - 1\right) \mod 1000000009
$$
Wait — but let’s test with sample:
Sample: n=3, m=4
Roads:
1. (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.
2. (2,3) → c=1, i=2 → 2^{2-3+1} = 2^0 = 1 → minus 1 = 0
3. (1,2) → c=1, i=3 → 2^{3-3+1} = 2^1 = 2 → minus 1 = 1
4. (1,2) again → parallel edge, c=1, i=4 → 2^{4-3+1} = 2^2 = 4 → minus 1 = 3 → matches sample!
So after 4th road: 3 ski bases — correct.
After 3rd road: 1 ski base — which is the triangle 1-2-3-1.
After 2nd road: 0 — correct, no cycle.
After 1st road: 0 — correct.
So the formula is:
> After $ i $ roads are built, let $ c_i $ be the number of connected components.
> Then the number of non-empty ski bases is:
> $$
> \boxed{2^{i - n + c_i} - 1 \mod 1000000009}
> $$
We maintain $ c_i $ using DSU with union by size/rank, and count components.
We also need to compute powers of 2 modulo $ 10^9+9 $ up to $ m \leq 10^5 $, so precompute powers of 2.
Algorithm:
- Initialize DSU with $ n $ components.
- Precompute $ \text{pow2}[k] = 2^k \mod 1000000009 $ for $ k = 0 $ to $ m $.
- For each new edge $ (a, b) $:
- If $ a $ and $ b $ are in different components: merge them, $ c_i = c_{i-1} - 1 $
- Else: $ c_i = c_{i-1} $
- Compute $ \text{answer}_i = (\text{pow2}[i - n + c_i] - 1) \mod 1000000009 $
- Output answer_i
Note: $ i - n + c_i $ can be negative? Initially, $ i=0 $: $ 0 - n + n = 0 $, ok.
After first edge: if connects two components: $ 1 - n + (n-1) = 0 $ → $ 2^0 -1 = 0 $, ok.
So exponent is always ≥ 0.
Because:
$ i \geq n - c_i $ always?
In a graph, number of edges ≥ number of edges in spanning forest: $ i \geq n - c_i $, so $ i - n + c_i \geq 0 $.
Yes, 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 $.
Thus, exponent is non-negative integer.
Final formal statement:
---
**Definitions:**
Let $ n $ be the number of vertices, $ m $ the number of edges added sequentially.
Let $ c_i $ denote the number of connected components in the graph after $ i $ edges have been added.
Let $ \mathbb{F} = \mathbb{Z}/1000000009\mathbb{Z} $.
**Given:**
- $ 2 \leq n \leq 10^5 $, $ 1 \leq m \leq 10^5 $
- Sequence of $ m $ edges $ (a_i, b_i) $, $ 1 \leq i \leq m $
**Objective:**
For each $ i \in \{1, 2, \dots, m\} $, compute:
$$
\left(2^{i - n + c_i} - 1\right) \mod 1000000009
$$
where $ c_i $ is the number of connected components after adding the first $ i $ edges.
**Implementation:**
Use DSU to maintain $ c_i $ incrementally. Precompute powers of 2 modulo $ 10^9+9 $ up to $ m $.
---