406784: GYM102538 J 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 \leq t \leq 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 \leq n \leq 200\,000, 0 \leq m \leq 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 \leq a_i, b_i \leq n, a_i \neq 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$$$.

3
1 0
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1

1
1
5