Hide

Problem C
Train Journey

Languages en ja sv

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×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=dx2+dy2 contributes 1/L2 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 (0T10), which describes the number of the test case (0 for the sample). The second line contains the numbers N and M (1N25000, 1M100000) – 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 (1a,b4N, ab) – 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×4 grid. The sample solution optimizes the distance for all friendships except 1 and 4 that are at a distance of 3 from each other. The sum of happiness is 41/1+1/34.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=8000

All edges in G are generated randomly.

4

N=8000, M45000

G is made up of groups of friends of sizes 1 - 5 where everyone knows everyone.

5

N=2500, M=8000

G contains no cycles. The maximum distance in G is 2.

6

N=2500, M=9800

G contains no cycles. The maximum distance in G is 2.

7

N=2500, M=9999

G contains no cycles.

8

N=25000, M=99999

G contains no cycles.

9

N=10000, M=100000

All edges in G are generated randomly.

10

N=25000, M=100000

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
Hide

Please log in to submit a solution to this problem

Log in