Головна ідея задачі в цілому аналогічна «Задачі комівояжера — 2», а отже й «Задачі комівояжера — 1». Більш того, формат вхідних даних та результату теж в цілому аналогічні «Задачі комівояжера — 2». Але є дуже істотні відмінності, які роблять задачу істотно іншою:

1. це (начебто, єдина в усьому курсі «Алгоритми та структури даних») задача, в якій не обов'язково знаходити точний розв'язок, досить і наближеного;

2. розмір вхідних даних ще більший, а обмеження часу й пам'яті жорсткіші.

На площині задані координати ~n~ (~4\leqslant n\leqslant 100~) різних вершин.

Знайти по можливості короткий замкнений маршрут, що починається і закінчується в 1-й вершині і відвідує всі інші вершини по одному разу. Дозволяється (якщо так виявляється вигідно) «проїжджати через вершину, не зупиняючись» (див. приклад 1).

Довжина маршруту обчислюється як сума довжин складових його ребер, довжини окремих ребер обчислюються згідно звичайної евклідової метрики, як ~\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}~.

Вхідні дані

Перший рядок містить кількість вершин ~n~ (~4\leqslant n\leqslant 100~). Кожен з наступних ~n~ рядків містить по два розділених пропуском числа з плаваючою точкою – ~x~- та ~y~-координати відповідної вершини.

Результати та особливості їх оцінювання

Перший рядок повинен містити єдине число (з плаваючою крапкою) – знайдену мінімальну довжину замкненого маршруту.

Другий рядок повинен містити перестановку чисел 2, 3, ..., ~n~ – порядок, в якому треба відвідувати ці вершини (нумерація вершин з одиниці, й вершина 1 є початком та кінцем замкненого маршруту). Числа всередині другого рядка повинні розділятися одинарними пропусками.

Довжина маршруту з першого рядка і сам маршрут з другого рядка повинні відповідати одне одному досить точно: необхідно, щоб довжина маршруту з другого рядка відповідала числу з першого з абсолютною або відносною похибкою (досить, щоб хоча б одна з них) не перевищувала ~10^{-9}~; при порушенні цієї вимоги, тест оцінюється на 0% балів.

Однак, знайдений «приблизно мінімальний» маршрут може й не бути справді мінімальним. Водночас, чим коротший – тим краще. Позначимо довжину найкоротшого з відомих автору задачі маршрутів як ~d_0~, а довжину знайденого Вашою програмою маршруту як ~d~; тоді, кількість балів за тест буде такою:

1. якщо ~d\leqslant 1{,}05\cdot d_0~, то 100% балів за цей тест;

2. якщо ~1{,}05\cdot d_0<d\leqslant 1{,}1\cdot d_0~, то 95% балів за цей тест; </p>

3. якщо ~1{,}1\cdot d_0<d\leqslant 1{,}2\cdot d_0~, то 90% балів за цей тест; </p>

4. якщо ~1{,}2\cdot d_0<d\leqslant 1{,}5\cdot d_0~, то 80% балів за цей тест; </p>

5. якщо ~1{,}5\cdot d_0<d\leqslant 2\cdot d_0~, то 60% балів за цей тест; </p>

6. якщо ~2\cdot d_0<d\leqslant 3\cdot d_0~, то 40% балів за цей тест; </p>

7. якщо ~3\cdot d_0<d\leqslant 5\cdot d_0~, то 20% балів за цей тест; </p>

8. якщо ~5\cdot d_0<d\leqslant 8\cdot d_0~, то 10% балів за цей тест; </p>

9. якщо ~d>8\cdot d_0~, то 5% балів за цей тест.

Приклади

Вхід

4
0 0
2 0.2
7 0.7
5 0.5

Результат

1.40698258695692E+0001
2 4 3

Вхід

5
1 0
4 4
3 2
4 0
1 1

Результат

1.24721359549995E+0001
5 3 2 4

Примітки

Задача з такими обмеженнями, по ідеї, повинна НЕ вирішуватися ніякими точними методами.

Вам доступний через систему DMOJ дещо детальніший, чим для решти задач, протокол, який містить більшу, чим для решти задач, частину інформації про тести. Однак відповідей-маршрутів там нема, тому просто списати не вийде.

Також, перевірятиметься (вручну), що запропонований Вами код розв'язує задачу по суті. Зокрема, прямо заборонено (тим, хто хоче отримати за цю заддачу хоч якісь бали в дисципліну «Алгоритми та структури даних») діяти за сценарієм «здати зовсім любо-що; взнати, які тести; якось познаходити відповіді для конкретно цих вхідних даних; здати програму, яка лише виводить готові відповіді для відомих їй тестів».

Тести 1 та 2 є тестами з умови, вони не приносять балів.

Тести з 3-го по 12-й задовольняють обмеження ~16\leqslant n\leqslant 25~; для них «найкоротший з відомих автору задачі маршрутів» і є гарантовано об'єктивно мінімальним. (Це перевірено точним алгоритмом, але для деяких із тестів він працював довше та займав більше пам'яті, чим відведено часу на сайті.)

Тести з 13-го по 27-й задовольняють обмеження ~30\leqslant n\leqslant 100~; для них невідомо, чи є «найкоротший з відомих автору задачі маршрутів» об'єктивно мінімальним. Тому, не виключено (геть зовсім не гарантовано, але й не виключено), що Вам вдасться знайти маршрут коротший, чим досі відомий автору задачі. Якщо таке справді станеться (Ви повинні знайти це в логах перевірки самостійно й повідомити) – це буде причиною для додаткових балів. Однак, лише т(ому/ій) одн(ому/ій) студент(у/ці), в чиєму розв'язку таке виявиться, й лише за умови, що він/вона може захистити, що написано в коді. Гарантовано, що ця краща відповідь не буде використана для жорсткішої перевірки цього ж навчального року (ніяких гарантій щодо подальших років), але й інші студенти цього ж навчального року вже не зможуть отримати такі бонусні бали за цей самий тест і аналогічний алгоритм.