A6066 | $「ZJOI2017」仙人掌$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人 掌。所谓简单环即不经过重复的结点的环。 <img src="http://img.uoj.ac/utility/what-is-cactus.png"> 现在九条可怜手上有一张**无自环无重边的无向连通图**，但是她觉得这张图中的边数太少了， 所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图，图中的边数又不能太多。 经过权衡，她想要加边后得到的图为一棵仙人掌。 不难发现合法的加边方案有很多，可怜想要知道总共有多少不同的加边方案。 两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

多组数据，第一行输入一个整数 $T$ 表示数据组数。 每组数据第一行输入两个整数 $n,m$，表示图中的点数与边数。 接下来 $m$ 行，每行两个整数 $u, v(1\leq u,v \leq n ,u \neq v)$ 表示图中的一条边。保证输入的图 联通且没有自环与重边。

对于每组数据，输出一个整数表示方案数，当然方案数可能很大，请对 $998244353$ 取模后 输出。

输入 #1

输出 #1

2
8

C++ 编辑器

输入

输出