A8260 | Ski Base

The first line contains two integers $n$ and $m$ ( $2<=n<=10^{5},1<=m<=10^{5}$ ). 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.

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$ ( $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.