406784: GYM102538 J Just Counting
Description
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$$$.
InputThe 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$$$.
OutputFor 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$$$.
ExampleInput3 1 0 3 3 1 2 2 3 3 1 4 4 1 2 2 3 3 4 4 1Output
1 1 5