В ходе своих недавних исследований берляндские ученые выяснили, что в Древней Берляндии было n городов, которые были соединены двусторонними дорогами. Любые два города соединены не более, чем одной дорогой. Никакая дорога не соединяет город сам с собой. Согласно известной традиции, сеть дорог строилась таким образом, что невозможно было выбрать такие три города, что из каждого можно проехать в каждый напрямую. То есть не существовало цикла длины ровно 3. К сожалению, карта дорог не дошла до наших времен. Сейчас ученым интересно, насколько развитым государством была Древняя Берляндия. Помогите им: найдите, какое наибольшее число дорог могло быть в государстве. Так же требуется восстановить любую из возможных карт дорог.
В первой строке записано целое число n (1 ≤ n ≤ 100) — количество городов в Берляндии.
В первой строке должно быть записано число m — наибольшее возможное число дорог в Берляндии. Далее выведите m строк по два числа в каждой — номера городов, которые соединяет очередная дорога. Города нумеруются целыми числами от 1 до n. Если решений несколько, выведите любое.
3
2
1 2
2 3
4
4
1 2
2 3
3 4
4 1
| Codeforces Beta Round 40 (Div. 2) |
|---|
| Закончено |
