Path Partition

This is an "output-only" problem. The test cases are made available to you. However, due to the large output size, you should still submit a program that reads the input and produces the outputs within the time limit.

Busy Beaver generated a random undirected graph with $N$ vertices and $M$ edges, where $M$ is a multiple of $3$. Now, he wants to partition the edges into $M/3$ paths of length $3$ (possibly starting and ending at the same vertex). Can you help Busy Beaver find such a partition?

Please download the test data using this link.

The first line of input contains two integers $N$ and $M$ --- the number of vertices and edges in the graph, respectively.

The $i$th of the next $M$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i,v_i \le N, u_i \ne v_i$) --- the endpoints of the $i$th edge.

It is guaranteed that the $M$ edges were generated randomly. Formally, out of the $\frac{N(N-1)}{2}$ possible edges, $M$ distinct edges were chosen uniformly at random without replacement.

Output $M/3$ lines. The $i$th line should contain $4$ integers $a_i$, $b_i$, $c_i$, and $d_i$ ($1 \le a_i,b_i,c_i,d_i \le N$), representing a path using edges $(a_i,b_i)$, $(b_i,c_i)$, and $(c_i,d_i)$.

It is allowed to have $a_i = d_i$. Your output should satisfy $$ \bigcup_{i=1}^{M/3} \{\{a_i,b_i\},\{b_i,c_i\},\{c_i,d_i\}\} = \bigcup_{i=1}^M \{\{u_i,v_i\}\}. $$

The sample is provided to illustrate the input and output format. It is not scored.

The sample graph and partition are shown in the figure below. Note that the path $2 - 5 - 8 - 2$ starts and ends at the same vertex, which is allowed.