← 返回题目列表

Codeforces · 1093/D

D. 美丽的图表

中文机器翻译题面 查看原题

给你一个无向无权图,由 $$$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$$$。

在第二次测试中,无法分配数字。