Юпітеріанські ювеліри#3151
Юпітер відомий своїми майстрами-ювелірами. Найцінніші прикраси в усій Сонячній системі — це плоскі орнаменти, що складаються з діамантів, з'єднаних золотими містками. Місток — це прямий відрізок дроту, який сполучає два дорогоцінних камені. Гарний орнамент вважається зв'язним, тобто діаманти не можна розбити на дві групи так, щоб жодного містка не було між каменями з різних груп.
Традиційно в кожному орнаменті присутній фірмовий смарагд із трьома петлями, кожна з яких прикріплена до золотого містка. Це дозволяє смарагду з'єднувати два або три діаманти. Йовіанський Фаберже розміщує свій смарагд у центрі орнаменту, а йовіанський Леонардо — ближче до лівого нижнього кута. Ці смарагди не лише ознака майстра, але й спосіб економити на золоті, тому найвинахідливіші ювеліри розташовують свої смарагди там, де це дозволяє мінімізувати використання дорогоцінного металу. У майстра є необмежена кількість смарагдів, тому вони вважаються безкоштовними. Іноді ювеліри не додають фірмовий камінь, якщо це збільшує витрати золота або не дає жодної вигоди.
Прем'єр-міністр Юпітера щодня замовляє нову прикрасу у придворних ювелірів для своєї коханої. Щоб забезпечити унікальність, він часто сам придумує їхню форму, тож коли робота починається, у ювеліра вже є план розміщення всіх каменів. Нещодавно прем'єр-міністр помітив надлишкове використання золота і планує найняти нового головного придворного ювеліра. Чинний майстер, прагнучи зберегти посаду, просить вас допомогти створити оптимальний дизайн прикраси з мінімальним використанням золотого дроту.
У першому рядку задано одне ціле число — кількість діамантів, які прем'єр-міністр бажає бачити в орнаменті. Далі в рядках наведені координати діамантів за планом: у кожному рядку по два числа через пробіл.
Координати у всіх тестах — цілі числа, що не перевищують 10^4 за абсолютною величиною. Кількість діамантів не перевищує .
У першому рядку виведіть одне дійсне число — сумарну довжину золотих дротяних відрізків у оптимальному плані.
У наступному рядку виведіть два дійсних числа — координати смарагду. Далі виведіть — кількість діамантів, з'єднаних зі смарагдом, а потім чисел — їхні номери. Номери не повинні повторюватись. Якщо у оптимальному плані смарагд відсутній, має дорівнювати нулю, а координати можуть бути довільними. Таким чином, може дорівнювати , або .
У наступному рядку виведіть число — кількість містків, що з'єднують діаманти. У наступних рядках виведіть по два числа — номери діамантів, які з'єднані містком.
Діаманти нумеруються від до .
Якщо існує кілька правильних відповідей, виведіть будь-яку.
Ваша відповідь буде звірятися з правильною з абсолютною або відносною похибкою 10^{-6}.
Приклад 1