Дано $$$n$$$ точек на плоскости. Все точки попарно различны. Требуется покрасить каждую из них в один из $$$k$$$ цветов, чтобы точек каждого цвета было ровно $$$\frac{n}{k}$$$ штук. Гарантируется, что $$$n$$$ делится на $$$k$$$.
Для каждого цвета $$$c$$$ будет вычислено $$$s_c$$$ — квадрат расстояния между двумя ближайшими точками этого цвета. Суммарный балл будет равен сумме $$$s_c$$$. Требуется максимизировать суммарный балл.
В первой строке записано целое число $$$t$$$ — количество тестов.
Каждый тест начинается с двух целых чисел $$$n$$$ и $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le k \le 25$$$) — количества точек и цветов соответственно. Затем следуют $$$n$$$ строк, в каждой строке по два числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \le x_i, y_i \le 1000$$$) — координаты точек.
Для каждого решенного вами теста выведите «Case #j:», где $$$j$$$ — номер теста от $$$1$$$ до $$$t$$$, а затем строку из $$$n$$$ заглавных латинских букв, где $$$i$$$-я буква обозначает цвет, в который нужно покрасить $$$i$$$-ю точку. Каждая буква должна быть среди $$$k$$$ первых букв латинского алфавита.
2 4 2 0 0 1 0 1 1 0 1 4 2 0 0 1 0 1 1 0 1
Case #1: AABB Case #2: ABAB
В примере два совпадающих теста, но два различных ответа на этот тест. Раскраска «AABB» дает суммарный балл 2, а раскраска «ABAB» дает суммарный балл 4.
В тестовом файле 60 тестов. Тесты 1-10 обладают одной особенностью, тесты 11-20 — другой особенностью, тесты 21-30 — третьей особенностью, тесты 31-40 — четвертой особенностью, а тесты 41-60 сгенерированы рандомно.
Балл за задачу будет вычислен как среднее арифметическое баллов за каждый тест, округленное вниз. Так, если бы входной файл содержал только два теста из примера, то ответ из примера набрал бы 3 балла.