E. Симфония кактусов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Требуется назначить каждой вершине и каждому ребру графа вес — целое число от $$$1$$$ до $$$3$$$.

Ребро графа назовём хорошим, если побитовый XOR весов смежных ему вершин не равен $$$0$$$ и не равен весу этого ребра.

Аналогично вершину графа назовём хорошей, если побитовый XOR весов смежных ей рёбер не равен $$$0$$$ и не равен весу этой вершины.

Вам нужно определить, сколько существует способов назначить веса вершинам и рёбрам графа, чтобы все вершины и все рёбра были хорошими. Так как ответ может быть достаточно большим, нужно вычислить остаток от деления ответа на $$$998\,244\,353$$$.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ — количество вершин и количество рёбер в графе ($$$2 \le n \le 5 \cdot 10^5$$$, $$$n - 1 \le m \le 10^6$$$).

Каждая из следующих $$$m$$$ строк содержит три целых числа $$$a_i, b_i$$$ и $$$d_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$, $$$0 \le d_i \le 10^9$$$), означающих, что в графе существует ребро, соединяющее вершины $$$a_i$$$ и $$$b_i$$$. Также, на этом ребре, дополнительно находятся $$$d_i$$$ вершин. Гарантируется, что заданный граф является связным, в нем нет кратных рёбер, петель, а также любые два различных простых цикла графа не имеют общих вершин.

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

Выведите единственное целое число — ответ на задачу по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3 3
1 2 0
2 3 0
3 1 0
Выходные данные
12
Входные данные
6 7
1 2 0
2 3 0
3 1 0
4 5 0
5 6 0
6 4 0
4 3 0
Выходные данные
0
Входные данные
2 1
2 1 777
Выходные данные
0
Входные данные
3 3
1 2 0
2 3 110850709
3 1 1000000000
Выходные данные
179179178
Примечание

В первом тесте граф имеет вид простого цикла из $$$3$$$ вершин. Можно показать, что есть ровно $$$12$$$ способов назначить веса вершинам и рёбрам, чтобы все они были хорошими.

Во втором тесте граф имеет вид двух простых циклов из $$$3$$$ вершин, соединённых ребром. Можно показать, что для такого графа нет ни одного способа расставить веса, чтобы все вершины и рёбра были хорошими.