Реформа#1911

Реформа

2 секунди

64 мегабайти

Дуже складна

На мальовничій площині з декартовою системою координат з давніх-давен існувала дуже традиційна країна. У цій країні було $N$ міст, пронумерованих підряд від $1$ до $N$ . Незважаючи на свої розміри, ці міста вважаються точками на площині через її безмежність. Координати $i$ -го міста — це $(X_{i}, Y_{i})$ (X_i, Y_i), причому жодна пара міст не має однакових координат. Жодні $3$ міста не лежать на одній прямій.

Деякі пари міст сполучені двосторонніми дорогами, кожна з яких є відрізком прямої між двома містами. Від кожного міста відходить рівно $3$ дороги. Жодна дорога не веде з міста в себе, і між будь-якою парою міст не більше однієї дороги.

Цей порядок не змінювався віками, аж поки до влади не прийшов ліберальний король і не почав проводити масштабні реформи. Був виданий указ про реформу дорожньої мережі, який вимагає:

Від кожного міста має відходити рівно $2$ дороги.
Кут повороту між цими двома дорогами в одному місті має бути строго меншим, ніж $60$ градусів.
Дві дороги не повинні перетинатися ніде, окрім міст.

Кут повороту між двома дорогами визначається так: якщо з міста $B$ ведуть дороги до міст $A$ і $C$ , то кут повороту — це зовнішній кут при вершині $B$ у трикутнику $A B C$ (див. малюнок).

Відповідальність за виконання цієї реформи було покладено на міністра транспорту. Він має визначити, які дороги прибрати, а які залишити. Щоб догодити королю, міністр прагне знайти таке рішення, за якого максимальний кут повороту між двома дорогами з будь-якого міста буде мінімальним.

Вхідні дані

Перший рядок містить одне ціле число $N$ . Кожен із наступних $N$ рядків містить $5$ цілих чисел. Перші два числа у $i$ -му рядку — це $X_{i}$ X_i та $Y_{i}$ Y_i. Наступні три числа — номери міст, які сполучені з $i$ -м містом дорогами.

Всі числа у вхідних даних — цілі. $4 \leq N \leq 200$ 4 \leq N \leq 200, $N$ — парне, $- 1 0^{5} \leq X_{i}, Y_{i} \leq 1 0^{5}$ -10^5 \leq X_i, Y_i \leq 10^5.

Жодні два міста не мають однакових координат. Жодні $3$ міста не лежать на одній прямій.

Кожне місто сполучене дорогами рівно з $3$ іншими містами.

Між будь-якою парою міст не більше однієї дороги. Жодна дорога не з'єднує місто із самим собою. Будь-які два кути повороту (не обов'язково в одному місті) до реформи різняться щонайменше на $1 0^{- 5}$ 10^{-5} градуса.

Будь-який кут повороту до реформи різниться з $60$ градусами щонайменше на $1 0^{- 5}$ 10^{-5} градуса.

Вихідні дані

Якщо неможливо виконати вимоги короля, виведіть у єдиному рядку Minister's life is short :(.

Інакше виведіть рішення міністра у вигляді $N$ цілих чисел, розділених пробілами. Якщо $i$ -те число у відповіді дорівнює $j$ , це означає, що міністр має видалити дорогу між містами $i$ та $j$ .

Приклади

Приклад 1