D. Красивый граф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный невзвешенный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер.

В каждую вершину графа вы должны записать одно из следующих чисел: $$$1$$$, $$$2$$$ и $$$3$$$. Граф станет красивым, если для каждого ребра сумма чисел, записанных на соединяемых этим ребром вершинах, будет нечетной.

Посчитайте количество способов расставить во все вершины числа $$$1$$$, $$$2$$$ и $$$3$$$ так, чтобы получившийся граф был красивым. Так как это количество может быть достаточно большим, выведите его по модулю $$$998244353$$$.

Обратите внимание, что в каждой вершине графа вы должны написать ровно одно число.

Гарантируется, что в заданном графе нет петель и кратных ребер.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — количество тестов, для которых нужно решить задачу.

Первая строка каждого теста содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^5$$$) — количество вершин и ребер в графе соответственно. В следующих $$$m$$$ строках содержится описание ребер: в $$$i$$$-й строке заданы два целых числа $$$u_i$$$, $$$ v_i$$$ ($$$1 \le u_i, v_i \le n; u_i \neq v_i$$$) — номера вершин, которые соединяет $$$i$$$-е ребро.

Гарантируется, что $$$\sum\limits_{i=1}^{t} n \le 3 \cdot 10^5$$$ и $$$\sum\limits_{i=1}^{t} m \le 3 \cdot 10^5$$$.

Выходные данные

Для каждого теста выведите по одной строке, в которой выведите целое число — количество способов расставить в вершины числа $$$1$$$, $$$2$$$ и $$$3$$$ так, чтобы получившийся граф был хорошим. Так как это количество может быть достаточно большим, выведите его по модулю $$$998244353$$$.

Пример
Входные данные
2
2 1
1 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Выходные данные
4
0
Примечание

В первом тестовом примере подходят четыре варианта:

  1. поставить в вершину $$$1$$$ число $$$1$$$, а в вершину $$$2$$$ — число $$$2$$$;
  2. поставить в вершину $$$1$$$ число $$$3$$$, а в вершину $$$2$$$ — число $$$2$$$;
  3. поставить в вершину $$$1$$$ число $$$2$$$, а в вершину $$$2$$$ — число $$$1$$$;
  4. поставить в вершину $$$1$$$ число $$$2$$$, а в вершину $$$2$$$ — число $$$3$$$.

Во втором тестовом примере не существует способа, удовлетворяющего описанным выше условиям.