310819: CF1893E. Cacti Symphony

E. Cacti Symphonytime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given an undirected connected graph in which any two distinct simple cycles do not have common vertices. Since the graph can be very large, it is given to you in a compressed form: for each edge, you are also given a number $d$, which indicates that there are $d$ additional vertices on this edge.

You need to assign a weight to each vertex and each edge of the graph — an integer from $1$ to $3$.

An edge of the graph is called good if the bitwise XOR of the weights of its adjacent vertices is not equal to $0$ and not equal to the weight of that edge.

Similarly, a vertex of the graph is called good if the bitwise XOR of the weights of its adjacent edges is not equal to $0$ and not equal to the weight of that vertex.

You need to determine how many ways there are to assign weights to the vertices and edges of the graph so that all vertices and edges are good. Since the answer can be quite large, you need to calculate the remainder of the answer divided by $998\,244\,353$.

Input

The first line contains two integers $n$ and $m$ — the number of vertices and the number of edges in the graph ($2 \le n \le 5 \cdot 10^5$, $n - 1 \le m \le 10^6$).

Each of the next $m$ lines contains three integers $a_i, b_i$, and $d_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $0 \le d_i \le 10^9$), indicating that there is an edge in the graph connecting vertices $a_i$ and $b_i$. Additionally, on this edge, there are $d_i$ additional vertices. It is guaranteed that the given graph is connected, there are no multiple edges, loops, and any two distinct simple cycles of the graph do not have common vertices.

Output

Output a single integer — the answer to the problem modulo $998\,244\,353$.

ExamplesInput

3 3
1 2 0
2 3 0
3 1 0

Output

12

Input

6 7
1 2 0
2 3 0
3 1 0
4 5 0
5 6 0
6 4 0
4 3 0

Output

0

Input

2 1
2 1 777

Output

0

Input

3 3
1 2 0
2 3 110850709
3 1 1000000000

Output

179179178

Note

In the first test, the graph is a simple cycle of $3$ vertices. It can be shown, that there are exactly $12$ ways to assign weights, to make all vertexes and edges good.

In the second test, the graph has the form of two simple cycles of $3$ vertices connected by an edge. It can be shown that for such a graph there are no ways to arrange weights so that all vertices and edges are good.

题目大意：
题目描述了一个无向连通图，图中的任意两个简单循环没有公共顶点。图以一种压缩形式给出，对于每条边，还给出了一个数 \( d \)，表示这条边上还有 \( d \) 个额外的顶点。需要为图的每个顶点和每条边分配一个权重，权重的整数值在 1 到 3 之间。如果一条边的两个相邻顶点的权重异或结果不等于 0 且不等于边本身的权重，则称这条边是“好的”。类似地，如果顶点的所有相邻边的权重异或结果不等于 0 且不等于顶点本身的权重，则称这个顶点是“好的”。需要计算有多少种方式可以为图的顶点和边分配权重，使得所有顶点和边都是“好的”。由于答案可能很大，需要计算答案除以 998,244,353 的余数。

输入输出数据格式：
输入：
- 第一行包含两个整数 \( n \) 和 \( m \) —— 图的顶点数和边数（\( 2 \le n \le 5 \times 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。题目大意： 题目描述了一个无向连通图，图中的任意两个简单循环没有公共顶点。图以一种压缩形式给出，对于每条边，还给出了一个数 \( d \)，表示这条边上还有 \( d \) 个额外的顶点。需要为图的每个顶点和每条边分配一个权重，权重的整数值在 1 到 3 之间。如果一条边的两个相邻顶点的权重异或结果不等于 0 且不等于边本身的权重，则称这条边是“好的”。类似地，如果顶点的所有相邻边的权重异或结果不等于 0 且不等于顶点本身的权重，则称这个顶点是“好的”。需要计算有多少种方式可以为图的顶点和边分配权重，使得所有顶点和边都是“好的”。由于答案可能很大，需要计算答案除以 998,244,353 的余数。 输入输出数据格式： 输入： - 第一行包含两个整数 \( n \) 和 \( m \) —— 图的顶点数和边数（\( 2 \le n \le 5 \times 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。