Description

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.

Input Format

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.

Output Format

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$.

4 4
1 2 10
2 3 9
3 4 8
4 1 7

1
12 3 1 2 3

2 1
1 2 3

0

6 8
1 2 6
2 3 1
3 5 6
3 1 5
4 5 0
3 6 0
4 2 8
4 1 1

2
2 2 4 6
15 1 7

Hint

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 CONTEST #3 T5 Praktični.

Translated by ChatGPT 5