J11 习题-3 黑魔法师之门

题目描述

经过了 $16$ 个工作日的紧张忙碌，未来的人类终于收集到了足够的能源。然而在与 $\text{Violet}$ 星球的战争中，由于 $\text{Z}$ 副官的愚蠢，地球的领袖 $\text{applepi}$ 被邪恶的黑魔法师 $\text{Vani}$ 囚禁在了 $\text{Violet}$ 星球。为了重启 $\text{Nescafé}$ 这一宏伟的科技工程，人类派出了一支由 $\text{XLk}$、$\text{Poetshy}$ 和 $\text{lydrainbowcat}$ 三人组成的精英队伍，穿越时空隧道，去往 $\text{Violet}$ 星球拯救领袖 $\text{applepi}$ 。

$\text{applepi}$ 被囚禁的地点只有一扇门，当地人称它为“黑魔法师之门”。这扇门上画着一张无向无权图，而打开这扇门的密码就是图中【每个点的度数大于零且都是偶数】的子图的个数对 $1000000009$ 取模的值。此处子图 $(V, E)$ 定义为：点集 $V$ 和边集 $E$ 都是原图的任意子集，其中 $E$ 中的边的端点都在 $V$ 中。

但是 $\text{Vani}$ 认为这样的密码过于简单，因此门上的图是动态的。起初图中只有 $N$ 个顶点而没有边。$Vani$ 建造的门控系统共操作 $M$ 次，每次往图中添加一条边。你必须在每次操作后都填写正确的密码，才能够打开黑魔法师的牢狱，去拯救伟大的领袖 $\text{applepi}$。

输入格式

第一行包含两个整数 $N$和 $M$。 接下来 $M$ 行，每行两个整数 $A$ 和 $B$，代表门控系统添加了一条无向边 $(A, B)$。

输出格式

输出一共 $M$ 行，表示每次操作后的密码。

输入样例

4 8
3 1
3 2
2 1
2 1
1 3
1 4
2 4
2 3

输出样例

0
0
1
3
7
7
15
31

样例分析

如上所述。

数据范围

对于 $30\%$ 的数据：$N, M \le 10$；

对于 $100\%$ 的数据：$N \le 200000,M \le 300000$；