Стоунхендж 2077

«Крoмлех – древнее сооружение, как правило, позднего неолита или раннего бронзового века,
представляющее собой несколько поставленных вертикально в землю продолговатых камней,
образующих одну или несколько концентрических окружностей.»
(Материал из Википедии – свободной энциклопедии)

В будущем 2077-м году миру откроется заповедник «Стоунхендж 2077» – продвинутая версия легендарной английской достопримечательности. Он будет представлять из себя n камней, расположенных по кругу и образующих правильный n-угольник. Камни пронумерованы от 1 до n по часовой стрелке, если смотреть на конструкцию сверху.

Уже сейчас администрация заповедника планирует открытие первого туристического сезона. Планируется проведение экскурсий внутри заповедника. Каждая экскурсия будет соединять два различных камня. Между этими двумя камнями будет проложена прямая дорога, по которой будут ходить люди.

Ваша задача – организовать создание и закрытие экскурсии по запросам администрации. Главное правило, которое должно соблюдаться на протяжении всего времени: во избежание столкновений никакие две экскурсии не должны пересекаться или иметь общий конец. Формально, администрация будет давать вам команды двух типов:

• «link a b» – запрос на создание экскурсии между камнями a и b (1 ≤ a, b ≤ n; a ≠ b). Если возможно создать такую экскурсию, то создать её и сообщить администрации её порядковый номер. Номера выдаются в порядке создания экскурсий, начиная с единицы. Если же создание невозможно из-за пересечения с какими-либо уже существующими экскурсиями – сообщить об ошибке и не создавать.
• «cut k» – запрос на отмену экскурсии с порядковым номером k. Гарантируется, что на момент запроса экскурсия с таким номером существует в программе заповедника.

Входные данные

В первой строке входного файла INPUT.TXT содержатся два целых числа n – количество камней, и m – количество команд (3 ≤ n ≤ 10⁹; 1 ≤ m ≤ 3×10⁵). В следующих m строках содержатся команды в формате, описанном выше.

Выходные данные

В выходной файл OUTPUT.TXT для каждой операции первого типа в отдельной строке выведите «added as k», где k – номер экскурсии, если её можно проводить в данный момент, и «error», если невозможно.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]