Graph Cycle Goodness via XOR Operations

You are given an undirected graph with \(N\) vertices and \(M\) edges. Each edge has a weight less than \(10^9\). A simple cycle is called a good cycle if the XOR (denoted by \(\oplus\)) of all edge weights in the cycle is \(0\).

You are allowed to perform an arbitrary number of operations on the graph. In each operation, you do the following:

• Select an integer \(x\).
• Select a non-empty set of edges.
• For every selected edge, update its weight as \(w \leftarrow w \oplus x\).

Your goal is to make every simple cycle in the graph a good cycle using as few operations as possible. In other words, after performing the operations, for every simple cycle \(C\) the following must hold:

[ \bigoplus_{e \in C} w_e = 0. ]

A key observation is that the condition is equivalent to being able to assign a value \(f(v)\) to each vertex \(v\) so that for every edge \((u,v)\) the new weight satisfies:

[ w_{uv} = f(u) \oplus f(v). ]

One natural solution is to choose a spanning forest of the graph and assign potentials \(f(\cdot)\) to vertices so that for every tree edge \((u,v)\) we have \(f(v) = f(u) \oplus w_{uv}\) (with some arbitrary starting value, say 0, for each component). Then for each non‐tree edge \((u,v)\), the desired consistency becomes:

[ w_{uv} \oplus (f(u) \oplus f(v)) = 0. ]

If for a non‐tree edge \(e\) we define:

[ d(e) = w_e \oplus (f(u) \oplus f(v)), ]

then we must change its weight by \(d(e)\) (i.e. apply an XOR of \(d(e)\)) so that \(w_e \oplus d(e) = f(u) \oplus f(v)\). Note that applying an XOR operation on a set of edges is cumulative. Thus, if several edges require the same \(d(e) \neq 0\), you can fix them all with one operation by choosing \(x = d(e)\).

Your task is to compute the minimum number of operations required and provide one valid sequence of operations. The output format is as follows:

• First line: an integer \(k\) representing the minimum number of operations.
• Then for each operation, output a line containing an integer \(x\), followed by an integer \(t\) (the number of edges in this operation), then \(t\) space‐separated edge indices (edges are numbered from 1 to \(M\) in the order of input) on which the operation is applied.

If no operation is needed, simply output 0.

inputFormat

The first line contains two integers \(N\) and \(M\) \((1 \leq N \leq 10^5, 0 \leq M \leq 10^5)\) representing the number of vertices and edges respectively.

Each of the next \(M\) lines contains three integers \(u\), \(v\), and \(w\) \((1 \leq u, v \leq N, 0 \leq w < 10^9)\) describing an edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

On the first line, output an integer \(k\) denoting the minimum number of operations.

If \(k > 0\), then for each operation output a line containing:

• an integer \(x\) (the value to XOR with),
• an integer \(t\) (the number of edges this operation is applied on),
• \(t\) space-separated integers representing the 1-indexed edge IDs.

The operations must be such that after all operations the weight of every edge \((u,v)\) satisfies \(w_{uv} = f(u) \oplus f(v)\) for some assignment of vertex values \(f(1), f(2),\dots, f(N)\), hence making every simple cycle a good cycle.

sample

3 3
1 2 1
2 3 2
3 1 3

0