Реформа
На одной замечательной плоскости с декартовой системой координат испокон веков была расположена очень консервативная страна. В этой стране испокон веков было N городов, пронумерованных последовательными целыми числами от 1 до N. По сравнению с бесконечностью плоскости города, даже очень большие, очень невелики, поэтому мы будем считать их точками на плоскости. Координаты i-го города — (X_i, Y_i). Координаты любых двух городов различны. Никакие 3 города не лежат на одной прямой линии.
Некоторые пары городов соединены двунаправленными дорогами. Каждая дорога — это отрезок прямой линии, соединяющий некоторые два города. Известно, что из каждого города выходит ровно 3 дороги. Никакая дорога не соединяет город с самим собой. Между каждой парой городов может быть не более одной дороги.
Так обстояли дела в этой стране с незапамятных времен, и никому даже не приходило в голову что-либо поменять. Но вот произошла беда — к власти пришел либеральный король! И проблемы не заставили себя ждать – незамедлительно последовал указ о реформе дорожного сообщения в стране. Было приказано убрать некоторые дороги так, чтобы в результате:
Из каждого города выходило ровно 2 дороги.
Угол поворота между двумя дорогами, выходящими из одного и того же города, был строго меньше 60 градусов.
Никакие две дороги не пересекались нигде, кроме как в городах.
Угол поворота между двумя дорогами вычисляется следующим образом. Пусть из города B дороги идут в города A и C. Тогда угол поворота между ними равен внешнему углу при вершине B в треугольнике ABC (см. рисунок).
Реализация реформы была поручена министру транспорта. Именно ему предстоит решить, какие дороги убрать, а какие оставить. Желая угодить королю, среди всех возможных способов решения поставленной королем задачи, министр хочет выбрать такой, в котором максимальный из углов поворота между двумя дорогами из одного и того же города минимален.
Входные данные
Первая строка входного файла содержит целое число N. Каждая из следующих N строк содержит 5 целых чисел. Первые два числа в i-й из этих строк — это X_i и Y_i. Следующие три числа — это номера городов, с которыми i-й город изначально соединен дорогами.
Все числа во входных данных целые. 4 ≤ N ≤ 200, N — четное, -10^5 ≤ X_i, Y_i ≤ 10^5.
Координаты никаких двух городов не совпадают. Никакие 3 города не лежат на одной прямой линии.
Каждый город соединен дорогами ровно с 3-мя городами.
Между парой городов может быть не более одной дороги. Никакая дорога не соединяет город с самим собой. Любые два угла поворота (не обязательно при одном городе) в стране до реформы различаются не менее чем на 10^{-5} градуса.
Любой угол поворота в стране до реформы отличается от угла в 60 градусов не менее чем на 10^{-5} градуса.
Выходные данные
Если поставленные королем условия выполнить невозможно, выведите единственную строку содержащую "Minister's life is short :(" (без крайних кавычек). Символы ’, : и ( имеют ASCII-коды 39, 58 и 40 соответственно.
Иначе выведите способ решения задачи, который следует выбрать министру, в виде N целых чисел, разделенных пробелами. Если i-е из выведенных чисел равно j, это означает, что министру следует убрать дорогу между городами i и j.