Головна ідея задачі та формат вхідних даних цілком тотожні «Задачі комівояжера — 1»; відрізняються лише такі складові:

• максимальний розмір вхідних даних тепер трохи більший;
• тепер потрібно вивести не лише довжину мінімального шляху, а й сам шлях як послідовність вершин.

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

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

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

Вхідні дані

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

Результати

Перший рядок повинен містити єдине число (з плаваючою крапкою) – знайдену мінімальну довжину замкненого маршруту. Ця складова відповіді зараховується, коли абсолютна або відносна похибка (хоча б одна з них) не перевищує ~10^{-9}~.

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

Приклади

Вхід

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

Примітки

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