Tågresan

문제

En grupp personer ska åka tåg och funderar hur de ska sitta. $MM$ par av personerna är vänner och vill sitta så nära varandra som möjligt. Tågvagnen de ska sitta i har $NN$ rader och är utformad som ett $N\times 4N\; \backslash times\; 4$ rutnät, med 4 platser på varje rad. Det finns $4N4N$ personer i gruppen. Personerna är numrerade $11$ till $4N4N$.

Varje par av vänner som sitter på platser med euklidiskt avstånd $L=\sqrt{d{x}^2+d{y}^2}L\; =\; \backslash sqrt\{dx^2\; +\; dy^2\}$ bidrar med $1\mathrm{/}{L}^{2}1/L^2$ till gruppens totala lycka. Din uppgift är att placera ut personerna så att gruppens lycka blir så stor som möjligt.

입력

Indatan består av $1010$ testfall.

Den första raden innehåller talet $TT$ ($0\le T\le 100\; \backslash le\; T\; \backslash le\; 10$), som beskriver numret på testfallet ($00$ för sample). Den andra raden innehåller talen $NN$ och $MM$ ($1\le N\le 250001\; \backslash le\; N\; \backslash le\; 25\backslash ,000$, $1\le M\le 1000001\; \backslash le\; M\; \backslash le\; 100\backslash ,000$) -- antalet rader i tågvagnen samt antalet par av vänner. De följande $MM$ raderna innehåller två heltal $aa$ och $bb$ ($1\le a,b\le 4N1\; \backslash le\; a,b\; \backslash le\; 4N$, $a\mathrm{\ne }ba\; \backslash ne\; b$) -- nummer för två vänner.

출력

Skriv ut $NN$ rader med 4 heltal på varje. Varje rad ska innehålla nummer för de fyra personer som sitter på den raden. Alla personer ska placeras ut någonstans.

힌트

I exempelfallet vill vi placera ut 8 personer i ett $2\times 42\; \backslash times\; 4$ rutnät. Exempellösningen optimerar avståndet för alla vänskapsrelationer utom 1 och 4 som sitter på avstånd $\sqrt{3}\backslash sqrt\; 3$ från varandra. Summan av lycka blir $4\cdot 1\mathrm{/}1+1\mathrm{/}3\approx 4.334\; \backslash cdot\; 1/1\; +\; 1/3\; \backslash approx\; 4.33$.

En bättre lösning kan fås till så att alla par av vänner sitter på avstånd 1. Om det testfallet have varit ett riktigt testfall och en annan deltagare hade genererat denna lösning (total lycka $55$) så hade testfallet getts $10\cdot (4.33\mathrm{/}5{)}^2\approx 7.5110\; \backslash cdot\; (4.33\; /\; 5)^2\; \backslash approx\; 7.51$ poäng.