Problem C
Train Journey

A group of people are going to travel by train and are thinking about where they are going to sit. A group of people are going to travel by train and are thinking about how to sit. $M$ pairs of people are friends and want to sit as close to each other as possible. The train car they are going to sit in has $N$ rows and is arranged as an $N \times 4$ grid, with $4$ seats per row. There are $4N$ people in the group. The people are numbered $1$ to $4N$.

Each pair of friends that sit in seats with Euclidean distance $L = \sqrt{dx^2 + dy^2}$ contributes $1/L^2$ to the group’s total happiness. Your task is to place the people so that the group’s happiness is as great as possible.

Input

The input consists of $10$ test cases.

The first line contains the number $T$ ($0 \le T \le 10$), which describes the number of the test case ($0$ for the sample). The second line contains the numbers $N$ and $M$ ($1 \le N \le 25\, 000$, $1 \le M \le 100\, 000$) – the number of rows in the train car and the number of pairs of friends. Then follow $M$ lines each containing two integers $a$ and $b$ ($1 \le a,b \le 4N$, $a \ne b$) – indicating that $a$ and $b$ are friends.

Output

Print $N$ lines with $4$ integers on each line. Each line should contain the numbers of the four people that sit in that row. All the people must be placed somewhere.

Scoring

Your program will be tested with $10$ test cases.

Your score for a submission is the sum of the points for the test cases.

Your score is computed relative to a judge’s solution. If your solution is better than the one the judges threw together, it is possible that you will get more than $10$ points on a test case. However, your total points are limited to $100$.

The sample test case always gives $0$ points.

Explanation of sample test case

In the sample test case we want to place $8$ in a $2 \times 4$ grid. The sample solution optimizes the distance for all friendships except $1$ and $4$ that are at a distance of $\sqrt3$ from each other. The sum of happiness is $4 \cdot 1/1 + 1/3 \approx 4.33$.

A better solution can be found so that all pairs of friends are at a distance of $1$

Test cases

The graph of friendships is called $G$ in some of the descriptions below. Here are descriptions of the $10$ test cases:

Here "random" means uniformly random.

0
2 5
5 7
8 7
1 2
2 3
1 4

6 5 7 8
1 2 3 4