domino

Pentru un $n$ dat avem la dispoziţie un set complet de piese de domino. Set complet înseamnă că avem câte o piesă pentru fiecare pereche posibilă de numere din mulţimea $\{1, 2 , \dots, n \}$. Numerele de pe o piesă pot fi diferite sau egale. În setul complet fiecare piesă apare o singură dată şi nu avem două piese care conţin aceleaşi numere scrise în altă ordine; piesa $\boxed{i\vphantom{|}}\boxed{j\vphantom{|}}$ este aceeaşi cu piesa $\boxed{j\vphantom{|}}\boxed{i\vphantom{|}}$.

De exemplu, dacă $n = 3$, avem şase piese: $\boxed{1\vphantom{|}}\boxed{1\vphantom{|}}, \boxed{2\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{3\vphantom{|}}\boxed{3\vphantom{|}}, \boxed{1\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{3\vphantom{|}}\boxed{1\vphantom{|}}, \boxed{2\vphantom{|}}\boxed{3\vphantom{|}}$. În jocul de domino, oricare piesă $\boxed{i\vphantom{|}}\boxed{j\vphantom{|}}$ poate fi folosită fie ca $\boxed{i\vphantom{|}}\boxed{j\vphantom{|}}$, şi în acest caz avem în stânga numărul $i$, iar în dreapta numărul $j$, fie ca $\boxed{j\vphantom{|}}\boxed{i\vphantom{|}}$ şi în acest caz avem în stânga numărul $j$, iar în dreapta numărul $i$.

Cu piesele pe care le avem la dispoziţie putem forma un şir, dacă respectăm următoarea regulă: două piese aflate în poziţii alăturate în şir trebuie să conţină prima în dreapta şi a doua în stânga un număr egal. Această regulă o vom numi proprietate “stânga-dreapta”. Excepţie de la această regulă fac prima piesă pentru numărul din stânga şi ultima piesă pentru numărul din dreapta. În acest şir, o piesă nu poate să apară de două ori. Exemple:

• şir corect pentu un set complet cu $n=3$:
  $\boxed{1\vphantom{|}}\boxed{1\vphantom{|}}, \boxed{1\vphantom{|}}\boxed{3\vphantom{|}}, \boxed{3\vphantom{|}}\boxed{3\vphantom{|}}, \boxed{3\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{2\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{2\vphantom{|}}\boxed{1\vphantom{|}}$
• şir corect care nu foloseşte toate piesele ale unui set complet cu $n=3$:
  $\boxed{3\vphantom{|}}\boxed{3\vphantom{|}}, \boxed{3\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{2\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{2\vphantom{|}}\boxed{1\vphantom{|}}$
• şir incorect, cu piese ce nu respectă proprietatea “stânga-dreapta” (piesa a treia şi piesa a patra):
  $\boxed{3\vphantom{|}}\boxed{3\vphantom{|}}, \boxed{3\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{\textcolor{lime}{2}\vphantom{|}}\boxed{\textcolor{lime}{2}\vphantom{|}}, \boxed{\textcolor{lime}{1}\vphantom{|}}\boxed{\textcolor{lime}{2}\vphantom{|}}$
• şir incorect, în care o piesă se foloseşte de două ori (piesa a treia şi piesa a cincea)
  $\boxed{1\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{2\vphantom{|}}\boxed{2\vphantom{|}}, \boxed{\textcolor{lime}{2}\vphantom{|}}\boxed{\textcolor{lime}{3}\vphantom{|}}, \boxed{3\vphantom{|}}\boxed{3\vphantom{|}}, \boxed{\textcolor{lime}{3}\vphantom{|}}\boxed{\textcolor{lime}{2}\vphantom{|}}$

Cerinţă

Determinaţi dacă pentru un $n$ dat se poate forma un şir cu toate piesele de domino dintr-un set complet.

Date de intrare

Fişierul domino.in conţine pe prima linie o singură valoare naturală $n$ cu semnificaţia de mai sus.

Date de ieşire

Fişierul domino.out va conţine pe fiecare linie cele două numere aflate pe câte o piesă din şirul cerut separate prin spaţiu. Prima linie va conţine numerele primei piese, a doua linie va conţine numerele de pe a doua piesă, etc. Numerele unei piese vor fi astfel scrise încât să respecte proprietatea “stânga-dreapta”. Dacă nu există soluţie, pe prima linie a fişierului se afişează valoarea $-1$.

Restricții și precizări

• $2 \leq n \leq 1 \ 500$.
• Pot exista mai multe soluţii, se acceptă orice soluţie corectă.

Exemplu

domino.in

3

domino.out

1 1
1 2
2 2
2 3
3 3
3 1