如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

现在九条可怜手上有一张无自环无重边的无向连通图，但是她觉得这张图中的边数太少了，

所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图，图中的边数又不能太多。

经过权衡，她想要加边后得到的图为一棵仙人掌。不难发现合法的加边方案有很多，可怜想要知道总共有多少不同的加边方案。两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

输入格式

多组数据，第一行输入一个整数 $T$ 表示数据组数。

每组数据第一行输入两个整数 $n,m$，表示图中的点数与边数。

接下来 $m$ 行，每行两个整数 $u,v(1\le u,v\le n,u\ne v)$ 表示图中的一条边。保证输入的图连通且没有自环与重边。

输出格式

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

样例一

input

2
3 2
1 2
1 3
5 4
1 2
2 3
2 4
1 5

output

2
8

explanation

对于第一组样例合法加边的方案有 $\{\},\{(2,3)\}$，共 $2$ 种。

样例二

见样例数据下载。

限制与约定

对于 100% 的数据，保证 $1\le m\le \frac{n(n-1)}{2},\sum m\le {10}^6$。

注意 $T$ 可能较大，请注意控制初始化的复杂度。

样例二的四组数据依次满足第 2, 4, 6, 8 个点的条件。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载