You are given an undirected unweighted graph consisting of $n$ vertices and $m$ edges.

You have to write a number on each vertex of the graph. Each number should be $1$, $2$ or $3$. The graph becomes beautiful if for each edge the sum of numbers on vertices connected by this edge is odd.

Calculate the number of possible ways to write numbers $1$, $2$ and $3$ on vertices so the graph becomes beautiful. Since this number may be large, print it modulo $998244353$.

Note that you have to write exactly one number on each vertex.

The graph does not have any self-loops or multiple edges.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 3 \cdot 10^5$) — the number of tests in the input.

The first line of each test contains two integers $n$ and $m$ ($1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^5$) — the number of vertices and the number of edges, respectively. Next $m$ lines describe edges: $i$-th line contains two integers $u_i$, $ v_i$ ($1 \le u_i, v_i \le n; u_i \neq v_i$) — indices of vertices connected by $i$-th edge.

It is guaranteed that $\sum\limits_{i=1}^{t} n \le 3 \cdot 10^5$ and $\sum\limits_{i=1}^{t} m \le 3 \cdot 10^5$.


-----Output-----

For each test print one line, containing one integer — the number of possible ways to write numbers $1$, $2$, $3$ on the vertices of given graph so it becomes beautiful. Since answers may be large, print them modulo $998244353$.


-----Example-----
Input
2
2 1
1 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output
4
0



-----Note-----

Possible ways to distribute numbers in the first test:   the vertex $1$ should contain $1$, and $2$ should contain $2$;  the vertex $1$ should contain $3$, and $2$ should contain $2$;  the vertex $1$ should contain $2$, and $2$ should contain $1$;  the vertex $1$ should contain $2$, and $2$ should contain $3$. 

In the second test there is no way to distribute numbers.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal


Solutions:
import sys
from collections import defaultdict, deque
mod = 998244353

def get(graph):
	vis = defaultdict(int)
	l = []
	for i in range(1, n + 1):
		if vis[i] == 0:
			vis[i] = 1
			q = deque()
			q.append(i)
			even = 0
			odd = 0
			while q:
				a = q.popleft()
				if vis[a] & 1:
					odd += 1
				else:
					even += 1
				for x in graph[a]:
					if vis[x] == 0:
						if vis[a] == 1:
							vis[x] = 2
						else:
							vis[x] = 1
						q.append(x)
					elif vis[x] == vis[a]:
						return 0
			l.append([even, odd])
	m = len(l)
	x = pow(2, l[0][0], mod)
	y = pow(2, l[0][1], mod)
	ans = (x + y) % mod
	for i in range(1, m):
		x = pow(2, l[i][0], mod)
		y = pow(2, l[i][1], mod)
		z = (x + y) % mod
		ans = ans * z
		ans %= mod
	return ans % mod
	return False
t = int(sys.stdin.readline())
for _ in range(t):
	graph = defaultdict(list)
	(n, m) = list(map(int, sys.stdin.readline().split()))
	for i in range(m):
		(u, v) = list(map(int, sys.stdin.readline().split()))
		graph[u].append(v)
		graph[v].append(u)
	z = get(graph)
	print(z)


from collections import deque
from sys import stdin, stdout
input = stdin.readline
print = stdout.write
anss = []
t = int(input())
for test_count in range(t):
	ans = 1
	part = 0
	factor = 0
	queue = deque([])
	(n, m) = map(int, input().split())
	if m > n // 2 * (n // 2 + 1):
		anss.append(0)
		for edge_count in range(m):
			input()
		continue
	edge = [[] for i in range(n + 1)]
	flag = [-1] * (n + 1)
	assure = 1
	for edge_count in range(m):
		(u, v) = map(int, input().split())
		edge[u].append(v)
		edge[v].append(u)
	flag[1] = 0
	queue.append(1)
	break_all = False
	while not break_all:
		(even, odd) = (1, 0)
		while queue and (not break_all):
			search = queue.popleft()
			current = flag[search]
			for to in edge[search]:
				if flag[to] == -1:
					flag[to] = current ^ 1
					if flag[to] & 1:
						odd += 1
					else:
						even += 1
					queue.append(to)
				elif flag[to] == current:
					break_all = True
				else:
					assert flag[to] == current ^ 1
		if break_all:
			ans = 0
		elif (even, odd) == (1, 0):
			factor += 1
		else:
			ans *= pow(2, even, 998244353) + pow(2, odd, 998244353)
			ans %= 998244353
		while assure <= n:
			if flag[assure] == -1:
				part += 1
				flag[assure] = 2 * part
				queue.append(assure)
				break
			assure += 1
		if assure == n + 1:
			break
	ans *= pow(3, factor, 998244353)
	ans %= 998244353
	anss.append(ans)
print('\n'.join(map(str, anss)))


import sys, threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 25)

def main():
	mod = 998244353

	def ain():
		return list(map(int, sin().split()))

	def sin():
		return sys.stdin.readline().strip()

	def dfs(x):
		if p[x] == 0:
			p[x] = 1
			pt[0] += 1
			for i in de[x]:
				if t[x] == 1:
					if t[i] == 1:
						s[0] = 0
						return
					elif p[i] != 1:
						t[i] = 2
						dfs(i)
				elif t[i] == 2:
					s[0] = 0
					return
				elif p[i] != 1:
					t[i] = 1
					r[0] += 1
					dfs(i)
	h = []
	pow1 = [1]
	s = 1
	for i in range(300000):
		s = s * 2 % mod
		pow1.append(s)
	for _ in range(int(input())):
		(n, m) = ain()
		de = [[] for i in range(n)]
		for i in range(m):
			(x, y) = ain()
			de[x - 1].append(y - 1)
			de[y - 1].append(x - 1)
		p = [0] * n
		s1 = 1
		t = [0] * n
		for i in range(n):
			if p[i] == 0:
				s = [1]
				pt = [0]
				t[i] = 1
				r = [1]
				dfs(i)
				if s[0] == 1:
					r1 = pt[0] - r[0]
					r2 = r[0]
					r1 = (pow1[r1] + pow1[r2]) % mod
					s1 = s1 * r1 % mod
				else:
					s1 = 0
					break
		h.append(str(s1))
	sys.stdout.write('\n'.join(h))
threading.Thread(target=main).start()


mod = 998244353
import sys
input = sys.stdin.readline
from collections import deque
from collections import Counter

def calc(s, a):
	return (pow(2, s, mod) + pow(2, a - s, mod)) % mod

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
testcase = int(input())
for test in range(testcase):
	(n, m) = list(map(int, input().split()))
	EDGE = [list(map(int, input().split())) for i in range(m)]
	EDGELIST = [[] for j in range(n + 1)]
	ANS = 1
	Group = [j for j in range(n + 1)]
	for (a, b) in EDGE:
		Union(a, b)
		EDGELIST[a].append(b)
		EDGELIST[b].append(a)
	testing = [None] * (n + 1)
	flag = 1
	for i in range(1, n + 1):
		if testing[i] != None:
			continue
		score = 1
		allscore = 1
		testing[i] = 1
		QUE = deque([i])
		while QUE:
			x = QUE.pop()
			for to in EDGELIST[x]:
				if testing[to] == -testing[x]:
					continue
				if testing[to] == testing[x]:
					flag = 0
					break
				testing[to] = -testing[x]
				if testing[to] == 1:
					score += 1
				allscore += 1
				QUE.append(to)
			if flag == 0:
				break
		if flag == 0:
			break
		ANS = ANS * calc(score, allscore) % mod
	if flag == 0:
		print(0)
		continue
	print(ANS)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
from heapq import *
mod = 998244353
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():

	def dfs(x):
		visited[x] = 1
		stack = [x]
		color[x] = 0
		val = [0, 0]
		while stack:
			a = stack.pop()
			val[color[a]] += 1
			for i in d[a]:
				if visited[i]:
					if color[i] == color[a]:
						return 0
				else:
					color[i] = color[a] ^ 1
					visited[i] = 1
					stack.append(i)
		ans = 0
		for i in val:
			ans += pow(2, i, mod)
			ans %= mod
		return ans
	(n, m) = mp()
	d = defaultdict(list)
	for i in range(m):
		(a, b) = mp()
		d[a].append(b)
		d[b].append(a)
	visited = defaultdict(int)
	ans = 1
	color = defaultdict(lambda : -1)
	for i in range(1, n + 1):
		if not visited[i]:
			cur = dfs(i)
			if cur == 0:
				pr(0)
				return
			ans *= cur
			ans %= mod
	pr(ans)
for _ in range(inp()):
	solve()


from collections import defaultdict
import sys
input = sys.stdin.readline
graph = defaultdict(list)
color = [0] * (3 * 10 ** 5 + 1000)
bipertite = True
MOD = 998244353
result = 1
color_count = [0] * 2
pow_value = []
t = int(input())
pow_value.append(1)
for i in range(1, 3 * 10 ** 5 + 1000):
	next_value = pow_value[i - 1] * 2 % MOD
	pow_value.append(next_value)
while t:
	(n, m) = map(int, input().split())
	if m == 0:
		print(pow(3, n, MOD))
		t -= 1
		continue
	graph.clear()
	bipertite = True
	result = 1
	for node in range(0, n + 1):
		color[node] = -1
	while m:
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
		m -= 1
	for i in range(1, n + 1):
		if color[i] != -1:
			continue
		bipertite = True
		color_count[0] = color_count[1] = 0
		queue = []
		queue.append(i)
		color[i] = 0
		color_count[0] += 1
		while queue:
			if bipertite == False:
				break
			front_node = queue.pop()
			for child_node in range(0, len(graph[front_node])):
				if color[graph[front_node][child_node]] == -1:
					color[graph[front_node][child_node]] = 1 - color[front_node]
					queue.append(graph[front_node][child_node])
					color_count[color[graph[front_node][child_node]]] += 1
				elif color[front_node] == color[graph[front_node][child_node]]:
					bipertite = False
					break
		if bipertite == False:
			print(0)
			break
		current = (pow_value[color_count[0]] + pow_value[color_count[1]]) % MOD
		result = result * current % MOD
	if bipertite:
		print(result)
	t -= 1


from sys import stdin, stdout
import cProfile, math
from collections import Counter
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10000000)

class Operation:

	def __init__(self, name, function, function_on_equal, neutral_value=0):
		self.name = name
		self.f = function
		self.f_on_equal = function_on_equal

def add_multiple(x, count):
	return x * count

def min_multiple(x, count):
	return x

def max_multiple(x, count):
	return x
sum_operation = Operation('sum', sum, add_multiple, 0)
min_operation = Operation('min', min, min_multiple, 1000000000.0)
max_operation = Operation('max', max, max_multiple, -1000000000.0)

class SegmentTree:

	def __init__(self, array, operations=[sum_operation, min_operation, max_operation]):
		self.array = array
		if type(operations) != list:
			raise TypeError('operations must be a list')
		self.operations = {}
		for op in operations:
			self.operations[op.name] = op
		self.root = SegmentTreeNode(0, len(array) - 1, self)

	def query(self, start, end, operation_name):
		if self.operations.get(operation_name) == None:
			raise Exception('This operation is not available')
		return self.root._query(start, end, self.operations[operation_name])

	def summary(self):
		return self.root.values

	def update(self, position, value):
		self.root._update(position, value)

	def update_range(self, start, end, value):
		self.root._update_range(start, end, value)

	def __repr__(self):
		return self.root.__repr__()

class SegmentTreeNode:

	def __init__(self, start, end, segment_tree):
		self.range = (start, end)
		self.parent_tree = segment_tree
		self.range_value = None
		self.values = {}
		self.left = None
		self.right = None
		if start == end:
			self._sync()
			return
		self.left = SegmentTreeNode(start, start + (end - start) // 2, segment_tree)
		self.right = SegmentTreeNode(start + (end - start) // 2 + 1, end, segment_tree)
		self._sync()

	def _query(self, start, end, operation):
		if end < self.range[0] or start > self.range[1]:
			return None
		if start <= self.range[0] and self.range[1] <= end:
			return self.values[operation.name]
		self._push()
		left_res = self.left._query(start, end, operation) if self.left else None
		right_res = self.right._query(start, end, operation) if self.right else None
		if left_res is None:
			return right_res
		if right_res is None:
			return left_res
		return operation.f([left_res, right_res])

	def _update(self, position, value):
		if position < self.range[0] or position > self.range[1]:
			return
		if position == self.range[0] and self.range[1] == position:
			self.parent_tree.array[position] = value
			self._sync()
			return
		self._push()
		self.left._update(position, value)
		self.right._update(position, value)
		self._sync()

	def _update_range(self, start, end, value):
		if end < self.range[0] or start > self.range[1]:
			return
		if start <= self.range[0] and self.range[1] <= end:
			self.range_value = value
			self._sync()
			return
		self._push()
		self.left._update_range(start, end, value)
		self.right._update_range(start, end, value)
		self._sync()

	def _sync(self):
		if self.range[0] == self.range[1]:
			for op in self.parent_tree.operations.values():
				current_value = self.parent_tree.array[self.range[0]]
				if self.range_value is not None:
					current_value = self.range_value
				self.values[op.name] = op.f([current_value])
		else:
			for op in self.parent_tree.operations.values():
				result = op.f([self.left.values[op.name], self.right.values[op.name]])
				if self.range_value is not None:
					bound_length = self.range[1] - self.range[0] + 1
					result = op.f_on_equal(self.range_value, bound_length)
				self.values[op.name] = result

	def _push(self):
		if self.range_value is None:
			return
		if self.left:
			self.left.range_value = self.range_value
			self.right.range_value = self.range_value
			self.left._sync()
			self.right._sync()
			self.range_value = None

	def __repr__(self):
		ans = '({}, {}): {}\n'.format(self.range[0], self.range[1], self.values)
		if self.left:
			ans += self.left.__repr__()
		if self.right:
			ans += self.right.__repr__()
		return ans

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def primeFactors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def isprime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def test_print(*args):
	if testingMode:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	nonlocal memory
	memory = dict()

def cached_fn(fn, *args):
	nonlocal memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result
TestCases = True
testingMode = False
optimiseForReccursion = False

def main():
	(n, m) = get_tuple()
	P = 998244353
	neighbours = [[] for _ in range(n)]
	for i in range(m):
		(a, b) = get_tuple()
		neighbours[a - 1].append(b - 1)
		neighbours[b - 1].append(a - 1)
	nature = [0 for _ in range(n)]
	res = 1
	for k in range(0, n):
		if nature[k] != 0:
			continue
		curr_level = [k]
		nature[k] = 1
		(r1, r2) = (2, 1)
		while len(curr_level) > 0:
			next_level = []
			for curr_level_vertex in curr_level:
				curr_nature = nature[curr_level_vertex]
				for v in neighbours[curr_level_vertex]:
					if nature[v] == 0:
						next_level.append(v)
						nature[v] = 1 if curr_nature == 2 else 2
						if nature[v] == 1:
							r1 = r1 * 2 % P
						else:
							r2 = r2 * 2 % P
					elif nature[v] == curr_nature:
						print(0)
						return
			curr_level = next_level
		res = res * (r1 + r2) % P % P
	(r1, r2) = (1, 1)
	print(res)
if TestCases:
	for _ in range(get_int()):
		cProfile.run('main()') if testingMode else main()
else:
	(cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mod = 998244353
pow_2 = [1 for i in range(4 * 10 ** 5)]
for i in range(1, 4 * 10 ** 5):
	pow_2[i] = pow_2[i - 1] * 2 % mod
ans = []
for _ in range(int(input())):
	mod = 998244353
	(n, m) = mi()
	edge = [[] for i in range(n)]
	for i in range(m):
		(a, b) = mi()
		edge[a - 1].append(b - 1)
		edge[b - 1].append(a - 1)
	res = 1
	cond = [-1 for i in range(n)]
	for root in range(n):
		if cond[root] == -1:
			cond[root] = 0
			color = [1, 0]
			stack = [root]
			while stack:
				v = stack.pop()
				for nv in edge[v]:
					if cond[nv] == -1:
						cond[nv] = 1 - cond[v]
						color[cond[nv]] += 1
						stack.append(nv)
					elif cond[nv] != 1 - cond[v]:
						res = 0
			way = (pow_2[color[0]] + pow_2[color[1]]) % mod
			res = res * way % mod
	ans.append(res)
print(*ans, sep='\n')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
import bisect
mod = 998244353
from collections import Counter
import bisect
from heapq import *
from collections import defaultdict
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 998244353

def power(base, exp):
	base %= mod
	if exp < 3:
		return base ** exp % mod
	half = power(base * base, exp // 2)
	return half * base % mod if exp % 2 == 1 else half % mod

def solve():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	(count, visited) = ([0, 0], [-1 for _ in range(n + 1)])
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	(possible, ans) = (True, 1)

	@bootstrap
	def dfs(node, par, parity):
		nonlocal possible, visited, graph, count
		if visited[node] != -1:
			possible = False if visited[node] != parity else possible
			yield None
		visited[node] = parity
		count[parity] += 1
		for child in graph[node]:
			if child != par:
				yield dfs(child, node, 1 - parity)
		yield
	for i in range(1, n + 1):
		if visited[i] == -1:
			count = [0, 0]
			dfs(i, -1, 1)
			ans *= (power(2, count[0]) + power(2, count[1])) % mod
			ans %= mod
	sys.stdout.write(str(ans) if possible else '0')
	sys.stdout.write('\n')

def main():
	tests = 1
	tests = int(input().strip())
	for test in range(tests):
		solve()
main()


from sys import stdin, stdout
from collections import defaultdict
import sys, threading
sys.setrecursionlimit(10 ** 5)
threading.stack_size(2 ** 25)

def main():

	def power(x, p):
		re = 1
		mode = 998244353
		while p:
			if p & 1:
				re = re * x % mode
			x = x * x % mode
			p >>= 1
		return re

	def dfs(node, col):
		visited[node] = True
		c[col] += 1
		color[node] = col
		for j in dic[node]:
			if not visited[j]:
				if not dfs(j, col ^ 1):
					return False
			elif color[j] == color[node]:
				return False
		return True
	t = int(stdin.readline())
	for _ in range(t):
		mod = 998244353
		(n, m) = list(map(int, stdin.readline().split()))
		dic = defaultdict(list)
		for i in range(m):
			(u, v) = list(map(int, stdin.readline().split()))
			dic[u].append(v)
			dic[v].append(u)
		visited = [False] * (n + 1)
		color = [-1] * (n + 1)
		c = [0] * 2
		result = 1
		flag = 0
		for i in range(1, n + 1):
			if not visited[i]:
				res = dfs(i, 0)
				if not res:
					flag = 1
					break
				else:
					result = result * (power(2, c[0]) + power(2, c[1])) % mod
					c[0] = 0
					c[1] = 0
		if flag == 1:
			stdout.write('0\n')
		else:
			stdout.write(str(result) + '\n')
threading.Thread(target=main).start()


from __future__ import division, print_function
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 998244353

def power(base, exp):
	base %= mod
	if exp < 3:
		return base ** exp % mod
	half = power(base * base, exp // 2)
	return half * base % mod if exp % 2 == 1 else half % mod

def solve():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	(count, visited) = ([0, 0], [-1 for _ in range(n + 1)])
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	(possible, ans) = (True, 1)

	@bootstrap
	def dfs(node, par, parity):
		nonlocal possible, visited, graph, count
		if visited[node] != -1:
			possible = False if visited[node] != parity else possible
			yield None
		visited[node] = parity
		count[parity] += 1
		for child in graph[node]:
			if child != par:
				yield dfs(child, node, 1 - parity)
		yield
	for i in range(1, n + 1):
		if visited[i] == -1:
			count = [0, 0]
			dfs(i, -1, 1)
			ans *= (power(2, count[0]) + power(2, count[1])) % mod
			ans %= mod
	sys.stdout.write(str(ans) if possible else '0')
	sys.stdout.write('\n')

def main():
	tests = 1
	tests = int(input().strip())
	for test in range(tests):
		solve()
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


mod = 998244353
from collections import deque
from sys import stdin, stdout
for _ in range(int(input())):
	(n, m) = list(map(int, stdin.readline().split()))
	a = [[] for i in range(n + 1)]
	length = [0] * (n + 1)
	if m == 0:
		print(pow(3, n, mod))
	else:
		d = []
		ans1 = 0
		ans2 = 0
		ans3 = 0
		for __ in range(m):
			(x, y) = list(map(int, stdin.readline().split()))
			a[x].append(y)
			a[y].append(x)
		col = [0] * (n + 1)
		de = deque([])
		for j in range(1, n + 1):
			if len(a[j]) == 0:
				ans3 += 1
			elif col[j] == 0:
				col[j] = 1
				de.append(j)
			c = 1
			c1 = 1
			while len(de):
				p = de.popleft()
				for i in a[p]:
					if col[i] == 0:
						col[i] = -col[p]
						de.append(i)
						if col[i] == 1:
							c1 += 1
						c += 1
			d.append([c, c1])
		flag = 0
		for i in range(1, n + 1):
			if flag == 1:
				break
			for j in a[i]:
				if col[i] == col[j]:
					flag = 1
					break
		k = 1
		if flag == 1:
			stdout.write(str(0) + '\n')
		else:
			for i in d:
				if i[0] != 1:
					k1 = pow(2, i[1], mod)
					k1 += pow(2, i[0] - i[1], mod)
					k *= k1
			k *= pow(3, ans3, mod)
			k %= mod
			stdout.write(str(k) + '\n')


from collections import deque
from sys import stdin, stdout
input = stdin.readline
saida = []
t = int(input())
modulo = 998244353
for _ in range(t):
	ans = 1
	part = 0
	factor = 0
	fila = deque([])
	(n, m) = map(int, input().split())
	if m > n // 2 * (n // 2 + 1):
		saida.append('0')
		for edge_count in range(m):
			input()
		continue
	edge = [[] for i in range(n + 1)]
	visitados = [-1] * (n + 1)
	assure = 1
	for arestas in range(m):
		(u, v) = map(int, input().split())
		edge[u].append(v)
		edge[v].append(u)
	visitados[1] = 0
	fila.append(1)
	break_all = False
	while not break_all:
		(par, impar) = (1, 0)
		while fila and (not break_all):
			search = fila.popleft()
			current = visitados[search]
			for i in edge[search]:
				if visitados[i] == -1:
					visitados[i] = current ^ 1
					if visitados[i] & 1:
						impar += 1
					else:
						par += 1
					fila.append(i)
				elif visitados[i] == current:
					break_all = True
				else:
					assert visitados[i] == current ^ 1
		if break_all:
			ans = 0
		elif (par, impar) == (1, 0):
			factor += 1
		else:
			ans *= pow(2, par, modulo) + pow(2, impar, modulo)
			ans %= modulo
		while assure <= n:
			if visitados[assure] == -1:
				part += 1
				visitados[assure] = 2 * part
				fila.append(assure)
				break
			assure += 1
		if assure == n + 1:
			break
	ans *= pow(3, factor, modulo)
	ans %= modulo
	saida.append(str(ans))
print('\n'.join(saida))


from sys import stdin, stdout
for _ in range(int(input())):
	(n, m) = (int(x) for x in stdin.readline().split())
	a = [[] for i in range(n + 1)]
	b = []
	for i in range(m):
		(c, d) = (int(x) for x in stdin.readline().split())
		a[d].append(c)
		a[c].append(d)
		b.append([c, d])
	vis = [0] * (n + 1)
	co = []
	for i in range(1, n + 1):
		if vis[i] == 0:
			st = [i]
			vis[i] = 'e'
			e = 1
			o = 0
			while st:
				x = st.pop()
				for i in a[x]:
					if vis[i] == 0:
						if vis[x] == 'e':
							vis[i] = 'o'
							o += 1
						else:
							vis[i] = 'e'
							e += 1
						st.append(i)
			co.append([e, o])
	fl = 0
	for i in b:
		if vis[i[0]] == vis[i[1]]:
			stdout.write(str(0) + '\n')
			fl = 1
			break
	if fl == 0:
		k = []
		for i in range(len(co)):
			x = co[i][0]
			y = co[i][1]
			m = 1
			for i in range(x):
				m *= 2
				m %= 998244353
			ans = m
			m = 1
			for i in range(y):
				m *= 2
				m %= 998244353
			ans += m
			k.append(ans % 998244353)
		ans = 1
		for i in k:
			ans *= i
			ans %= 998244353
		stdout.write(str(ans) + '\n')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dic = {}
	for i in range(m):
		(x, y) = map(int, input().split())
		if x in dic:
			dic[x].append(y)
		else:
			dic[x] = [y]
		if y in dic:
			dic[y].append(x)
		else:
			dic[y] = [x]
	alone = 0
	for i in range(1, n + 1):
		if not i in dic:
			alone += 1
	over = set({})
	ans = []
	flag = True
	check = {}
	for i in dic:
		odd = 0
		even = 1
		count = 1
		if not i in over:
			over.add(i)
			fir = [i]
			se = {i}
			check[i] = 0
			while fir:
				tem = []
				for j in fir:
					xx = dic[j]
					for k in xx:
						if k in se:
							if check[k] % 2 != count % 2:
								flag = False
						else:
							se.add(k)
							over.add(k)
							tem.append(k)
							if count % 2 == 0:
								even += 1
							else:
								odd += 1
							check[k] = count
				count += 1
				fir = tem.copy()
			ans.append([odd, even])
	if not flag:
		print(0)
	else:
		rem = 998244353
		main = 3 ** alone % rem
		for i in ans:
			main *= (2 ** i[0] + 2 ** i[1]) % rem
			main %= rem
		print(main)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
for ik in range(int(input())):
	(n, m) = map(int, input().split())
	graph = defaultdict(list)
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
	if m == 0:
		print(pow(3, n, mod1))
		continue
	e = [0]
	visited = [False for i in range(n)]
	re = [-1] * n

	def DFS(s, rem):
		cou = 0
		stack = []
		stack.append((s, rem))
		while len(stack):
			(s, rem) = stack[-1]
			if re[s] == -1:
				if rem == 1:
					e[0] += 1
				re[s] = rem
			elif re[s] != rem:
				e[0] = -10000
				return -1
			stack.pop()
			if not visited[s]:
				cou += 1
				visited[s] = True
			for node in graph[s]:
				if not visited[node]:
					stack.append((node, (rem + 1) % 2))
				elif re[node] != (rem + 1) % 2:
					e[0] = -10000
					return -1
		return cou
	f = 0
	ans = 1
	for i in range(n):
		if visited[i] == False:
			e[0] = 0
			cr = DFS(i, 0)
			if e[0] < 0 or cr < 0 or cr < e[0]:
				f = 1
				print(0)
				break
			else:
				ans *= pow(2, e[0], mod1) + pow(2, cr - e[0], mod1)
				ans %= mod1
	if f == 0:
		print(ans)


M = 998244353
t = int(input())
(n, m) = (0, 0)
g = []
v = []

def dfs(r):
	s = [r]
	v[r] = 1
	c = [0, 1]
	while s:
		x = s.pop()
		for j in g[x]:
			if v[j] == v[x]:
				return 0
			if v[j] == -1:
				v[j] = v[x] ^ 1
				c[v[j]] += 1
				s.append(j)
	if c[0] == 0 or c[1] == 0:
		return 3
	return (2 ** c[0] % M + 2 ** c[1] % M) % M
o = []
for i in range(t):
	(n, m) = map(int, input().split())
	g = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		g[a - 1].append(b - 1)
		g[b - 1].append(a - 1)
	v = [-1] * n
	ox = 1
	for j in range(n):
		if v[j] == -1:
			ox = ox * dfs(j) % M
	o.append(ox)
print('\n'.join(map(str, o)))


from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
mod = 998244353

def bfs(node, v, p):
	ans = 1
	q = deque()
	q.append(node)
	v[node] = 1
	(a, b) = (0, 0)
	while q:
		i = q.popleft()
		if p[i] == 1:
			a = a + 1
		else:
			b = b + 1
		for j in d[i]:
			if v[j] == 0:
				v[j] = 1
				v[j] = 1
				q.append(j)
				p[j] = 1 if p[i] == 0 else 0
			elif p[j] == p[i]:
				return 0
	return (2 ** a + 2 ** b) % mod
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	d = defaultdict(list)
	p = {}
	for i in range(m):
		(x, y) = map(int, input().split())
		d[x].append(y)
		d[y].append(x)
	v = [0] * (n + 1)
	ans = 1
	for i in d:
		if v[i] == 0:
			p[i] = 1
			f = bfs(i, v, p)
			ans = ans * f % mod
	for i in range(1, n + 1):
		if v[i] == 0:
			ans = ans * 3 % mod
	print(ans % mod)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque

def bfs(x):
	global a
	q = deque([])
	v[x] = 1
	q.append(x)
	c1 = 1
	c2 = 2
	ans[x][0] = 1
	ans[x][1] = 2
	mo = 998244353
	while len(q):
		cur = q.popleft()
		for i in adj[cur]:
			if not v[i]:
				v[i] = 1
				d[i] = d[cur] + 1
				if d[i] % 2 == 0:
					c2 *= 2
					c2 %= mo
				else:
					c1 *= 2
					c1 %= mo
				q.append(i)
	return (c1 + c2) % mo
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	v = [0] * (n + 1)
	d = [0] * (n + 1)
	l = []
	adj = [[] for j in range(n + 1)]
	ans = [[0, 0] for j in range(n + 1)]
	for j in range(m):
		(x, y) = map(int, input().split())
		l.append([x, y])
		adj[x].append(y)
		adj[y].append(x)
	a = True
	an = 1
	for j in range(1, n + 1):
		if not v[j]:
			if len(adj[j]) == 0:
				an *= 3
				an %= 998244353
			else:
				an *= bfs(j)
				an %= 998244353
	for j in l:
		if d[j[0]] == d[j[1]]:
			a = False
			break
	if a == False:
		print(0)
	else:
		print(an)


import sys
import io, os
input = sys.stdin.buffer.readline
mod = 998244353
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	g = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		g[u].append(v)
		g[v].append(u)
	color = [-1] * n
	visit = [-1] * n
	group = [-1] * n
	cur = 0
	flag = True
	for i in range(n):
		if visit[i] != -1:
			continue
		s = []
		s.append((i, 0))
		color[i] = 0
		visit[i] = 0
		group[i] = cur
		while s:
			(v, c) = s.pop()
			for u in g[v]:
				if color[u] == c:
					flag = False
					break
				if visit[u] == -1:
					color[u] = 1 - c
					visit[u] = 0
					group[u] = cur
					s.append((u, 1 - c))
		cur += 1
	if not flag:
		print(0)
		continue
	C = [[0, 0] for i in range(max(group) + 1)]
	for (i, c) in enumerate(color):
		C[group[i]][c] += 1
	ans = 1
	for (c0, c1) in C:
		temp = pow(1, c0, mod) * pow(2, c1, mod)
		temp += pow(2, c0, mod) * pow(1, c1, mod)
		temp %= mod
		ans *= temp
		ans %= mod
	print(ans)


import sys
input = sys.stdin.readline
from collections import deque

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		if rx == ry:
			return False
		if self.rank[rx] < self.rank[ry]:
			(rx, ry) = (ry, rx)
		self.par[rx] += self.par[ry]
		self.par[ry] = rx
		if self.rank[rx] == self.rank[ry]:
			self.rank[rx] += 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]

def bfs(s):
	q = deque([s])
	color[s] = 1
	(b, w) = (1, 0)
	while q:
		v = q.popleft()
		for nv in adj_list[v]:
			if color[nv] == 0:
				color[nv] = -color[v]
				q.append(nv)
				if color[nv] == 1:
					b += 1
				else:
					w += 1
			elif color[nv] == color[v]:
				return (-1, -1)
	return (b, w)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	adj_list = [[] for _ in range(n)]
	uf = Unionfind(n)
	MOD = 998244353
	for _ in range(m):
		(u, v) = map(int, input().split())
		adj_list[u - 1].append(v - 1)
		adj_list[v - 1].append(u - 1)
		uf.unite(u - 1, v - 1)
	roots = set((uf.root(i) for i in range(n)))
	ans = 1
	color = [0] * n
	for r in roots:
		if uf.count(r) == 1:
			ans *= 3
		else:
			(b, w) = bfs(r)
			if b == -1:
				ans = 0
				break
			else:
				ans *= pow(2, b, MOD) + pow(2, w, MOD)
		ans %= MOD
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 998244353

def graph_undirected():
	(n, e) = [int(x) for x in input().split()]
	graph = {}
	for i in range(e):
		(vertex, neighbour) = [int(x) for x in input().split()]
		if vertex in graph:
			graph[vertex].append(neighbour)
		else:
			graph[vertex] = [neighbour]
		if neighbour in graph:
			graph[neighbour].append(vertex)
		else:
			graph[neighbour] = [vertex]
	return (graph, n)
from collections import deque

def cycle_bfs(graph, n, node):
	q = deque([node])
	color[node] = 0
	while q:
		currnode = q.popleft()
		visited[currnode] = True
		a[color[currnode]] += 1
		if color[currnode] == 0:
			currcolor = 1
		else:
			currcolor = 0
		if currnode in graph:
			for neighbour in graph[currnode]:
				if visited[neighbour] == False:
					visited[neighbour] = True
					color[neighbour] = currcolor
					q.append(neighbour)
				elif color[neighbour] != currcolor:
					return False
	return True
k = 3 * 10 ** 5 + 10
pow2 = [1 for x in range(k)]
pow3 = [1 for x in range(k)]
for i in range(1, k):
	pow2[i] = pow2[i - 1] * 2
	pow3[i] = pow3[i - 1] * 3
	pow2[i] %= mod
	pow3[i] %= mod
t = int(input())
while t:
	t -= 1
	(graph, n) = graph_undirected()
	c = 0
	for i in range(1, n + 1):
		if i not in graph:
			c += 1
	visited = [False for x in range(n + 1)]
	color = [None for x in range(n + 1)]
	res = 1
	a = [0, 0]
	for i in range(1, n + 1):
		if visited[i] == False and i in graph:
			a = [0, 0]
			ans = cycle_bfs(graph, n, i)
			if ans:
				res *= (pow2[a[0]] + pow2[a[1]]) % mod
				res %= mod
			else:
				res = 0
				break
	res *= pow3[c] % mod
	sys.stdout.write(str(res % mod) + '\n')


import sys, collections
input = sys.stdin.readline
mod = 998244353
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	g = [[] for i in range(n)]
	for i in range(m):
		(a, b) = [int(x) for x in input().split()]
		g[a - 1].append(b - 1)
		g[b - 1].append(a - 1)
	v = set()
	ans = 1
	for i in range(n):
		if i in v:
			continue
		v.add(i)
		q = collections.deque([])
		q.append(i)
		f = True
		(odd, even) = (set(), set())
		even.add(i)
		while q:
			now = q.popleft()
			if now in even:
				curr = 'even'
			else:
				curr = 'odd'
			for i in g[now]:
				if curr == 'even' and i in even:
					f = False
					break
				if curr == 'odd' and i in odd:
					f = False
					break
				if i in even or i in odd:
					continue
				if curr == 'even':
					v.add(i)
					q.append(i)
					odd.add(i)
				else:
					v.add(i)
					q.append(i)
					even.add(i)
		if f == False:
			ans = 0
			break
		else:
			ans *= 2 ** len(odd) + 2 ** len(even)
			ans = ans % mod
	print(ans % mod)


import sys
input = sys.stdin.readline
from collections import deque
mod = 998244353
t = int(input())

def isbip2(i, vis, col, f):
	q = deque()
	q.append(i)
	vis[i] = 1
	col[i] = 0
	f[0] += 1
	while len(q) > 0:
		z = q.popleft()
		for j in a[z]:
			if col[z] == col[j]:
				return 0
			if vis[j] == 0:
				vis[j] = 1
				col[j] = col[z] ^ 1
				f[col[j]] += 1
				q.append(j)
	return 1

def isbip(col, vis, n):
	c = 1
	z = 0
	o = 0
	f = [0, 0]
	for i in range(1, n + 1):
		if vis[i]:
			continue
		if not isbip2(i, vis, col, f):
			return 0
		c = c % mod * (pow(2, f[0] - z, mod) + pow(2, f[1] - o, mod)) % mod
		z = f[0]
		o = f[1]
	return c
while t > 0:
	t -= 1
	(n, m) = list(map(int, input().split()))
	col = [-1 for i in range(n + 1)]
	a = [[] for i in range(n + 1)]
	vis = [0 for i in range(n + 1)]
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		a[x].append(y)
		a[y].append(x)
	print(isbip(col, vis, n))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict

def dfs(node):
	vis[node] = 1
	colour[node] = 0
	arr[0] += 1
	stack = [node]
	while stack:
		cur = stack.pop()
		for j in edge[cur]:
			if vis[j] == 0:
				stack.append(j)
				colour[j] = colour[cur] ^ 1
				vis[j] = 1
				arr[colour[j]] += 1
			elif colour[cur] == colour[j]:
				return False
	return True
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	edge = defaultdict(list)
	z = 998244353
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		edge[u].append(v)
		edge[v].append(u)
	ans = 1
	s = 0
	vis = [0] * (n + 1)
	colour = [0] * (n + 1)
	for i in range(1, n + 1):
		if vis[i] == 0:
			arr = [0, 0]
			if dfs(i):
				a = 1
				b = 1
				for j in range(arr[0]):
					a *= 2
					a %= z
				for j in range(arr[1]):
					b *= 2
					b %= z
				ans *= a + b
				ans %= z
			else:
				s += 1
				break
	if s == 1:
		print(0)
	else:
		print(ans)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left

def dfs(x):
	stack = [[x, 1]]
	(a, b) = (0, 0)
	while stack:
		(x, v) = stack.pop()
		if visited[x] == 0:
			if v == 1:
				a += 1
				t = 2
			else:
				b += 1
				t = 1
			visited[x] = v
			for i in graph[x]:
				if visited[i] == 0:
					stack.append([i, t])
					graph[i].remove(x)
	return (a, b)

def check(x):
	stack = [x]
	s = set()
	while stack:
		x = stack.pop()
		s.add(x)
		for i in graph[x]:
			if i not in s:
				stack.append(i)
			if (visited[x] + visited[i]) % 2 == 0:
				return 0
	return 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = {i: set() for i in range(n)}
	visited = [0 for i in range(n)]
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a - 1].add(b - 1)
		graph[b - 1].add(a - 1)
	f = 1
	mod = 998244353
	count = 1
	for i in range(n):
		if visited[i] == 0 and len(graph[i]) != 0:
			(a, b) = dfs(i)
			f = check(i)
			if f == 0:
				print(0)
				break
			else:
				count = count * (pow(2, a, mod) + pow(2, b, mod)) % mod
	if f == 1:
		print(count * pow(3, visited.count(0), mod) % mod)