시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 512 MB33015413548.736%

## 문제

Let G = (V, E) be a simple undirected graph with N vertices and M edges, where V = {1, . . . , N}. A tuple <u, v, w> is called as boomerang in G if and only if {(u, v),(v, w)} ⊆ E and u ≠ w; in other words, a boomerang consists of two edges which share a common vertex.

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

For example, consider a graph G = (V, E) of N = 5 vertices and M = 7 edges where E = {(1, 2), (1, 4), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5)}.

The maximum number of disjoint boomerangs in this example graph is 3. One example set containing the 3 disjoint boomerangs is {<4, 1, 2>,<4, 3, 2>,<2, 5, 3>}; no set can contain more than 3 disjoint boomerangs in this example.

## 입력

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

## 출력

The first line of output contains an integer: K, representing the maximum number of disjoint boomerangs in G. The next K lines, each contains three integers: u v w (each separated by a single space), representing a boomerang <u, v, w>. 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