Question

pbinfo #685 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,...,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 este aceeaşi cu piesa .

De exemplu, dacă n=3, avem şase piese: . În jocul de domino, oricare piesă poate fi folosită fie ca , şi în acest caz avem în stânga numărul i, iar în dreapta numărul j, fie ca ş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:

ş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ța

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

1 ≤ n ≤ 1500
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

Answer 1

Iata sursa C++, atasata.

0fcb841ee9964c8f0a53bd4b4545dd79.cpp