1093D - Beautiful Graph - CodeForces Solution

import gc
import heapq
import itertools
import math
import sqlite3
from collections import Counter, deque, defaultdict
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import threading
from heapq import *
from fractions import Fraction


def S():
    return sys.stdin.readline().split()


def I():
    return [int(i) for i in sys.stdin.readline().split()]


def II():
    return int(sys.stdin.readline())


def IS():
    return sys.stdin.readline().replace('\n', '')


def main():
    n, m = I()
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v = I()
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)
    visited = [-1] * n
    pool = set(range(n))
    ans = 1
    while pool:
        v = pool.pop()
        visited[v] = 0
        d = [1, 0]
        queue = deque([v])
        while queue:
            v = queue.pop()
            for u in graph[v]:
                if visited[u] == -1:
                    queue.append(u)
                    visited[u] = visited[v] ^ 1
                    d[visited[u]] += 1
                    pool.remove(u)
                elif visited[u] ^ visited[v] == 0:
                    print(0)
                    return
        ans = (ans * (pow(2, d[0], mod) + pow(2, d[1], mod))) % mod
    print(ans)


if __name__ == '__main__':
    mod = 998244353
    for _ in range(II()):
        main()