CF1093D Beautiful Graph

给定一个无向无权图，包含 $n$ 个顶点和 $m$ 条边。 你需要在图的每个顶点上写一个数字。每个数字只能是 $1$、$2$ 或 $3$。如果对于每一条边，其两端顶点上的数字之和为奇数，则称该图是美丽的。 请计算有多少种方法可以在顶点上填写 $1$、$2$、$3$，使得图变为美丽的。由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。 注意，每个顶点必须且只能写一个数字。 图中不存在自环或重边。

第一行包含一个整数 $t$（$1 \le t \le 3 \times 10^5$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 3 \times 10^5, 0 \le m \le 3 \times 10^5$），分别表示顶点数和边数。接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n; u_i \neq v_i$），表示第 $i$ 条边连接的两个顶点编号。 保证所有测试用例中 $\sum\limits_{i=1}^{t} n \le 3 \times 10^5$ 且 $\sum\limits_{i=1}^{t} m \le 3 \times 10^5$。

对于每个测试用例，输出一行一个整数，表示使图变为美丽的方案数。由于答案可能很大，请输出对 $998244353$ 取模后的结果。

第一个测试用例的所有可能分配方式如下： 1. 顶点 $1$ 填写 $1$，顶点 $2$ 填写 $2$； 2. 顶点 $1$ 填写 $3$，顶点 $2$ 填写 $2$； 3. 顶点 $1$ 填写 $2$，顶点 $2$ 填写 $1$； 4. 顶点 $1$ 填写 $2$，顶点 $2$ 填写 $3$。 在第二个测试用例中，没有任何一种分配方式满足条件。 由 ChatGPT 4.1 翻译