You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

想要治愈一个人，我们需要给他运气，智力，还有 GF。

题目描述

小 M 需要被治愈。对一张无向连通图，每一条边我们都可以给运气，智力，GF 之一。这样的一张图可以治愈小 M 当且仅当存在一条简单路径使得经过运气，智力，GF 三种边。

你需要给小 M 一张给定的图，给每条边给予运气，智力，GF 之一，使得它可以治愈小 M。

你觉得治愈小 M 还不够，你还要数数有多少种不同的给予方案。对 $998244353$ 取模。

输入格式

本题单点含有多组测试数据。

第一行一个正整数 $T$。

每个测试点第一行两个正整数 $n,m$ 表示这张图的点数，边数。

接下来 $m$ 行，每行两个正整数表示边。 保证图无重边自环。

输出格式

$T$ 行，每行一个非负实数表示答案。

测试样例

样例解释

对于样例 $1$，第一组数据没有简单路径经过三条边，所以无解。第二组样例是一条链，只要同时出现三种颜色就可以，由容斥原理，$3^4-3\times 2^4+3=36$。

样例中 heart2 满足测试点 $1$ 的性质。

样例中 heart3 满足测试点 $2,3$ 性质。

样例中 heart4 测试数据依次满足 $1,2,3,4,5,6,7,8,9,10$ 的数据范围。

数据范围

• 特殊性质 A：保证每条边形如 $i,i+1$。
• 特殊性质 B：保证每条边形如 $i,i\bmod n+1$。
• 特殊性质 C：每条边最多属于一个环内。
• 特殊性质 D：保证 $m=\dfrac{n\times (n+1)}{2}$。
• 特殊性质 E：保证图随机生成。具体方法：先随机生成 $n$，再随机生成合法的边。