给你一个无向无权图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。
您必须在图的每个顶点上写一个数字。每个数字应为 $$$1$$$、$$$2$$$ 或 $$$3$$$。如果对于每条边,由该边连接的顶点上的数字之和是奇数,那么该图就会变得很漂亮。
计算在顶点上写数字 $$$1$$$、$$$2$$$ 和 $$$3$$$ 的可能方式的数量,使图形变得漂亮。由于这个数字可能很大,因此打印它对 $$$998244353$$$ 取模。
请注意,您必须在每个顶点上准确地写入一个数字。
该图没有任何自环或多重边。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — 输入中的测试数量。
每个测试的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^5$$$) — 分别是顶点数和边数。接下来的 $$$m$$$ 行描述边:第 $$$i$$$ 行包含两个整数 $$$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 \cdot 10^5$$$ 和 $$$\sum\limits_{i=1}^{t} m \le 3 \cdot 10^5$$$。
输出
对于每个测试打印一行,包含一个整数 - 在给定图的顶点上写数字 $$$1$$$、$$$2$$$、$$$3$$$ 的可能方法数,以便它变得漂亮。由于答案可能很大,请以 $$$998244353$$$ 为模打印它们。
示例
输入 #1
2 2 1 1 2 4 6 1 2 1 3 1 4 2 3 2 4 3 4
输出 #1
4 0
注意
在第一次测试中分配数字的可能方法:
1. 顶点$$$1$$$应包含$$$1$$$,$$$2$$$应包含$$$2$$$;
2. 顶点$$$1$$$应包含$$$3$$$,$$$2$$$应包含$$$2$$$;
3. 顶点$$$1$$$应包含$$$2$$$,$$$2$$$应包含$$$1$$$;
4. 顶点$$$1$$$应包含$$$2$$$,$$$2$$$应包含$$$3$$$。
在第二次测试中,无法分配数字。