Cacti Symphony
Contest: Codeforces Round 908 (Div. 1)
Difficulty rating: 3500
Tags: combinatorics, dfs and similar, dp, graphs

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 format:
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 format:
Output a single integer — the answer to the problem modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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.

Example input:
3 3
1 2 0
2 3 0
3 1 0

Example output:
12

Example input:
6 7
1 2 0
2 3 0
3 1 0
4 5 0
5 6 0
6 4 0
4 3 0

Example output:
0

Editorial:
First observation: for each edge, the vertices connected by it have different weights, otherwise the XOR of the weights of the adjacent vertices of this edge is equal to $$$0$$$.
Second observation: for each edge, one of its adjacent vertices has a weight equal to the weight of the edge, since $$$1 \oplus 2 \oplus 3 = 0$$$.
From these two observations, it follows that each edge has the same weight as EXACTLY one of the vertices it is connected to. Let's say that a vertex controls all the adjacent edges with the same weight. Then each edge is controlled by exactly one vertex.
Third observation: if a vertex has an even degree, then the number of edges controlled by it must be odd, and this is a sufficient condition for the vertex to be good.
Fourth observation: if a vertex has an odd degree, then the number of edges controlled by it must be even, and this is a sufficient condition for the vertex to be good.
Therefore, in order for all vertices to be good, it is necessary to choose who controls each edge in such a way that the parity of the vertex degree and the parity of the number of edges controlled by it are different.
And in order for all edges to be good, it is necessary to assign weights from $$$1$$$ to $$$3$$$ to the vertices in such a way that no two adjacent vertices have the same weight. The weight of each edge will then be equal to the weight of the vertex it is controlled by.
Now the problem is divided into two independent parts: finding the number of ways to assign weights to the vertices, and finding the number of ways to orient the edges. The answer to the original problem will be the product of the answers to these two parts.
1. How many ways are there to color the vertices with $$$3$$$ colors, such that two adjacent vertices are colored differently?
2. How many ways are there to orient the edges, such that a vertex with an even degree has an odd number of outgoing edges, and a vertex with an odd degree has an even number of outgoing edges?
Solution to problem 1: note that if there is a bridge in the graph $$$G$$$, and it divides the graph into graphs $$$G1$$$ and $$$G2$$$, then the answer for $$$G$$$ is the product of the answers for $$$G1$$$ and $$$G2$$$ multiplied by $$$\frac{2}{3}$$$. Then we can identify all the bridges, and since the graph is a vertex cactus, after removing the bridges, the graph will be divided into cycle components. For a cycle of length $$$n$$$, the number of ways to color the vertices can be calculated using simple dynamic programming: $$$dp_1 = 3, dp_3 = 6, dp_4 = 18, dp_n = dp_{n - 1} + 2 \cdot dp_{n - 2}$$$. To prove this dynamic programming, consider any two vertices that are one apart in a cycle of length $$$n$$$. If they have the same color, then the vertex between them has $$$2$$$ possible colors, and the rest have $$$dp_{n-2}$$$ possibilities. If they have different colors, then there are $$$dp_{n-1}$$$ possibilities. Knowing the transition formula, we can notice that $$$dp_n = 2^n + 2 \cdot (-1)^n$$$. This formula can be trivially proved by induction.
Solution to problem 2: we will solve the same problem, but requiring that each vertex has an odd number of outgoing edges (if we invert all the edges in such a graph, we will get what is required). If $$$n$$$ and $$$m$$$ have different parity, then the answer is $$$0$$$, since the sum of $$$n$$$ odd numbers, which are the degrees of the vertices, must be equal to $$$m$$$. Otherwise, the answer is $$$2^{number of cycles}$$$. At any moment, we can remove any leaf, as it does not solve anything. We will remove the leaves as long as they exist. After this, one of the cycles in the graph will be a "leaf" - connected only to one other cycle. For all vertices of this cycle, the necessary parities of the degrees are known. Choose any edge of the cycle and orient it (there are $$$2$$$ ways to orient it, both will work). After that, all other edges in the cycle are oriented uniquely. After that, the bridge between this cycle and the other one is also uniquely oriented. Now we have one less cycle, and we also know all the necessary parities of the vertices (the parity changes for the vertex where the bridge came in). In this way, we can gradually reduce the number of cycles. With each removal of a cycle, the answer is multiplied by $$$2$$$, since there are $$$2$$$ ways to orient the edge in the cycle. In the end, we get $$$2^{number of cycles}$$$ ways.
The final answer to the problem if $$$n$$$ and $$$m$$$ have same parity is:
$$$ans = \frac{2}{3}^{number of bridges} \cdot 2^{number of cycles} \cdot (2^{c_1} + 2 \cdot (-1)^{c_1}) \cdot \ldots \cdot (2^{c_k} + 2 \cdot (-1)^{c_k})$$$ where $$$c_1, \ldots, c_k$$$ are the sizes of cycles (cycle can be a single vertice if it did not lie on any other cycle, and $$$c_i = 0$$$ in this case).