CF91C.Ski Base

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

输入输出样例

输入#1
```
3 4
1 3
2 3
1 2
1 2
```
输出#1
```
0
0
1
3
```

说明/提示

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.

首页