Great road theft

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

In Ukraine, cities are connected by bidirectional roads. Between each pair of cities, there is at most one road. Also, a road cannot lead from a city to itself. However, between some cities, there may be no path, even transitively through other cities.

Zenyk has taken it upon himself to fix the situation. He wants it to be possible to reach any city from any other city via roads (possibly through other cities), so he started building roads between some pairs of cities.

The gray-haired Hetman claims that Zenyk is not building new roads, but is stealing old ones and moving them. Zenyk supposedly can steal a road connecting cities \(u\) and \(v\), and lay it between cities \(u\) and \(w\), if there is no road between them yet. According to the Hetman, Zenyk can do this many times.

You need to check the plausibility of the Hetman’s accusations. To do this, find the minimum number of thefts Zenyk must make so that it is possible to reach any city from any other city via roads, and provide an example of any minimum sequence of such thefts.

Input

The first line contains two integers \(n\) and \(m\) — the number of cities and roads in Ukraine, respectively.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) — the numbers of the cities connected by the corresponding road. Cities are numbered with integers from 1 to \(n\).

Output

In the first line, print an integer \(k\) — the minimum required number of thefts.

In the next \(k\) lines, print three integers \(u\), \(v\), and \(w\), describing the corresponding theft — theft of the road between cities \(u\) and \(v\) and laying a road between cities \(u\) and \(w\). At the moment of the theft, there must be a road between \(u\) and \(v\), and there must not be a road between \(u\) and \(w\).

For the given tests, there is at least one sequence of thefts that will connect all cities.

Constraints

\(1 \le n \le m \le 10^5\),

\(1 \le u, v, w \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
11 11 1 5 1 8 1 9 2 6 2 7 3 10 3 11 4 10 4 11 5 9 6 7	2 4 11 7 9 1 4

Notes

In the given test, Zenyk performs two thefts. First, he removes the road between cities 4 and 11 and replaces it with a road connecting cities 4 and 7. Then he replaces the road (9, 1) with the road (9, 4). After performing these two thefts, all pairs of cities will be connected to each other.