Privet ljudi.
Skagu prjamo mne nadojeli etistolbi
.
Каждый из расположенных вдоль Н-ского проспекта N фонарных столбов покрашен в один из трех цветов: серый, бурый или малиновый. Главный архитектор хочет, чтобы к юбилею города все столбы имели одинаковый цвет. Он решил составить план перекраски, но знакомиться с имеющейся раскраской у него нет времени. Поэтому план должен быть универсальным, то есть приводить к нужному результату при любой начальной раскраске. План состоит из списка пар столбов. Этот список просматривается последовательно. Если оба столба очередной пары списка имеют одинаковый цвет, то их не трогают, иначе они перекрашиваются в третий цвет (не совпадающий с их цветами).
Помогите главному архитектору составить такой план, по возможности меньшей длины.
Формат выходных данных
Решением задачи являются выходные файлы. Если задачу решить невозможно, первая строка должна содержать число 0. В противном случае первая строка должна содержать число M - количество пар в плане, каждая из следующих M строк должна содержать пару чисел - номера столбов.
Размер выходного файла не должен превышать 100 килобайт
.
Примеры
N=3
0
N=4
4
1 2
3 4
1 3
2 4
Nu probujte.Budu ochen blagodaren za vach trud
.