← 返回题目列表

Codeforces · 91/C

C. 滑雪基地

中文机器翻译题面 查看原题

海象岛计划建设滑雪基地。但近期,该项目仍处于建设阶段。选择了一大片土地进行建设。它包含n个滑雪连接点,编号从1到n。最初,连接点没有以任何方式连接。

建设过程中将修建m条双向滑雪道。道路是依次修建的:首先修建 1 号公路,然后修建 2 号公路,以此类推。第 i 条路连接编号为 ai 和 bi 的路口。

Track 是具有以下属性的路线:

- 路线是封闭的,也就是说,它的起点和终点都是同一个路口。
- 该路线至少包含一条道路。
- 该路线不会在一条道路上行驶多次,但它可以多次访问任何路口。

让我们将滑雪基地视为一组非空的道路,可以将其分为一条或多条轨道,以便只有一条轨道沿着所选组的每条道路行驶。此外,每条轨道只能由所选组中的道路组成。滑雪基地不必连接。

如果两个滑雪基地由不同的道路组组成,则它们被视为不同。

在修建每条新道路后,海象国政府希望了解根据已建成道路的某些子集选择滑雪基地的变体数量。政府要求您帮助他们解决给定的问题。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105)。它们分别代表路口的数量和相应的道路的数量。然后在 m 行上按照道路的建造顺序描述道路。每条道路由一对整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi) 描述 - 连接路口的数量。一对路口之间可能有多条道路。

输出

打印m行:第i行应表示第i条路施工结束后,有多少种方式可以建造滑雪基地。数字应以 1000000009 (109 + 9) 为模打印。

示例

输入 #1

3 4
1 3
2 3
1 2
1 2

输出 #1

0
0
1
3

注意

假设有 3 个路口和路口之间的 4 条道路已经建成(在示例中修建所有道路之后):1 和 3、2 和 3、路口 1 和 2 之间有 2 条道路。用于建设的土地将如下所示:

建设用地如下:

我们可以通过三种方式选择道路子集:

在第一种和第二种方式中,您可以选择一条路径,例如1 - 2 - 3 - 1。在第一种情况下,您可以选择一条路径1 - 2 - 1。