Армия магов
Армия магов
На собрании стояла довлеющая тишина. Стало окончательно ясно, что после битвы на Севере все члены великого войска Коалиции закончат карьеру боевых магов и займут руководящие должности Наставников. А значит, нужно срочно набирать новую боеспособную армию. Лишь мудрый Сандро нарушал тишину скрипом пера о бумагу - он выписывал имена достойных по его мнению кандидатов. Наконец, он закончил. На листке были написаны 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