Problem C
Tågresan

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

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

Indata

Indatan består av $10$ testfall.

Den första raden innehåller talet $T$ ($0 \le T \le 10$), som beskriver numret på testfallet ($0$ för sample). Den andra raden innehåller talen $N$ och $M$ ($1 \le N \le 25\, 000$, $1 \le M \le 100\, 000$) – antalet rader i tågvagnen samt antalet par av vänner. De följande $M$ raderna innehåller två heltal $a$ och $b$ ($1 \le a,b \le 4N$, $a \ne b$) – nummer för två vänner.

Utdata

Skriv ut $N$ 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.

Poängsättning

Ditt program kommer att testas på $10$ testfall.

Din poäng för en inskickning är summan av poängen för testfallen, och din totala poäng är poängen för den bästa inskickningen. Det går alltså inte att kombinera testfall mellan olika inskickningar, utan du måste skicka in ett enda program som maximerar din poäng på alla testfall samtidigt.

Din poäng sättas relativt en domarlösning. Om din lösning är bättre än den domarna slängt ihop är det därmed möjligt att du tillfälligt får mer än $10$ poäng på ett testfall. Din totalpoäng kommer dock att begränsas till $100$.

Sampletestfallet kommer alltid att ge $0$ poäng.

Förklaring av exampelfall

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

En bättre lösning kan fås till så att alla par av vänner sitter på avstånd $1$.

Testfall

Grafen av vänskapsrelationer kallas $G$ i vissa av beskrivningarna nedan. Här är beskrivningar av de $10$ testfallen som förekommer:

Med slumpmässig menas här likformigt slumpmässig.

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

6 5 7 8
1 2 3 4