Državno natjecanje 2017. / Osnovna škola (8. razred) - 3. zadatak

U razredu jedne osnovne škole ima K dječaka.

Dječaci se vole igrati careva u obližnjoj šumi. U toj šumi nalazi se N kampova.

S obzirom da kampova ima barem koliko i dječaka, potrebno je kampove podijeliti među dječacima kako bi svaki mogao upravljati svojim carstvom.

Carstvo se sastoji od jednog ili više kampova, a svaki kamp mora pripadati točno jednom carstvu.

Zbog iznimno teškog upravljanja carstvima, svaki dječak želi smanjiti raspršenost svoga carstva.

Raspršenost jednog carstva definiramo kao zbroj udaljenosti svih parova kampova unutar carstva.

Kao i obično, nemoguće je svima udovoljiti pa te molimo da pomogneš dječacima i ispišeš neko grupiranje kampova u carstva tako da je zbroj raspršenosti carstva što manji.

Napomene:

Svakom kampu pridružene su dvije koordinate i nikoja dva kampa ne nalaze se na istoj poziciji.

Udaljenost dvaju kampova definiramo kao zbroj kvadrata razlika pripadajućih koordinata:

Ako u nekom carstvu postoji samo jedan kamp, tada smatramo da je njegova raspršenost kampova 0.

ULAZNI PODATCI

U prvom retku nalaze se prirodni brojevi N i K iz teksta zadatka (1 ≤ K ≤ N ≤ 1000). Kampovi su označeni brojevima 1, 2, ..., N.

U svakom od sljedećih N redaka nalaze se dvije koordinate kampa, cijeli brojevi X i Y (0 ≤ X, Y ≤ 10 000).

IZLAZNI PODATCI

U svakom od N redaka ispišite jedan broj između 1 i K, koji označava kojem carstvu i-ti kamp pripada.

PRIMJERI TEST PODATAKA

Ulaz

3 3
1 1
2 2
3 3

Izlaz

1
2
3

Ulaz

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

Izlaz

3
3
3
3
3
2
1

Objašnjenje

Opis drugog test podatka: Postoji više valjanih rješenja, ovo je jedno od mogućih, a ukupna raspršenost u ovom rješenju približno iznosi: