Disjoint Triangle Selection in a Partitionable Graph

You are given an undirected graph with \(6n\) vertices and \(m\) edges. It is guaranteed that the graph can be partitioned into \(2n\) copies of \(K_3\) (a complete graph on 3 vertices). Your task is to select \(n\) triangles (each forming a \(K_3\)) such that no vertex appears in more than one selected triangle.

Note: Vertices are numbered from 1 to \(6n\). The input guarantees that there exists a partition of the vertices into \(2n\) disjoint triangles. You only need to output any set of \(n\) disjoint triangles.

The problem can be formulated in \(\LaTeX\) as follows:

[ \begin{aligned} &\text{Given an undirected graph } G=(V,E) \text{ with } |V| = 6n \text{ and } |E| = m, \ &\text{and the guarantee that } V \text{ can be partitioned into } 2n \text{ triangles (i.e. } K_3 \text{ subgraphs),}\ &\text{find a collection } {T_1, T_2, \dots, T_n} \text{ of triangles such that } \forall i \neq j, \ T_i \cap T_j = \emptyset. \end{aligned} ]

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is a positive integer and \(m\) is the number of edges in the graph. The vertices are labeled from 1 to \(6n\). Each of the next \(m\) lines contains two integers \(u\) and \(v\) representing an undirected edge between vertex \(u\) and vertex \(v\).

It is guaranteed that the graph can be partitioned into \(2n\) disjoint triangles (i.e. \(K_3\) subgraphs).

outputFormat

Output exactly \(n\) lines, each containing three space-separated integers representing the vertices of a triangle (i.e. a \(K_3\)). The selected triangles must be vertex-disjoint (i.e. no vertex appears in more than one triangle).

sample

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

1 2 3