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

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


1 2
2 3
3 1
1 10
1 2 3
3 1 10
1 2
2 3
3 1
4 10


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