ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

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”.

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