그냥 세기

루프와 중복 간선이 없는 무방향 그래프가 주어진다.

각 간선에 [0; 4] 범위의 정수를 적어, 모든 정점에서 그 정점에 붙은 간선들의 가중치 합이 5로 나눈 나머지가 0이 되도록(즉, 어떤 정수 k에 대해 5k가 되도록) 하는 방법의 수를 구하라.

답이 매우 클 수 있으므로 998 244 353으로 나눈 나머지를 구하면 된다.

첫째 줄에 정수 t (1 ≤ t ≤ 500 000)가 주어진다. 이는 테스트케이스의 수이다.

다음 줄들에 t개의 테스트케이스 설명이 이어진다.

각 테스트케이스의 첫째 줄에는 두 정수 n, m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 300 000)이 주어진다. n은 정점의 수이다.

다음 m개의 줄에는 간선의 설명이 주어지며, i번째 줄에는 두 정수 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)가 주어져 그래프에서 정점 ai와 bi를 잇는 간선을 나타낸다.

중복 간선은 없다.

모든 테스트케이스에서 n + m의 합은 500 000 이하이다.

각 테스트케이스마다, 각 간선에 [0; 4] 범위의 정수를 적어 모든 정점에서 그 정점에 붙은 간선들의 가중치 합이 5로 나눈 나머지가 0이 되도록 하는 방법의 수를 998 244 353으로 나눈 나머지를 한 줄에 출력한다.