#P9745. 数树

    ID: 6369 传统题 3000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-深度优先搜索状压 DP轮廓线 DP计数 DP轮廓状态规范化预计算转移

数树

题目描述

给定一张连通无向图 G=(V,E)G=(V,E)。保证不存在从顶点 11 出发、恰好经过 88 个顶点的简单路径,即不存在形如 (1,v1,v2,…,v7)(1,v_1,v_2,\ldots,v_7) 的简单路径。

求 GG 的生成树个数,对 2302^{30} 取模。图可以包含自环和重边。不同的平行边视为不同的边,自环不会出现在生成树中。

输入格式

第一行一个正整数 TT,表示数据组数。

对于每组数据,第一行两个整数 n,mn,m,表示顶点数和边数。接下来 mm 行,每行两个正整数 u,vu,v,表示一条连接 uu 和 vv 的边。

输出格式

对于每组数据,输出一行一个整数,表示生成树个数对 2302^{30} 取模后的结果。

样例

3
2 4
1 1
2 2
1 2
1 2
5 5
1 2
2 3
3 4
4 5
1 5
10 16
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
9 10
8 10
7 10
6 10
5 10
4 10
3 10
2 10
2
5
1024

原 PDF 在第三组数据的 1616 条边之后多列了一行 1 10。上面的样例按输入声明保留 1616 条边,对应原样例答案 10241024。

原题另有下发样例,见 tree.in 和 tree.out。

数据范围

  • 对于 25% 的数据,n,m≤200n,m\le200。
  • 对于 50% 的数据,n,m≤10000n,m\le10000。
  • 对于另外 25% 的数据,保证 T=1T=1。
  • 对于全部数据,1≤T≤101\le T\le10,1≤n≤500001\le n\le50000,1≤m≤1000001\le m\le100000。

原 PDF 题面