#P2389. XY的赛车场

    ID: 1432 传统题 1000ms 128MiB 尝试: 97 已通过: 49 难度: 5 上传者: 标签>CF1800普及+/提高-欧拉回路双射计数奇偶性分析普通并查集路径压缩按大小合并

XY的赛车场

题目描述

神牛 XY 是一中信息组最牛逼,也是最富有的孩子,而他又是一个赛车迷。XY 神牛要成年了,所以他的父亲 XZG 准备给他建一座 赛车场。XZG 要建这座赛车场上有 NN 个连接点,建 MM 截直道,连接这 NN 个连接点(不存在从 ii 到 ii 的直道)。而建这 MM 截直道是有顺序的,按从 11 到 MM 建。

对于建设过程中的赛车场,XZG 希望知道这时 XY 是否可以使用赛车场了,使用的方法有几种。而赛车场可以使用的标准如下:

  1. 赛车跑道必须由已建的直道组成,即选出组成赛车跑道的直道是已建直道的子集。
  2. 赛车跑道必须是封闭的,即必须从任意一个点出发可以回到这个点。
  3. 每个连接点可以多次经过,但是每条直道只能经过一次。

(修者注:即选出一个赛道的子集使得每个联通块都是欧拉图)

XZG 想知道对于修好第 11 至第 MM 条直道后可行的组成赛车场的方案有多少种。

输入格式

输入第一行是两个数 NN 和 MM。

接下来 MM 行,每行两个数 A,BA,B,表示第 ii 条直道连接 AA 到 BB。

输出格式

MM 行,每行一个数 SiS_i 表示表示连接了第 ii 条直道后的方案数。由于答案较大,所以答案 mod  109+9\mod 10^9+9。

样例输入

3 4
1 3
2 3
1 2
1 2

样例输出

0
0
1
3

数据规模与约定

对于 10%10\% 的数据,1≤N≤10,1≤M≤101\le N\le 10,1\le M\le 10;

对于 40%40\% 的数据,1≤N≤103,1≤M≤5×1041\le N\le 10^3,1\le M\le 5\times 10^4;

对于 100%100\% 的数据,1≤N≤5×105,1≤M≤1061\le N\le 5\times 10^5,1\le M\le 10^6;