Спрятать заложницу
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фрэнсис Баррисон хочет похитить и спрятать Энн. А как известно, лучшее место, где можно спрятать заложницу — лабиринт.

Фрэнсис знает одно отдаленное от города здание, в котором есть $$$n$$$ комнат. Причем каждая из комнат имеет переход в любую другую комнату.

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

Разумеется, при этом она хочет выбрать лучший из возможных лабиринтов, поэтому она просит вас предложить ей как можно больше возможных планов лабиринтов (план — множество переходов между комнатами, как раз и образующее потенциальный лабиринт).

Очевидно, что планов лабиринтов может быть слишком много, поэтому чтобы не запутаться, она просит вас найти не все возможные планы, а как можно больше попарно непересекающихся по переходам между комнатами планов.

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

В единственной строке входного файла дано целое число $$$n$$$ ($$$2 \leqslant n \leqslant 1000$$$) — число комнат в здании.

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

В первой строке выведите число $$$k$$$ — количество найденных вами планов лабиринтов.

Далее выведите $$$k$$$ последовательностей строк, описывающих каждый из планов лабиринта.

В $$$i$$$-й последовательности строк — описании $$$i$$$-го плана лабиринта — перечислите все переходы между комнатами, которые входят в этот план. Каждый переход между комнатой $$$v_i$$$ и $$$u_i$$$ опишите в отдельной строке в формате «$$$u_i$$$ $$$v_i$$$» (без кавычек).

Последовательности строк, относящиеся к разным планам, разделите пустыми строками.

Примеры

Входные данные
2
Выходные данные
1
1 2
Входные данные
4
Выходные данные
2
1 2
1 3
2 4

3 4
1 4
2 3

Примечание

Синим и красным цветом показаны планы двух непересекающихся лабиринтов во втором примере: