Liga piłkarska

Limit pamięci: 32 MB

W lidze piłkarskiej gra drużyn ( jest liczbą parzystą). W ramach jednej rundy rozgrywek każda drużyna gra z każdą inną dokładnie raz. Runda składa się z kolejek, każda drużyna rozgrywa w kolejce jeden mecz. Rozgrywki są najciekawsze dla kibiców, gdy kolejne mecze ich drużyny rozgrywane są na przemian: u siebie, na wyjeździe, u siebie, na wyjeździe, itd. Niestety nie zawsze istnieje terminarz rozgrywek, w którym żadna drużyna nie gra dwóch kolejnych meczów u siebie ani dwóch kolejnych meczów na wyjeździe. Konstruując terminarz rozgrywek, należy się jednak starać, aby liczba takich sytuacji była jak najmniejsza. (Jeśli, na przykład, drużyna gra mecz na wyjeździe, następnie cztery mecze u siebie, a potem jeszcze jeden mecz na wyjeździe, to mamy trzy niepożądane sytuacje.)

Twoim zadaniem jest skonstruowanie terminarza rozgrywek ligi, w którym liczba sytuacji, takich że drużyna gra dwa kolejne mecze u siebie lub na wyjeździe, jest możliwie najmniejsza. Terminarz powinien składać się z kolejek. W każdej kolejce powinno być rozgrywanych meczów, przy czym każda drużyna powinna grać dokładnie jeden mecz w kolejce. W całej rundzie powinno zostać rozegranych meczów, każda drużyna powinna zagrać z każdą inną dokładnie raz. Każdy mecz jest rozgrywany na stadionie jednej z grających w nim drużyn - ta drużyna gra u siebie, drużyna przecina na wyjeździe. Liczba sytuacji, w których drużyna gra dwa kolejne mecze u siebie lub dwa kolejne mecze na wyjeździe, powinna być możliwie najmniejsza.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę drużyn,
• obliczy minimalną liczbę sytuacji, w których drużyna gra dwa kolejne mecze u siebie lub na wyjeździe,
• skonstruuje terminarz rozgrywek, dla którego wartość ta jest osiągana,
• wypisze wyniki na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz standardowego wejścia zawiera parzystą liczbę całkowitą () - liczbę drużyn biorących udział w rozgrywkach ligi.

Wyjście

Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą - minimalną liczbę sytuacji, w których drużyna gra dwa kolejne mecze u siebie lub dwa kolejne mecze na wyjeździe. Kolejne wierszy powinno zawierać opis terminarza rozgrywek: wiersz -szy powinien zawierać opis -tej kolejki.

Opis kolejki składa się z różnych liczb całkowitych z zakresu , pooddzielanych pojedynczymi odstępami. Para (dla ) oznacza, że w danej kolejce rozgrywany jest mecz między drużynami i . Drużyna gra u siebie, a drużyna na wyjeździe.

Przykład

Dla danych wejściowych:

4

poprawną odpowiedzią jest:

2
1 4 2 3
1 2 4 3
2 4 3 1

Autor zadania: Jakub Pawlewicz.