D. Path Partition
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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?

Input

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

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\}\}. $$$$$$

Scoring

There are $$$10$$$ test cases in total, each worth $$$10$$$ points. For your convenience, the values of $$$N$$$ and $$$M$$$ in each test case are shown in the following list:

  • Test $$$1$$$: $$$N = 771$$$, $$$M = 296835$$$.
  • Test $$$2$$$: $$$N = 772$$$, $$$M = 297606$$$.
  • Test $$$3$$$: $$$N = 1000$$$, $$$M = 300000$$$.
  • Test $$$4$$$: $$$N = 3000$$$, $$$M = 300000$$$.
  • Test $$$5$$$: $$$N = 10000$$$, $$$M = 300000$$$.
  • Test $$$6$$$: $$$N = 30000$$$, $$$M = 300000$$$.
  • Test $$$7$$$: $$$N = 50000$$$, $$$M = 300000$$$.
  • Test $$$8$$$: $$$N = 70000$$$, $$$M = 300000$$$.
  • Test $$$9$$$: $$$N = 80000$$$, $$$M = 300000$$$.
  • Test $$$10$$$: $$$N = 90000$$$, $$$M = 300000$$$.

It is guaranteed that each of the $$$10$$$ generated graphs has a valid partition.

Example
Input
10 15
3 10
10 4
3 6
5 8
10 9
5 2
1 4
1 9
1 7
8 3
1 6
6 10
10 2
8 2
4 3
Output
2 5 8 2
8 3 10 2
3 4 1 7
6 1 9 10
3 6 10 4
Note

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.