CF1093D.Beautiful Graph

You are given an undirected unweighted graph consisting of $n$ vertices and $m$ edges.

You have to write a number on each vertex of the graph. Each number should be $1$, $2$ or $3$. The graph becomes beautiful if for each edge the sum of numbers on vertices connected by this edge is odd.

Calculate the number of possible ways to write numbers $1$, $2$ and $3$ on vertices so the graph becomes beautiful. Since this number may be large, print it modulo $998244353$.

Note that you have to write exactly one number on each vertex.

The graph does not have any self-loops or multiple edges.

你被给定一个由 $n$ 个顶点和 $m$ 条边构成的无向无权图。

你需要在图的每个顶点上写一个数字，该数字只能是 $1$、$2$ 或 $3$。若对图中每条边，其两个端点上的数字之和均为奇数，则称该图为“优美的”。

请计算有多少种方式在顶点上写数字 $1$、$2$ 和 $3$，使得该图变为优美的。由于答案可能很大，请输出其对 $998244353$ 取模的结果。

注意：每个顶点上必须且只能写一个数字。

该图不含自环或重边。

The first line contains one integer $t$ ($1 \le t \le 3 \cdot 10^5$) — the number of tests in the input.

The first line of each test contains two integers $n$ and $m$ ($1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^5$) — the number of vertices and the number of edges, respectively. Next $m$ lines describe edges: $i$-th line contains two integers $u_i$, $ v_i$ ($1 \le u_i, v_i \le n; u_i \neq v_i$) — indices of vertices connected by $i$-th edge.

It is guaranteed that $\sum\limits_{i=1}^{t} n \le 3 \cdot 10^5$ and $\sum\limits_{i=1}^{t} m \le 3 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test print one line, containing one integer — the number of possible ways to write numbers $1$, $2$, $3$ on the vertices of given graph so it becomes beautiful. Since answers may be large, print them modulo $998244353$.

对每组测试数据，输出一行，包含一个整数——即在给定图的顶点上填入数字 $1$、$2$、$3$ 使其变为“优美图”的方案数。由于答案可能很大，请对 $998244353$ 取模后输出。

Possible ways to distribute numbers in the first test:

1. the vertex $1$ should contain $1$, and $2$ should contain $2$;
2. the vertex $1$ should contain $3$, and $2$ should contain $2$;
3. the vertex $1$ should contain $2$, and $2$ should contain $1$;
4. the vertex $1$ should contain $2$, and $2$ should contain $3$.

In the second test there is no way to distribute numbers.

第一次测试中数字的可能分配方式：

1. 顶点 $1$ 应包含 $1$，顶点 $2$ 应包含 $2$；
2. 顶点 $1$ 应包含 $3$，顶点 $2$ 应包含 $2$；
3. 顶点 $1$ 应包含 $2$，顶点 $2$ 应包含 $1$；
4. 顶点 $1$ 应包含 $2$，顶点 $2$ 应包含 $3$。

在第二次测试中，不存在可行的数字分配方式。