Garbage Truck Routes

In a city that can be seen as an undirected graph, there are \(n\) vertices and \(m\) edges. Each edge (road) has a state: clean (represented by 0) or unclean (represented by 1). Initially, all roads are clean. Every day several garbage trucks run in a cycle (that is, they start at some vertex, travel through other vertices without revisiting any vertex except the starting vertex, and finally return to the start) and every time a truck passes an edge, it toggles the state of that edge (i.e. changes it from 0 to 1, or from 1 to 0).

The mayor wants certain roads – specifically those whose residents do not pay the garbage fee – to become unclean (1), and all the other roads to remain clean (0). You are given, for each road, its endpoints and the desired final state \(d_i\) (either 0 or 1). Determine a set of cycles (each cycle corresponding to one garbage truck’s route) so that if every truck’s cycle is executed (the order does not matter because toggling is taken modulo 2), then each road is toggled an appropriate number of times and ends up with the required state.

Important: For every truck, besides the starting vertex, no vertex should be visited more than once (i.e. each truck’s route must be a simple cycle).

Note: An edge is toggled each time it is traversed. Therefore if an edge is traversed an even number of times, its state remains unchanged; if it is traversed an odd number of times, its state is flipped. Since the initial state is 0 (clean), to achieve a final state of 1 the edge must be traversed an odd number of times, and to achieve a final state of 0 it must be traversed an even number of times.

A necessary and sufficient condition for the existence of such a set of cycles is that for every vertex, the sum (modulo 2) of \(d_i\) for all edges incident on that vertex is 0. If this condition is not met, output -1.

If a solution exists, output the number of cycles \(k\) in the first line. Then, for each cycle, output one line starting with its length \(L\) (the number of vertices in the cycle) followed by \(L\) integers representing the vertices in order. The cycle is understood to be closed (i.e. there is an implicit edge from the last vertex back to the first); note that apart from the implicit closure, no vertex appears more than once in the listing.

If no solution exists, output -1.

Example: For a triangle where all three edges require toggling (i.e. each has \(d=1\)), one valid output is:

1
3 1 2 3

because the cycle 1 → 2 → 3 → 1 toggles all three edges once.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(0 \le m \le 10^5\)); the number of vertices and edges in the graph.

Each of the next \(m\) lines contains three integers \(u\), \(v\) and \(d\) (\(1 \le u, v \le n\), \(d \in \{0,1\}\)) representing an undirected edge between vertices \(u\) and \(v\) with a desired final state \(d\).

outputFormat

If there is no solution (i.e. the necessary parity condition is not met at one or more vertices), output a single line containing -1.

Otherwise, output an integer \(k\) on the first line – the number of cycles (garbage truck routes). Then output \(k\) lines, each describing a cycle. For each cycle, first output an integer \(L\), the number of vertices in the cycle (do not count the starting vertex twice), followed by \(L\) space‐separated integers indicating the vertices in order along the cycle. The cycle is considered closed (i.e. there is an edge from the last vertex back to the first), and aside from that, no vertex is repeated.

sample

3 3
1 2 1
2 3 1
3 1 1

1
3 1 2 3

</p>