Фрэнсис Баррисон хочет похитить и спрятать Энн. А как известно, лучшее место, где можно спрятать заложницу — лабиринт.
Фрэнсис знает одно отдаленное от города здание, в котором есть $$$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
Синим и красным цветом показаны планы двух непересекающихся лабиринтов во втором примере: