CF91C.Ski Base

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.

计划在海象国（Walrusland）建造一座滑雪基地。然而，截至目前，该项目仍处于建设阶段。已选定一块广阔的地块用于施工。该地块内包含 $n$ 个滑雪枢纽（junction），编号从 $1$ 到 $n$。初始时，这些枢纽之间彼此互不连通。

在建设过程中，将依次修建 $m$ 条双向滑雪道路（ski road）。道路按顺序逐条修建：先修建第 $1$ 条道路，再修建第 $2$ 条道路，依此类推。其中，第 $i$ 条道路连接编号为 $a_i$ 和 $b_i$ 的两个枢纽。

所谓环路（track），是指满足以下条件的一条路径：

• 路径是闭合的，即起点与终点为同一个枢纽；
• 路径至少包含一条道路；
• 路径中每条道路至多经过一次，但可任意多次访问任一枢纽。

我们定义一个滑雪基地（ski base） 为一个非空的道路集合，该集合可被划分为一个或多个环路，使得所选集合中的每条道路恰好属于且仅属于其中一个环路；此外，每个环路所含的道路必须全部来自该选定集合。注意：滑雪基地不必连通。

若两个滑雪基地所含的道路集合不同，则认为它们是不同的。

在每条新道路建成之后，海象国政府希望知道：基于目前已建成的所有道路的某个子集，能构成多少种不同的滑雪基地？政府请你帮助他们解决这一问题。

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.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$1 \leq m \leq 10^5$），分别表示路口的数量和道路的数量。接下来的 $m$ 行按道路修建的顺序描述这些道路。每条道路由一对整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$）描述，表示该道路所连接的两个路口的编号。同一对路口之间可能存在多条道路。

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).

输出 m 行：第 i 行应表示在修建完第 i 条道路后，建造滑雪场基地的方案数。所有数字需对 1000000009（即 $10^9 + 9$）取模后输出。

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:

The land lot for the construction will look in the following way:

We can choose a subset of roads in three ways:

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.

我们已有 3 个路口，且在这些路口之间已建成 4 条道路（如样例中全部道路建成后的状态）：路口 1 与路口 3 之间 1 条，路口 2 与路口 3 之间 1 条，路口 1 与路口 2 之间 2 条。施工用地将如下所示：

施工用地的具体结构如下所示：

我们可以以三种方式选取道路的一个子集：

在第一种和第二种方式中，你可以选择一条路径，例如 $1 - 2 - 3 - 1$；在第一种方式中，你也可以选择路径 $1 - 2 - 1$。