ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Later is better than never

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Graph Decomposition. Version 2

Time limit: 1.0 second
Memory limit: 128 MB
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

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.

Output

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 {ab} and {bc}. If there is no such decomposition, output “-1”.

Samples

inputoutput
1 2
2 3
3 1
1 10
2
1 2 3
3 1 10
1 2
2 3
3 1
4 10
-1

Notes

This problem is a more difficult version of the problem “Graph Decomposition”.
Problem Author: Alexander Petrov, prepared by Alexander Ipatov
To submit the solution for this problem go to the Problem set: 2132. Graph Decomposition. Version 2