Дан неориентированный невзвешенный граф, состоящий из \(n\) вершин и \(m\) ребер.
В каждую вершину графа вы должны записать одно из следующих чисел: \(1\), \(2\) и \(3\). Граф станет красивым, если для каждого ребра сумма чисел, записанных на соединяемых этим ребром вершинах, будет нечетной.
Посчитайте количество способов расставить во все вершины числа \(1\), \(2\) и \(3\) так, чтобы получившийся граф был красивым. Так как это количество может быть достаточно большим, выведите его по модулю \(998244353\).
Обратите внимание, что в каждой вершине графа вы должны написать ровно одно число.
Гарантируется, что в заданном графе нет петель и кратных ребер.
Выходные данные
Для каждого теста выведите по одной строке, в которой выведите целое число — количество способов расставить в вершины числа \(1\), \(2\) и \(3\) так, чтобы получившийся граф был хорошим. Так как это количество может быть достаточно большим, выведите его по модулю \(998244353\).
Примечание
В первом тестовом примере подходят четыре варианта:
- поставить в вершину \(1\) число \(1\), а в вершину \(2\) — число \(2\);
- поставить в вершину \(1\) число \(3\), а в вершину \(2\) — число \(2\);
- поставить в вершину \(1\) число \(2\), а в вершину \(2\) — число \(1\);
- поставить в вершину \(1\) число \(2\), а в вершину \(2\) — число \(3\).
Во втором тестовом примере не существует способа, удовлетворяющего описанным выше условиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1
1 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
|
4
0
|