403202: GYM101064 I Protecting the Central Park

One of the most popular tourist attractions in the USA is the Central Park, in New York City. This park appears in several movies. It is also one of the largest in the world: it spans an area twice as large as Monaco. The park has many monuments and buildings such as the Belvedere Castle, the Victorian Gardens, the Marionette Theather, a zoo, among others. These attract visitors and tourists everyday. Central Park is administered by Central Park Conservancy (CPC). The CPC is responsible for security of the park, among other things. Recently, the CPC has noted that attendance to the park has been increasing. Due to concerns with the safety of visitors and tourists, the CPC has chosen a few places, and paths that joins these places, to be kept under constant surveillance.

Due to the humongous size of the park and budget issues, CPC is looking for a way to perform this task as efficiently as possible. The CPC hired an expert to solve this problem, Marcel "the optimizer" Saito. After studying the situation for a while, Marcel concluded that the problem can be solved optimally using his most famous technique: Separation Determined by Pairs (SDP).

SDP considers the places and paths that need protection and attributes pairs of paths to the guards, with the requirement that each path must be in a single pair, and each pair of paths must intersect at a common place. The following figure shows (a) the first sample input, and (b) one way to perform separation determined by pairs (each pair of paths is represented by a different type of line).

You wish to impress Marcel so that he will take you as an apprentice, by writing a program that finds such separation. After a little thought, you believe it is not always possible to find such separation, and you inquire Marcel. But Marcel says: "Everything is connected and we always have an even number of paths, so clearly it is always possible!" Though you still do not understand why this claim is true, you decide not to cross your mentor and start working.

The first line has two integers, N and M, separated by a blank space, the represent the number of critical places and the number of paths joining these places, respectively. The places are numbered 1 to N. Each one of the next M lines describes a path. Each path is represented by two integers, say u and v, separated by a blank space. The numbers u and v represent the places connected by this path. It is guaranteed that u ≠ v, that there are not multiple paths joining the same two places and that you can go from one place to any other place by traversing a sequence of paths.

Limits

• 1 ≤ N ≤ 10⁴
• 2 ≤ M ≤ 5·10⁵, and M is even

In the first line, print the number of paths of the separation, say K. In the next K lines, print the pairs of the separation, one per line. Each pair of paths must be represented by three integers separated by a blank space, and they must be printed in the following format: "u v w", where (u, v) and (v, w) are the paths that make up this pair. Note that it is equivalent to write "u v w" ou "w v u". If there are multiple solutions, any one will be accepted.

5 6
1 2
1 3
2 4
2 3
3 5
4 5

3
1 3 2
3 5 4
4 2 1