P7317 [COCI 2018/2019 #3] Practical

You are given an undirected graph with $N$ nodes and $M$ edges. Each edge has a weight less than $10^9$. A cycle is called a good cycle if the XOR sum of the weights of all edges on the cycle is $0$. You may perform some operations on the undirected graph. Each operation consists of the following steps: - Choose an integer $x$. - Choose a non-empty set of edges. - XOR $x$ onto the weight of every edge in this set. Make all simple cycles in the undirected graph become good cycles using as few operations as possible. Find the minimum number of operations, and output the corresponding operation parameters.

The first line contains positive integers $N, M$, representing the number of nodes and edges. Each of the next $M$ lines (line $i$) contains $a_i, b_i, p_i$, meaning that the $i$-th edge connects nodes $a_i$ and $b_i$ and has weight $p_i$. It is guaranteed that the graph is connected and has no multiple edges.

The first line output $K$, the minimum number of operations required. In the next $K$ lines, output several integers separated by spaces: - The first number is the chosen number $x$. - The second number is $B$, the number of chosen edges. - Then output $B$ numbers $E_i$ ($1 \le E_i \le M$), indicating the indices of the chosen edges. These $B$ numbers must be output in increasing order. All output numbers must be less than or equal to $2 \times 10^9$.

#### Sample 1 Explanation The initial and final states of the graph (XOR $12$ onto the weights of the first three edges based on the initial state) are shown in the left and right figures below:   #### Sample 2 Explanation This undirected graph has no cycles, so the requirement is already satisfied and no modification is needed. Therefore, the minimum number of operations is $0$. #### Constraints For $20\%$ of the testdata, $K = 1$. For another $40\%$ of the testdata, all input numbers are less than or equal to $10^6$. For $100\%$ of the testdata, $1 \le N, M \le 10^5$, $1 \le a_i, b_i \le N$, $a_i \neq b_i$, and $0 \le p_i \le 10^9$. #### Notes **The score of this problem follows the original COCI setting, with a full score of $130$.** **Translated from [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf) _T5 Praktični_.** Translated by ChatGPT 5