Сборка гирлянды
Вася на Новый год купил ёлочную гирлянду "Сделай сам".
В ее комплект входят:
2·N разноцветных лампочек, среди них нет лампочек одинакового цвета;
2·N патронов, в которые эти лампочки нужно вкрутить;
достаточное количество проводов, чтобы соединить патроны с вкрученными в них лампочками в сеть.
Каждый патрон имеет некоторое количество контактов для подсоединения проводов. В комплекте представлено N типов патронов. Патрон первого типа имеет один контакт для подсоединения провода, у патрона второго типа таких контактов два, у патрона третьего типа ― три контакта для проводов, и т.д. Патроны типа N снабжены N контактами для подсоединения проводов. Патронов каждого типа представлено ровно по две штуки.
Гирлянда заработает, если так распределить лампочки по патронам и соединить соответствующие патроны проводами, чтобы выполнились следующие условия:
у всех патронов все контакты для проводов должны быть использованы;
к одному контакту патрона должен быть подсоединен только один провод;
у любого провода оба конца должны быть подсоединены к контактам двух разных патронов;
нельзя два различных патрона соединить более чем одним проводом.
Для Васи эта задача показалась очень трудной. Помогите ему собрать гирлянду к Новому году.
Входные данные
Во входном файле записано целое число N — количество типов патронов (1 ≤ N ≤ 500).
Выходные данные
В первую строку выходного файла необходимо вывести целое число M — количество проводов, которые потребуются для сборки гирлянды. В следующие M строк нужно вывести через пробел по два целых числа ― номера лампочек, вкрученных в патроны, соединенные одним проводом. Лампочки нумеруются числами от 1 до 2·N. Если решений несколько, то выведите любое.