Problem Description

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 in the cycle is $0$.

You can perform several operations on the undirected graph. Each operation includes the following steps:

• Select an integer $x$.
• Select a non-empty set of edges.
• XOR each edge in the set with $x$.

Your task is to make all simple cycles in the graph good cycles with the minimum number of operations. Output the minimum number of operations and the corresponding operation parameters.

Input Format

The first line contains two positive integers $N$ and $M$, representing the number of nodes and edges, respectively.

The next $M$ lines, each containing three integers $a_i$, $b_i$, and $p_i$, represent the nodes connected by the $i$-th edge and the edge's weight. The graph is guaranteed to be connected and has no duplicate edges.

Output Format

The first line should output $K$, the minimum number of operations needed.

The next $K$ lines should each contain several numbers separated by spaces:

• The first number is the selected integer $x$.
• The second number is $B$, the number of selected edges.
• The next $B$ numbers $E_i$ ($1 \le E_i \le M$) represent the indices of the selected edges. These $B$ numbers must be output in ascending order.

All numbers output must be less than or equal to $2 \times 10^9$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
12 3 1 2 3

Sample Input #2

2 1
1 2 3

Sample Output #2

0

Sample Input #3

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

Sample Output #3

2
2 2 4 6
15 1 7

Notes

Sample 1 Explanation

The initial and final states of the graph (after XORing the weights of the first three edges with $12$) are shown in the left and right diagrams below:

Sample 2 Explanation

The undirected graph has no cycles, so the condition is already satisfied, and no modifications are needed, resulting in a minimum operation count of $0$.

Data Size and Constraints

For $20\%$ of the data, $K=1$.

For another $40\%$ of the data, all input numbers are less than or equal to $10^6$.

For $100\%$ of the data, $1 \le N, M \le 10^5$, $1 \le a_i, b_i \le N$, $a_i \neq b_i$, $0 \le p_i \le 10^9$.

Notes

This problem's score is set according to the original COCI contest, with a full score of $130$.

The problem is translated from COCI2018-2019 CONTEST #3 T5 Praktični.

见题面 Input 部分

见题面 Output 部分