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,...,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 i|j este aceeaşi cu piesa j|i.
De exemplu, dacă n=3, avem şase piese:
În jocul de domino, oricare piesă i|j poate fi folosită fie ca i|j, şi în acest caz avem în stânga numărul i, iar în dreapta numărul j, fie ca j|i ş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 pentru un set complet cu n=3:
• şir corect care nu foloseşte toate piesele ale unui set complet cu n=3:
• şir incorect, cu piese ce nu respectă proprietatea “stânga-dreapta” (piesa a treia şi piesa a patra):
• şir incorect, în care o piesă se foloseşte de două ori (piesa a treia şi piesa a cincea)
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 domino2.in conţine pe prima linie o singură valoare naturală n cu semnificaţia de mai sus.
Date de ieşire
Fişierul domino2.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
• 2 ≤ n ≤ 1500
• Pot exista mai multe soluţii, se acceptă orice soluţie corectă.
