Hide

# 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:

 Test case Bounds Description of test case $1$ $N = 10$, $M = 100$ All edges in $G$ are generated randomly. $2$ $N = 100$, $M = 500$ All edges in $G$ are generated randomly. $3$ $N = 100$, $M = 8\, 000$ All edges in $G$ are generated randomly. $4$ $N = 8\, 000$, $M \le 45\, 000$ $G$ is made up of groups of friends of sizes $1$ - $5$ where everyone knows everyone. $5$ $N = 2\, 500$, $M = 8\, 000$ $G$ contains no cycles. The maximum distance in $G$ is $2$. $6$ $N = 2\, 500$, $M = 9\, 800$ $G$ contains no cycles. The maximum distance in $G$ is $2$. $7$ $N = 2\, 500$, $M = 9\, 999$ $G$ contains no cycles. $8$ $N = 25\, 000$, $M = 99\, 999$ $G$ contains no cycles. $9$ $N = 10\, 000$, $M = 100\, 000$ All edges in $G$ are generated randomly. $10$ $N = 25\, 000$, $M = 100\, 000$ All edges in $G$ are generated randomly.

Here "random" means uniformly random.

Sample Input 1 Sample Output 1
0
2 5
5 7
8 7
1 2
2 3
1 4

6 5 7 8
1 2 3 4

CPU Time limit 6 seconds
Memory limit 1024 MB
Difficulty 4.6 - 9.2hard
Statistics Show