2014 весна: Тур 27 марта

2. Юбилейная

Каждый из расположенных вдоль Н-ского проспекта N фонарных столбов покрашен в один из трех цветов: серый, бурый или малиновый. Главный архитектор хочет, чтобы к юбилею города все столбы имели одинаковый цвет. Он решил составить план перекраски, но знакомиться с имеющейся раскраской у него нет времени. Поэтому план должен быть универсальным, то есть приводить к нужному результату при любой начальной раскраске. План состоит из списка пар столбов. Этот список просматривается последовательно. Если оба столба очередной пары списка имеют одинаковый цвет, то их не трогают, иначе они перекрашиваются в третий цвет (не совпадающий с их цветами).

Помогите главному архитектору составить такой план, по возможности меньшей длины.

Система оценки

В каждом тесте за правильный план вы получаете от половины до полного балла, в зависимости от длины плана. За самый короткий план среди полученных для данного теста вы получите полный балл.

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

Вам предлагается решить эту задачу для следующих входных данных:

Тест 1: N=5 Тест 2: N=7 Тест 3: N=8 Тест 4: N=12 Тест 5: N=25 Тест 6: N=32

Тест 7: N=34 Тест 8: N=128 Тест 9: N=253 Тест 10: N=511 Тест 11: N=999 Тест 12: N=1000

Формат выходных данных

Решением задачи является архив. Архив должен иметь расширение zip, и содержать в себе файлы, ответы на тест. Каждый файл имеет имя 01, 02, 03,...,11,12 в зависимости от теста. Первая строка каждого файла должна содержать число N для данного теста. Если задачу решить невозможно, вторая строка должна содержать число 0. В противном случае вторая строка должна содержать число M — количество пар в плане, каждая из следующих M строк должна содержать пару чисел — номера столбов.

Размер архива не должен превышать 2МБ.

Примеры