#P17492. PM15279 连通生成子图计数

PM15279 连通生成子图计数

题目描述

给定一个有 nn 个点、mm 条边的无向图,顶点编号为 0,1,…,n−10,1,\ldots,n-1。图中允许出现自环和重边。

定义 f(k)f(k) 为:从 mm 条边中恰好选择 kk 条,使得保留全部 nn 个顶点以及所选边后得到的图连通的方案数。

令 g(k)=f(k) mod (109+7)g(k)=f(k)\bmod(10^9+7)。

请依次输出

g(n−1),g(n),…,g(m)g(n-1),g(n),\ldots,g(m)。

输入格式

第一行输入两个整数 n,mn,m。

接下来 mm 行,每行两个整数 ui,viu_i,v_i,表示一条连接 uiu_i 与 viv_i 的无向边。允许 ui=viu_i=v_i,也允许多条边拥有相同端点。

输出格式

第一行输出一个整数 m−n+2m-n+2,表示答案个数。

第二行输出 m−n+2m-n+2 个整数,依次为 g(n−1),g(n),…,g(m)g(n-1),g(n),\ldots,g(m)。

数据范围

  • 1≤n≤151\le n\le15;
  • n−1≤m≤200n-1\le m\le200;
  • 0≤ui,vi<n0\le u_i,v_i<n。