#216024. [ICPC 2018 Jakarta R] Boomerangs

Let be a simple undirected graph with vertices and edges, where . A tuple is called as boomerang in if and only if and ; in other words, a boomerang consists of two edges which share a common vertex.

Given , your task is to find as many disjoint boomerangs as possible in . A set contains disjoint boomerangs if and only if each edge in only appears at most once (in one boomerang) in . You may output any valid disjoint boomerangs, but the number of disjoint boomerangs should be maximum.

For example, consider a graph of vertices and edges where .

:::align{center} :::

The maximum number of disjoint boomerangs in this example graph is . One example set containing the disjoint boomerangs is ; no set can contain more than disjoint boomerangs in this example.

Input begins with a line containing two integers: (), representing the number of vertices and the number edges in , respectively. The next lines, each contains two integers: (), representing the edge in . You may safely assume that each edge appears at most once in the given list.

The first line of output contains an integer: , representing the maximum number of disjoint boomerangs in . The next lines, each contains three integers: (each separated by a single space), representing a boomerang . All boomerangs in the output should be disjoint. If there is more than one valid solution, you can output any of them.

样例输入 1

5 7
1 2
1 4
2 3
2 4
2 5
3 4
3 5

样例输出 1

3
4 1 2
4 3 2
2 5 3

样例输入 2

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

样例输出 2

3
1 2 3
1 3 4
1 4 2

样例输入 3

3 3
1 2
1 3
2 3

样例输出 3

1
2 1 3