[ZJOI2017] 仙人掌
题目描述
如果一个**无自环无重边无向连通图**的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。
![](https://cdn.luogu.com.cn/upload/pic/4742.png)
现在九条可怜手上有一张**无自环无重边的无向连通图**,但是她觉得这张图中的边数太少了,所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图,图中的边数又不能太多。经过权衡,她想要加边后得到的图为一棵仙人掌。
不难发现合法的加边方案有很多,可怜想要知道总共有多少不同的加边方案。
两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。
输入输出格式
输入格式
多组数据,第一行输入一个整数 $T$ 表示数据组数。
每组数据第一行输入两个整数 $n$,$m$,表示图中的点数与边数。
接下来 m 行,每行两个整数 $u$,$v$(1 ≤ $u$,$v$ ≤ $n$,$u$ ≠ $v$) 表示图中的一条边。保证输入的图联通且没有自环与重边。
输出格式
对于每组数据,输出一个整数表示方案数,当然方案数可能很大,请对 998244353 取模后输出。
输入输出样例
输入样例 #1
2
3 2
1 2
1 3
5 4
1 2
2 3
2 4
1 5
输出样例 #1
2
8
说明
**样例说明**
对于第一组样例合法加边的方案有 {},{(2,3)},共 2 种。
**时空限制**
时间限制1s,空间限制512M。
**数据范围**
![](https://cdn.luogu.com.cn/upload/pic/4743.png)