Задачі
Реформа
Реформа
На одній чудовій площині з декартовою системою координат з давніх давен була розміщена дуже консервативна країна. У цій країні з давніх давен було \textbf{N} міст, пронумерованих послідовними цілими числами від \textbf{1} до \textbf{N}. У порівнянні з нескінченністю площини міста, навіть дуже великі, дуже невеликі, тому ми будемо вважати їх точками на площині. Координати \textbf{i}-го міста --- (\textbf{X_i}, \textbf{Y_i}). Координати довільних двох міст різні. Ніякі \textbf{3} міста не лежать на одній прямій лінії.
Деякі пари міст з'єднані двосторонніми дорогами. Кожна дорога --- це відрізок прямої лінії, який з'єднує деякі два міста. Відомо, що з кожного міста виходить рівно \textbf{3} дороги. Ніяка дорога не з'єднує місто саме з собою. Між кожною парою міст може бути не більше однієї дороги.
Так йшли справи у цій країні з незапам'ятних часів, і нікому навіть не приходило до голови що-небудь змінити. Але ось пройшла біда --- до влади прийшов ліберальний король! І проблеми не заставили себе чекати -- негайно було видано указ про реформу дорожного сполучення у країні. Було наказано прибрати деякі дороги так, щоб у результаті:
\begin{itemize}
\item З кажного міста виходило рівно \textbf{2} дороги.
\item Кут повороту між двома дорогами, які виходять із одного і того ж міста, був строго меншим \textbf{60} градусів.
\item Ніякі дві дороги не перетинались ніде, крім як у містах.
\end{itemize}
Кут повороту між двома дорогами обчислюється наступним чином. Нехай з міста \textbf{B} дороги йдуть у міста \textbf{A} і \textbf{C}. Тоді кут повороту між ними дорівнює зовнішньому куту при вершині \textbf{B} у трикутнику \textbf{ABC} (див. рисунок).
\includegraphics{https://static.e-olymp.com/content/92/92d2fc7497b5e546101170e331444d312807f563.jpg}
Реалізацію реформи було доручено міністру транспорту. Саме йому належить вирвшити, які дороги видалити, а які залишити. Бажаючи догодити королю, серед усіх можливих способів вирішення поставленої королем задачі, міністр хоче вибрати такий, у якому максимальний з кутів повороту між двома дорогами із одного і того ж міста мінімальний.
\InputFile
Перший рядок вхідного файлу містить ціле число \textbf{N}. Кожен з наступних \textbf{N} рядків містить \textbf{5} цілих чисел. Перші два числа у \textbf{i}-му з цих рядків --- це \textbf{X_i} і \textbf{Y_i}. Наступні три числа --- це номери міст, з якими \textbf{i}-те місто спочатку з'єднано дорогами.
Всі числа у вхідних даних цілі. \textbf{4} ≤ \textbf{N} ≤ \textbf{200}, \textbf{N} --- парне, \textbf{-10^5} ≤ \textbf{X_i}, \textbf{Y_i} ≤ \textbf{10^5}.
Координати ніяких двох міст не співпадають. Ніякі \textbf{3} міста не лежать на одній прямій лінії.
Кожне місто з'єднано дорогами рівно з \textbf{3}-ма містами.
Між парою міст може бути не більше однієї дороги. Ніяка дорога не з'єднує місто саме з собою. Довільні два кути повороту (не обов'язково при одному місті) у країні до реформи відрізняються не менше ніж на \textbf{10^\{-5\}} градуса.
Довільни кут повороту у країні до реформи відрізняється від кута у \textbf{60} градусів не менше ніж на \textbf{10^\{-5\}} градуса.
\OutputFile
Якщо поставлені королем вимоги виконати неможливо, виведіть єдиний рядок, що містить "\textbf{Minister's life is short :(}" (без крайніх лапок). Символи \textbf{’}, \textbf{:} та \textbf{(} мають \textbf{ASCII}-коди \textbf{39}, \textbf{58} і \textbf{40} відповідно.
Інакше виведіть спосіб розв'язання задачі, який слід вибрати міністру, у вигляді \textbf{N} цілих чисел, відокремлених пропусками. Якщо \textbf{i}-те із виведених чисел рівне \textbf{j}, це означає, що міністру слід видалити дорогу між містами \textbf{i} та \textbf{j}.
Вхідні дані #1
4 0 0 2 3 4 41 0 1 3 4 0 42 4 2 1 43 44 2 3 1
Вихідні дані #1
Minister's life is short :(