Lýsing

Skoðum $n$ heiltölupunkta á sléttu, þar sem $n$ er deilanlegt með $3$. Hnitin $x$ eru umröðun heiltalnanna frá $1$ til $n$. Hnitin $y$ eru einnig umröðun heiltalnanna frá $1$ til $n$.

Smíðið uppsetningu af $n/3$ þríhyrningum með hornpunkta í gefnu punktunum: sérhver punktur verður að koma fyrir sem hornpunktur í einum af þríhyrningunum. Þríhyrningarnir mega vera úrkynjaðir og mega skerast frjálslega.

Stigafjöldi uppsetningar er summa stærða allra þríhyrninga í henni. Stærð þríhyrnings er ummál umlykjandi rétthyrnings hans (bounding rectangle). Umlykjandi rétthyrningurinn er minnsti rétthyrningurinn með hliðar samsíða hnitásunum sem inniheldur þríhyrninginn.

Finnið uppsetningu sem nær hæsta mögulega stigafjölda.

Inntak

Fyrsta línan inniheldur heiltölu $n$ ($3 \le n \le 99\,999$; $n$ er deilanlegt með $3$).

Hver af næstu $n$ línum inniheldur tvær heiltölur $x$ og $y$: hnit eins punktsins. Hver heiltala frá $1$ til $n$ kemur einu sinni fyrir meðal $x$-hnitanna og einu sinni meðal $y$-hnitanna.

Úttak

Prentið hæsta mögulega stigafjöldann á fyrstu línuna.

Prentið næst hvaða uppsetningu sem er sem nær þessum stigafjölda. Til þess skuluð þið prenta $n/3$ línur með þremur heiltölum í hverri: númer punktanna í inntakinu sem eru hornpunktar þríhyrnings. Punktarnir eru númeraðir frá $1$ til $n$ í inntaksröð. Hægt er að prenta þríhyrningana og hornpunkta þeirra í hvaða röð sem er.

Dæmi

6
6 5
3 6
5 3
2 4
1 1
4 2

32
2 3 5
6 1 4

Athugasemd