ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Winter 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Армия магов

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
На собрании стояла довлеющая тишина. Стало окончательно ясно, что после битвы на Севере все члены великого войска Коалиции закончат карьеру боевых магов и займут руководящие должности Наставников. А значит, нужно срочно набирать новую боеспособную армию. Лишь мудрый Сандро нарушал тишину скрипом пера о бумагу — он выписывал имена достойных по его мнению кандидатов. Наконец, он закончил. На листке были написаны 5n имён. Но суровые законы предписывали выбрать лишь n достойнейших магов. После долгих споров, было решено создать армию, в которой каждая пара магов уважала бы друг друга.
Как известно, в королевстве все маги живут в отдельных домах, расположенных в точках плоскости с целыми координатами. Так получилось, что маги уважают друг друга в том и только в том случае, если на отрезке, соединяющем их дома, лежит хотя бы одна точка с целыми координатами, отличная от концов отрезка. Например, если дома расположены в точках (1,1) и (5,5), то эти маги уважают друг друга, так как между их домами есть точка (2,2). А вот жильцы домов с координатами (0,0) и (1,10), увы, не относятся друг к другу с уважением. Помогите правительству королевства собрать армию!

Исходные данные

В первой строке записано целое число n (1 ≤ n ≤ 5000). В i-й из следующих 5n строк записана пара целых чисел x и y, по модулю не превосходящих 10000 — координаты дома i-го кандидата в армию. Все дома расположены в различных точках.

Результат

Если искомая армия существует, в первой строке выведите «OK», а во второй строке запишите через пробел в произвольном порядке n чисел — номера выбранных кандидатов. Если возможных ответов несколько, выведите любой. Если армию создать нельзя, выведите «IMPOSSIBLE».

Пример

исходные данныерезультат
2
1 1
5 5
0 0
2 2
0 10
6 6
7 7
8 8
9 9
10 10
OK
2 1
Автор задачи: Евгений Курпилянский
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1690. Армия магов