409147: GYM103446 L Three,Three,Three

A poor little penguin has been thrown by a killer whale for a distance of one hundred and eight thousand li. The poor little penguin found itself on a mysterious island then. On the ground there are many graphs. The poor little penguin found that all the vertices are of degree three. "The Dao produced One; One produced Two; Two produced Three; Three produced All things", the poor little penguin recalled this mystical sentence. Suddenly, a quill-pen came into view. A sound said, "Every time you dip the quill-pen in the sea, you can one-touch-draw three edges. That is, you can start at a vertex, pass three different edges to a vertex." It is a parrot with three golden feathers on top of its head, "If all edges of a graph could be drawn once and only once by this way, then we call it a Three-throwable graph. You should find all the Three-throwable graphs, and show me how to throw three! As soon as you're done, I will bestow you the Produced-All-Things Power and send you back to avenge yourself on the killer whale!"

Too many graphs! So the poor little penguin asks you three for help. Please help it, for Light and Justice.

In short, given a graph of $$$n$$$ vertices and $$$m$$$ edges, where $$$n$$$ is even and all the vertices are of degree 3. So it can be seen that $$$m = \frac{3n}{2}$$$ and that $$$m$$$ is multiple of 3. You should try to split the graph into $$$\frac{m}{3}$$$ chains of length 3. Determine if the graph is Three-throwable graph(such chain spliting scheme exists) and output the splited chains if solution exists.

The first line contains two integers $$$n,m\,(2\leq n\leq 500)$$$, denoting the number of vertices and edges.

Following $$$m$$$ lines each contains two integers $$$u,v\,(1\leq u,v\leq n)$$$, denoting an edge connecting vertex $$$u$$$ and $$$v$$$.

It is guaranteed that $$$n$$$ is even, $$$m=\frac{3n}{2}$$$ and that all the vertices are of degree 3.

If it is not a Three-throwable graph, output "IMPOSSIBLE"(without quotes) in one line.

Otherwise, output $$$\frac{m}{3}$$$ lines each contains four integers $$$a_i,b_i,c_i,d_i$$$, denoting one chain containing three edges $$$a_i\leftrightarrow b_i,b_i\leftrightarrow c_i,c_i\leftrightarrow d_i$$$. The multiset of given edges and the multiset of all the chain edges should be the same. If multiple solutions, output any one of them.

2 3
1 2
1 2
1 2

2 1 2 1

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

1 1 2 3
2 3 4 4

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

IMPOSSIBLE