Это интерактивная задача.
Алиса и Боб изобрели игру «Точки и отрезки», в которую они играют на скучных уроках геометрии.
Поле для игры представляет собой листок бумаги, на котором отмечены $$$n$$$ различных точек, никакие три из которых не лежат на одной прямой. После этого они по очереди делают ходы, Алиса ходит первой. Ход очередного игрока заключается в том, что он выбирает две точки и соединяет их отрезком. При этом проведенный отрезок не должен иметь общих внутренних точек с ранее проведенными отрезками (иметь общие концы разрешается). Тот, кто не может сделать ход, — проигрывает.
В этой задаче ваше решение должно сыграть в «Точки и отрезки» против программы жюри и выиграть. Вашей программе будет передано поле с $$$n$$$ точками и предложено выбрать, за кого играть, за Алису или за Боба. Затем ваша программа должна делать ходы за выбранного игрока, пока не победит.
Сначала ваша программа должна считать целое число $$$n$$$ — количество точек на поле ($$$3 \le n \le 300$$$).
Затем необходимо считать $$$n$$$ пар целых чисел $$$(x_i, y_i)$$$ — координаты точек ($$$-10^4\le x_i, y_i \le 10^4$$$; все точки различны, никакие три точки не лежат на одной прямой).
Проанализировав поле, ваша программа должна решить, за кого она хочет играть — за Алису или за Боба, и вывести $$$1$$$, если хочет играть за Алису и ходить первой, либо $$$2$$$, если хочет играть за Боба и ходить второй. После выведенного числа следует перевести строку.
После этого игроки делают ходы по очереди, в соответствии с выбором вашей программы. Если очередной ход принадлежит вашей программе, она должна вывести два числа на строке: $$$i$$$ и $$$j$$$ — номера точек, которые она соединяет отрезком ($$$1 \le i, j \le n$$$; $$$i$$$ и $$$j$$$ должны быть различны, проведенный отрезок не должен иметь общих внутренних точек с ранее проведенными отрезками). Если очередной ход делает программа жюри, она выводит свой ход в том же формате.
Если ваша программа находится в ситуации, что она должна сделать очередной ход, а сделать его невозможно, она будет принудительно завершена (программа жюри и тестирующая система не будут дожидаться реакции вашей программы на эту ситуацию). Если ваша программа выиграет, программа жюри вместо очередного своего хода выведет «0 0». Считав эту информацию, ваша программа должна завершиться.
3 0 0 10 0 0 10 1 3 0 0
1 1 2 2 3
4 0 0 10 0 5 7 5 3 1 2 1 3 2 3 0 0
2 1 4 2 4 3 4
В примере выше сообщения программы жюри и программы участника отформатированы пустыми строками так, чтобы было видно, ответом на что является какое сообщение. В реальном взаимодействии пустых строк не будет во вводе, и не следует делать их в выводе. Однако помните, что после любого вывода необходимо переводить строку!
