Tiedostossa finland.in on 10639 Suomen paikkakunnan koordinaatit. Tehtäväsi on etsiä kierros, joka käy jokaisella paikkakunnalla ja palaa takaisin alkuun. Mitä lyhyempi kierros on, sitä enemmän pisteitä saat.

Syöte

Tiedoston ensimmäisellä rivillä on kokonaisluku n, paikkakuntien määrä. Paikkakunnat on numeroitu kokonaisluvuin 1,2,\ldots,n.

Sitten tiedostossa on n riviä, joista jokainen kuvaa tietyn paikkakunnan koordinaatit. Kullakin rivillä on kaksi desimaalilukua: x- ja y-koordinaatti. Kahden paikkakunnan etäisyys on niiden euklidinen etäisyys.

Palautus

Lähetä tiedosto finland.out, jossa on n kokonaislukua: paikkakuntien järjestys kierroksessa.

Saat tehtävästä \lfloor 100 p/u \rfloor pistettä, missä p on lyhin mahdollinen kierroksen pituus ja u on löytämäsi kierroksen pituus.

Esimerkki

Syöte:

3
3.2 5.0
0.0 1.2
3.3 7.0

Tuloste:

2 1 3

Selitys: Kierros on 2 \rightarrow 1 \rightarrow 3 \rightarrow 2.