자기 루프나 다중 간선이 없는 무방향 그래프가 주어집니다.

그래프의 각 정점에 음이 아닌 정수 값을 할당합니다. 어떤 할당이 다음 두 조건을 만족하면 유효하다고 합니다:

• 인접한 임의의 두 정점의 값의 차이는 정확히 $1$입니다;
• 어떤 정점의 값이 그 모든 이웃 정점들의 값보다 엄격하게 작다면, 그 정점의 값은 $0$과 같습니다.

유효한 할당의 개수를 $998\,244\,353$으로 나눈 나머지를 구하세요. 두 할당에서 서로 다른 값을 가지는 정점이 존재한다면 두 할당은 서로 다릅니다.

입력 형식

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $t$가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 $n$과 $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$)이 주어집니다.

다음 $m$개의 줄 각각에는 해당하는 간선의 양 끝점을 나타내는 두 정수 $u$와 $v$ ($1 \le u, v \le n$, $u \ne v$)가 주어집니다. 그래프는 자기 루프나 다중 간선을 포함하지 않습니다. 모든 정점은 적어도 하나의 이웃을 가집니다.

모든 테스트 케이스에 대한 $m$의 합은 $10^6$을 초과하지 않습니다.

출력 형식

각 테스트 케이스마다 유효한 할당의 개수를 $998\,244\,353$으로 나눈 나머지를 나타내는 정수 하나를 출력합니다.

예제

입력 형식 1

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

출력 형식 1

6
0