Рабочее место участника

Сверхсекретный завод, расположенный высоко в горах, занимается изготовлением новейших систем контроля торсионных полей — нанокристаллов. Нанокристалл состоит из нескольких атомов, некоторые из которых попарно связаны сверхпрочными торсионными связями.

Нанокристалл стабилен, если между любыми двумя его атомами можно построить соединяющую их цепочку связей, возможно с использованием других атомов. Например, нанокристалл `X` из четырех атомов `A`, `B`, `C` и `D`, в котором между собой связаны пары `A-B`, `A-C`, `B-C` и `B-D`, стабилен. Если же, например, в нанокристалле из данных четырех атомов связаны только пары `A-B` и `C-D`, то кристалл нестабилен, поскольку, например, `A` и `C` не соединены никакой цепочкой связей.

Для любой пары атомов стабильного нанокристалла определена их взаимная удаленность — минимальная длина цепочки из связей, которая их соединяет. Например, рассмотрим описанный выше нанокристалл `X`. Взаимная удаленность атомов `A` и `B` равна единице (они соединены напрямую), а взаимная удаленность `C` и `D` равна двум (они соединены цепочками `C-B-D` и `C-A-B-D`, длина кратчайшей цепочки равна двум).

Важнейшей характерикой стабильного нанокристалла является его емкость. Емкость нанокристалла равна сумме взаимных удаленностей всех пар его атомов. Например, емкость нанокристалла `X` равна 8.

Недавно на завод поступил заказ — разработать стабильный нанокристалл заданной емкости `c`. При этом как число атомов в нанокристалле, так и число связей может быть произвольным. Помогите ученым разработать такой кристалл!

Входной файл содержит целое число `c` (`1\ ≤\ c\ ≤\ 10\ 000`).

На первой строке выходного файла выведите два целых числа `n` и `m` — количество атомов и связей в разработанном нанокристалле, соответственно. Будем считать, что атомы нанокристалла пронумерованы от 1 до `n`. Следующие `m` строк должны содержать по два целых числа — пары атомов, которые следует соединить торсионными связями. Если решений несколько, выведите любое.

Если искомого нанокристалла не существует, выведите на первой выходного файла строке два нуля.

8

4 4
1 2
1 3
2 3
2 4

2

0 0