Problem C
鉄道旅行

電車で移動することになり、どこに座ろうかと考えているグループがいます。 $m$組のペアの人たちは友達で、できるだけ近くに座りたいと思っています。 彼らが座ろうとしている電車の車両には、$N$列の座席があり、$N \times 4$の格子状に配置されていて、各列に$4$席があります。 グループの中には、$4N$人がいます。 それぞれの人には、$1$から$4N$までの番号が振られています。

ユークリッド距離 $L = \sqrt{dx^2 + dy^2}$ だけ離れた席に座っている友達のペアは、グループの幸福度に $1/L^2$ を与えます。 あなたの課題は，グループの幸福度が最大になるように人を配置することです．

入力

入力は$10$個のテストケースで構成されています。

最初の行には数 $T$ ($0 T \le T \le 10$) を含みます。これは、テストケースの番号(サンプルの場合は$0$)を表します。 2行目には、数 $N$と$M$（$1 \le N \le 25\, 000$, $1 \le M \le 100\, 000$）があり、車内の列の数と友達のペアの数を表します。 以降の$M$行には、2つの整数$a$と$b$ ($1 \le a,b \le 4N$, $a \ne b$) があり、$a$と$b$が友達だということを表します。

出力

各行に $4$ 個の整数を含む $N$ 行を出力します。 各行には、その行に座っている4人の番号を出力します。 すべての人をどこかに配置しなければなりません。

得点

プログラムは、$10$ 個のテストケースでテストを行います。

投稿に対する得点は、それぞれのテストケースに対する得点の合計となります。

あなたのスコアは、審査員の解答に対して相対的に設定されます。 あなたの解答が審査員の解答よりも優れている場合、テストケースの得点は$10$点以上になることがあります。 しかし、合計得点は$100$点に制限されます。

サンプル問題の得点は $0$ 点です。

サンプルの説明

サンプル問題では、$8$人を $2 \times 4$ のグリッドに配置します。 解答は、$1$ と $4$ (彼らは距離 $\sqrt3$) 以外の友達の距離を最適化しています。 幸福度の合計は、$4 \cdot 1/1 + 1/3 \approx 4.33$となります。

よりよい解として、すべての友達の距離を$1$にすることが可能です。

テストケース

友達の関係グラフは下記の記述で$G$と呼びます。 $10$個のテストケースを説明します。

「ランダム」は、次の意味です。 連続一様分布.

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

6 5 7 8
1 2 3 4