There is a simple graph with an even number of edges. You need to represent it as a set of pairs of adjacent edges (having a common vertex).

Input contains a sequence of the pairs with the integers. The length of the sequence is even and is from 2 to 100000. Each pair of integers is the identifiers of vertices of one edge. All the identifiers are from 1 to 100000. It is guaranteed that there are neither loops nor multiple edges in the given graph.

If a required decomposition exists, in the first line output an integer m that is a number of pairs of adjacent edges. The following m lines should contain triples of integers a, b, c, representing the edges of the given graph {a, b} and {b, c}. If there is no such decomposition, output “-1”.

This problem is a more difficult version of the problem “Graph Decomposition”.