28576번 - Спрятать заложницу 스페셜 저지다국어

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

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

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

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

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

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

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

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

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

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

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