#P9745. 数树
数树
题目描述
给定一张连通无向图 。保证不存在从顶点 出发、恰好经过 个顶点的简单路径,即不存在形如 的简单路径。
求 的生成树个数,对 取模。图可以包含自环和重边。不同的平行边视为不同的边,自环不会出现在生成树中。
输入格式
第一行一个正整数 ,表示数据组数。
对于每组数据,第一行两个整数 ,表示顶点数和边数。接下来 行,每行两个正整数 ,表示一条连接 和 的边。
输出格式
对于每组数据,输出一行一个整数,表示生成树个数对 取模后的结果。
样例
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 在第三组数据的 条边之后多列了一行 1 10。上面的样例按输入声明保留 条边,对应原样例答案 。
原题另有下发样例,见 tree.in 和 tree.out。
数据范围
- 对于 25% 的数据,。
- 对于 50% 的数据,。
- 对于另外 25% 的数据,保证 。
- 对于全部数据,,,。