18467번 - Just Counting 다국어

You are given an undirected graph without loops and multiple edges.

Find the number of ways to write integers [0; 4] on edges such that for each vertex, the sum of weights of edges incident to it will be equal to zero modulo five (i.e. is equal to 5k for some integer k).

As the answer may be very large, you only need to find it modulo 998 244 353.

The first line of input contains one integer t (1 ≤ t ≤ 500 000): the number of testcases.

The next lines contain t descriptions of test cases.

The first line of each test case contains two integers n, m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 300 000): the number of vertices.

The next m lines contain descriptions of edges, where the i-th of them contains two integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), denoting an edge connecting vertices a_i and b_i in the graph.

It is guaranteed that there are no multiple edges.

It is also guaranteed that the total sum of n + m in all test cases is at most 500 000.

For each test case, print one integer: the number of ways to write integers [0; 4] on edges such that for each vertex, the sum of weights of edges incident to it will be equal to zero modulo five (i.e. is equal to 5k for some integer k), modulo 998 244 353.