Митя и граф

В рамках своей дипломной работы маленький Митя изучает графы. Он уже провел исследования различных видов графов, таких как деревья, кактусы, а также полные графы. Сейчас он хочет изучить графы, в которых нет простых четных циклов. Цикл называется простым, если он не проходит через одну вершину более одного раза. Цикл называется четным, если он содержит четное число вершин.

Мите нужно построить такой граф на заданном числе вершин, так чтобы число ребер было максимально. Помогите Мите завершить его исследование.

Первая строка содержит одно целое число n (1 ≤ n ≤ 10 000).

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